## Thursday, July 27, 2017

### [Leetcode] Maximum Length of Pair Chain, Solution

You are given `n` pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair `(c, d)` can follow another pair `(a, b)` if and only if `b < c`. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:
```Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]
```
Note:
1. The number of given pairs will be in the range [1, 1000].

[Thoughts]

[Code]

``````1:    int findLongestChain(vector<vector<int>>& pairs) {
2:      if(pairs.size() == 0) return 0;
3:
4:      std::sort(pairs.begin(), pairs.end(), comp);
5:
6:      int count = 1;
7:      vector<int>& pair = pairs[0];
8:      for(int i =1; i<pairs.size(); i++) {
9:        if(pairs[i][0] > pair[1]) {
10:          count ++;
11:          pair = pairs[i];
12:        }
13:      }
14:
15:      return count;
16:    }
17:
18:    static bool comp(vector<int>& a, vector<int>& b) {
19:      return a[1] < b[1];
20:    }
``````

### [Leetcode] Palindromic Substrings, Solution

Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
```Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
```
Example 2:
```Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
```
Note:
1. The input string length won't exceed 1000.

[Thoughts]

[Code]
``````1:    int countSubstrings(string s) {
2:      if(s == "") return 0;
3:
4:      int count = 1;
5:      for(int i =1; i< s.size(); i++) {
6:        // palindrom length is odd and i in the middle
7:        count += countPalindrom(s, i, i);
8:
9:        // palindrom length is even and (i-1, i) in themiddle
10:        count += countPalindrom(s, i-1, i);
11:      }
12:      return count;
13:    }
14:
15:    int countPalindrom(string& s, int start, int end) {
16:      int count = 0;
17:      for(int i =0; start >=0 && end <s.size(); i++)
18:      {
19:        if(s[start] != s[end]) break;
20:
21:        count++;
22:        start--;
23:        end++;
24:      }
25:
26:      return count;
27:    }
``````

### [Leetcode] Replace Words, Solution

In English, we have a concept called `root`, which can be followed by some other words to form another longer word - let's call this word `successor`. For example, the root `an`, followed by `other`, which can form another word `another`.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the `successor` in the sentence with the `root`forming it. If a `successor` has many `roots` can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:
```Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
```
Note:
1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000
[Thoughts]

[Code]
``````1:    string replaceWords(vector<string>& dict, string sentence) {
2:      if(dict.size() == 0) return sentence;
3:      unordered_map<string, int> roots;
4:      for(auto& root : dict) {
5:        roots[root] = 1;
6:      }
7:
8:      string result = "";
9:
10:      stringstream ss(sentence);
11:      string successor ;
12:      while(ss>>successor ) {
13:
14:        string prefix;
15:        for(int i =1; i<= successor.size(); i++) {
16:          prefix = successor.substr(0, i);
17:          if(roots.find(prefix) != roots.end()) break;
18:        }
19:
20:        result += prefix + " ";
21:      }
22:
23:      //remove the end empty space
24:      if (result != "") result.resize(result.size()-1);
25:      return result;
26:    }
``````

## Monday, July 24, 2017

### [Leetcode] Decode String, Solution

Given an encoded string, return it's decoded string.
The encoding rule is: `k[encoded_string]`, where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like `3a` or `2[4]`.
Examples:
```s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
```

[Thoughts]

[Code]
``````1:    string decodeString(string s) {
2:      stack<int> repeat_counts;
3:      stack<string> pre_fix;
4:
5:      int num = 0;
6:      string decoded = "";
7:      string cur = "";
8:
9:      s = "1[" + s +"]"; // wrap the input into a bracket to simplify the logic
10:      for(int i = 0; i< s.size(); i++) {
11:        if(isdigit(s[i])) {
12:          num = num*10 + s[i] -'0';
13:          continue;
14:        }
15:
16:        if(s[i] == '[') {
17:          repeat_counts.push(num);
18:          num = 0;
19:          pre_fix.push(cur);
20:          cur = "";
21:          continue;
22:        }
23:
24:        if(s[i] == ']') {
25:          int repeat = repeat_counts.top();
26:          repeat_counts.pop();
27:          string prefix = pre_fix.top();
28:          pre_fix.pop();
29:
30:          cur = prefix + repeatString(cur, repeat);
31:          continue;
32:        }
33:
34:        cur += s[i];
35:      }
36:
37:      return cur;
38:    }
39:
40:    string repeatString(string& organic, int repeats) {
41:      string result = "";
42:      for(int i =0; i< repeats; i++) {
43:        result += organic;
44:      }
45:
46:      return result;
47:    }
``````

### [Leetcode] House Robber III, Solution

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
```     3
/ \
2   3
\   \
3   1
```
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
```     3
/ \
4   5
/ \   \
1   3   1
```
Maximum amount of money the thief can rob = 4 + 5 = 9.

[Thoughts]

1. root + left_left + left_right + right_left + right_right
2. left + right

[Code]

``````1:    int rob(TreeNode* root) {
2:      if(root == NULL) return 0;
3:
4:      int val = 0;
5:
6:      if(root->left) {
7:        val += rob(root->left->left) + rob(root->left->right);
8:      }
9:
10:      if(root->right) {
11:        val += rob(root->right->left) + rob(root->right->right);
12:      }
13:
14:      return max(root->val + val, rob(root->left) + rob(root->right));
15:    }
``````

### [Leetcode] House Robber II, Solution

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

[Thoughts]

1. 抢劫house 0，那么就不能抢劫house n-1，所以抢劫的范围就是[0, n-2]
2. 不抢劫house 0，那么就得从house 1开始抢，抢劫的范围就是[1, n-1]

[Code]

``````1:    int rob(vector<int>& nums) {
2:      int len = nums.size();
3:
4:      if(len == 0) return 0;
5:      if(len == 1) return nums[0];
6:
7:      return max(robList(nums, 0, len -2), robList(nums, 1, len-1));
8:    }
9:
10:    int robList(vector<int>& nums, int start, int end) {
11:      int rob=0, no_rob=0;
12:      for(int i = start; i<= end; i++) {
13:        int new_rob = no_rob + nums[i];
14:        no_rob = max(rob, no_rob);
15:        rob = new_rob;
16:      }
17:
18:      return max(rob, no_rob);
19:    }
``````

## Sunday, July 23, 2017

### [Leetcode] House Robber, Solution

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

[Thoughts]

rob[i] = no_rob[i-1] + house[i];
no_rob[i] = max( rob[i-1], no_rob[i-1]);

2             1              1               2
rob           2             1              3               4
no_rob      0              2             2               3

[Code]

``````1:    int rob(vector<int>& nums) {
2:      int len = nums.size();
3:
4:      if(len == 0) return 0;
5:
6:      if(len == 1) return nums[0];
7:
8:      int rob=0, no_rob=0;
9:      for(int i =0; i< len; i++) {
10:        int new_rob = no_rob + nums[i];
11:        no_rob = max(rob, no_rob);
12:        rob = new_rob;
13:      }
14:
15:      return max(rob, no_rob);
16:    }
``````

### [Leetcode] Diagonal Traverse, Solution

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.
Example:
```Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

```
Note:
1. The total number of elements of the given matrix will not exceed 10,000.

[Thoughts]

1. 如果row < 0, row = 0, 变换通道
2. 如果col < 0, col = 0, 变换通道
3. 如果 col > N, col = N-1, row = row +2;
4. 如果 row > M, row = M-1. col = col +2;

[Code]
``````1:    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
2:      if(matrix.size() == 0 || matrix[0].size() == 0) return {};
3:
4:      vector<int> result;
5:
6:      vector<pair<int, int>> move_delta{{-1, 1}, {1, -1}};
7:
8:      int rows = matrix.size(), cols = matrix[0].size();
9:      int row = 0, col = 0, m = 0;
10:      for(int i = 0; i< rows * cols; i++) {
11:        result.push_back(matrix[row][col]);
12:        row += move_delta[m].first;
13:        col += move_delta[m].second;
14:
15:        if(row >= rows) {
16:          row = rows-1;
17:          col = col +2;
18:          m = 1-m;
19:        }
20:
21:        if(col >= cols) {
22:          col = cols -1;
23:          row = row + 2;
24:          m = 1-m;
25:        }
26:
27:        if(row < 0) {
28:          row = 0;
29:          m = 1-m;
30:        }
31:
32:        if(col < 0) {
33:          col = 0;
34:          m = 1-m;
35:        }
36:      }
37:      return result;
38:    }
``````

### [Leetcode] Optimal Account Balancing, Solution

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for \$10. Then later Chris gave Alice \$5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y \$z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as `[[0, 1, 10], [2, 0, 5]]`.
Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Note:
1. A transaction will be given as a tuple (x, y, z). Note that `x ? y` and `z > 0`.
2. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Example 1:
```Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 \$10.
Person #2 gave person #0 \$5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 \$5 each.
```
Example 2:
```Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 \$10.
Person #1 gave person #0 \$1.
Person #1 gave person #2 \$5.
Person #2 gave person #0 \$5.

Therefore, person #1 only need to give person #0 \$4, and all debt is settled.
```

[Thoughts]

1. 最后的负债一定可以清零
2. 题目不要求保留原有付款关系。

[Code]
``````1:    int minTransfers(vector<vector<int>>& trans) {
2:      unordered_map<int, long> bal; // balance on each person
3:      for(auto t: trans) {
4:        bal[t[0]] -= t[2];
5:        bal[t[1]] += t[2];
6:      }
7:
8:      vector<long> debt;
9:      for(auto b: bal) {
10:        // only track the person who has debt
11:        if(b.second) debt.push_back(b.second);
12:      }
13:      return dfs(0, 0, debt);
14:    }
15:
16:    // get the min number of transactions starting from s
17:    int dfs(int s, int cnt, vector<long>& debt) {
18:         while (s < debt.size() && !debt[s]) ++s; // skip all zero debt
19:
20:         int res = INT_MAX;
21:         for (long i = s+1, prev = 0; i < debt.size(); ++i) {
22:        // skip same value or same sign debt
23:        if (debt[i] != prev && debt[i]*debt[s] < 0){
24:             debt[i] += debt[s];
25:          res = min(res, dfs(s+1,cnt+1, debt));
26:          debt[i]-=debt[s];
27:          prev = debt[i];
28:        }
29:      }
30:         return res < INT_MAX? res : cnt;
31:    }
``````

### [Leetcode] Alien Dictionary, Solution

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Given the following words in dictionary,
```[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
```
The correct order is: `"wertf"`.
Example 2:
Given the following words in dictionary,
```[
"z",
"x"
]
```
The correct order is: `"zx"`.
Example 3:
Given the following words in dictionary,
```[
"z",
"x",
"z"
]
```
The order is invalid, so return `""`.
Note:
1. You may assume all letters are in lowercase.
2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return any one of them is fine.

[Thoughts]

1. 找出当前入度为0的节点
2. 所有和该节点相连接的节点入度减1
3. go to #1

[Code]
``````1:  string alienOrder(vector<string>& words) {
2:       unordered_map<char, set<char>> outbound;
3:       unordered_map<char, set<char>> inbound;
4:    set<char> no_pre;
5:
6:    string s = "";
7:    for(int i =0; i< words.size(); i++) {
8:      string t = words[i];
9:      no_pre.insert(t.begin(), t.end());
10:      for(int j = 0; j< min(s.size(), t.size()); j++) {
11:        if(t[j] != s[j]) {
12:          inbound[t[j]].insert(s[j]);
13:          outbound[s[j]].insert(t[j]);
14:          break;
15:        }
16:      }
17:      s = t;
18:    }
19:
20:    // get the nodes which has 0 inbound edge
21:    int char_count = no_pre.size();
22:    for(auto p : inbound) {
23:      no_pre.erase(p.first);
24:    }
25:
26:    string result = "";
27:    while(no_pre.size() >0) {
28:      auto it = no_pre.begin();
29:      char c = *it;
30:      no_pre.erase(c);
31:      result+=c;
32:
33:      for(char su : outbound[c]) {
34:        inbound[su].erase(c);
35:        if(inbound[su].size() == 0) {
36:          no_pre.insert(su);
37:        }
38:      }
39:
40:    }
41:       return result.size() == char_count? result : "";
42:  }
``````

## Saturday, July 22, 2017

### [Leetcode] Missing Ranges, Solution

Given a sorted integer array where the range of elements are in the inclusive range [lowerupper], return its missing ranges.
For example, given `[0, 1, 3, 50, 75]`lower = 0 and upper = 99, return `["2", "4->49", "51->74", "76->99"].`

[Thoughts]

1. 可以把lower和upper两个边界值加入到数组里面去，这样避免不必要的if-else。 因为lower和upper不是数组中的数字，他们可以出现在range里面，所以这里添加的边界应该是lower -1 和upper +1
2. 测试数据中有很多边界检测，可以直接用int64_t来跳过检测，省了繁琐的if-else

[Code]
``````1:    vector<string> findMissingRanges(vector<int>& ori_nums, int lower, int upper) {
2:      int64_t right = upper;
3:         int64_t left = lower;
4:      if(ori_nums.size() == 0) return {getRange(left-1, right+1)};
5:      vector<int64_t> nums(ori_nums.size());
6:      std::copy ( ori_nums.begin(), ori_nums.end(), nums.begin() );
7:
8:      // insert lower and upper as boundary of the array
9:      nums.insert(nums.begin(), left-1);
10:      nums.push_back(right+1);
11:
12:      int64_t pre = nums[0];
13:      vector<string> result;
14:      for(int i = 1; i< nums.size(); i++) {
15:        if(nums[i]- pre > 1) {
16:          string range = getRange(pre, nums[i]);
17:          result.push_back(range);
18:        }
19:        pre = nums[i];
20:      }
21:      return result;
22:    }
23:
24:    string getRange(int64_t start, int64_t end) {
25:
27:
29:    }
``````

### [Leetcode] Combination Sum IV, Solution

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
```nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
```
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

[Thoughts]

DP[n] = ∑ DP[target - nums[i]]       0<= i< n

[Code]
``````1:    int combinationSum4(vector<int>& nums, int target) {
2:      vector<int> count(target +1, 0);
3:
4:      count[0] =1;
5:      for(int i =1; i<=target; i++) {
6:        for(int j =0; j< nums.size(); j++) {
7:          if(i - nums[j] >=0) {
8:            count[i] += count[i-nums[j]];
9:          }
10:        }
11:      }
12:
13:      return count[target];
14:    }
``````

### [Leetcode] Remove K Digits, Solution

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.
Example 1:
```Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
```
Example 2:
```Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
```
Example 3:
```Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.```

[Thoughts]

[Code]
``````1:    string removeKdigits(string num, int k) {
2:      string res = "";
3:
4:      for(int i =0; i<num.size(); i++) {
5:        while(res.size()>0 && res.back() > num[i]&& k>0) {
6:          res.pop_back();
7:          k--;
8:        }
9:        res.push_back(num[i]);
10:      }
11:
12:      // if k != 0, remove the digit from right
13:      res.erase(res.size() - k, k);
14:
15:      // trim the zero
16:      int i =0;
17:      while(res[i] == '0' && i<res.size()-1) i++;
18:
19:      res.erase(0, i);
20:
21:      return res.size() == 0? "0": res;
22:    }
``````

### [Leetcode] Frog Jump, Solution

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Note:
• The number of stones is ≥ 2 and is < 1,100.
• Each stone's position will be a non-negative integer < 231.
• The first stone's position is always 0.
Example 1:
```[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping
1 unit to the 2nd stone, then 2 units to the 3rd stone, then
2 units to the 4th stone, then 3 units to the 6th stone,
4 units to the 7th stone, and 5 units to the 8th stone.
```
Example 2:
```[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as
the gap between the 5th and 6th stone is too large.```

[Thoughts]

[Code]
``````1:    bool canCross(vector<int>& stones) {
2:      map<int, set<int>> jumps;
3:
4:      for(int i =0; i< stones.size(); i++) {
5:        jumps[stones[i]] = {};
6:      }
7:
8:      jumps[0].insert(0);
9:
10:      for(int i =0; i< stones.size()-1; i++) {
11:        int index = stones[i];
12:        if(jumps[index].size() == 0) continue;
13:        for(auto step : jumps[index]) {
14:          for(int j = step-1; j<= step+1; j++) {
15:            if(j<0) continue;
16:            if(jumps.find(index+j) != jumps.end())
17:              jumps[index+j].insert(j);
18:          }
19:        }
20:      }
21:
22:      return jumps[stones[stones.size()-1]].size() != 0;
23:    }
``````

### [Leetcode] Ternary Expression Parser, Solution

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits `0-9``?``:``T` and `F` (`T` and `F` represent True and False respectively).
Note:
1. The length of the given string is ≤ 10000.
2. Each number will contain only one digit.
3. The conditional expressions group right-to-left (as usual in most languages).
4. The condition will always be either `T` or `F`. That is, the condition will never be a digit.
5. The result of the expression will always evaluate to either a digit `0-9``T` or `F`.
Example 1:
```Input: "T?2:3"

Output: "2"

Explanation: If true, then result is 2; otherwise result is 3.
```
Example 2:
```Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

"(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
-> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
-> "4"                                    -> "4"
```
Example 3:
```Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

"(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
-> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
-> "F"                                    -> "F"```

[Thoughts]

[Code]
``````1:    string parseTernary(string expression) {
2:      int len = expression.size();
3:
4:      if(len == 0) return expression;
5:
6:      for(int i = len-1; i>=0; i--) {
7:        if(expression[i] != '?') continue;
8:
9:        int index = i;
10:        char result;
11:        if(expression[index-1] == 'T'){
12:          result = expression[index+1];
13:        }else {
14:          result = expression[index+3];
15:        }
16:
17:        expression.erase(index -1, 5);
18:        expression.insert(index-1, 1, result);
19:      }
20:      return expression;
21:    }
``````

### [Leetcode] Valid Triangle Number, Solution

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:
```Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
```
Note:
1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

[Thoughts]

[Code]
``````1:    int triangleNumber(vector<int>& nums) {
2:      if(nums.size() < 3) return 0;
3:
4:      sort(nums.begin(), nums.end());
5:
6:      int count = 0;
7:      for(int third_edge =2; third_edge < nums.size(); third_edge++) {
8:        int first_edge = 0, second_edge = third_edge-1;
9:        while(first_edge < second_edge) {
10:          if(nums[first_edge] + nums[second_edge] > nums[third_edge]) {
11:            count+= second_edge - first_edge;
12:            second_edge --;
13:          }else {
14:            first_edge ++;
15:          }
16:        }
17:      }
18:      return count;
19:    }
``````

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example 1:
```Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
```
Note:
1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].

[Thoughts]

[Code]

``````1:    int leastInterval(vector<char>& tasks, int n) {
2:      unordered_map<char, int> mp;
3:
4:      int count =0;
5:      for(auto t : tasks) {
6:        mp[t]++;
7:        count = max(count, mp[t]);
8:      }
9:
10:      int ans = (count-1)*(n+1);
11:      // in case multiple tasks hold the same max count
12:      for(auto e : mp) {
13:        if(e.second == count) ans++;
14:      }
15:
17:    }
``````

### [Leetcode] Add One Row to Tree, Solution

Given the root of a binary tree, then value `v` and depth `d`, you need to add a row of nodes with value `v` at the given depth `d`. The root node is at depth 1.
The adding rule is: given a positive integer depth `d`, for each NOT null tree nodes `N` in depth `d-1`, create two tree nodes with value `v`as `N's` left subtree root and right subtree root. And `N's` original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth `d` is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.
Example 1:
```Input:
A binary tree as following:
4
/   \
2     6
/ \   /
3   1 5

v = 1

d = 2

Output:
4
/ \
1   1
/     \
2       6
/ \     /
3   1   5

```
Example 2:
```Input:
A binary tree as following:
4
/
2
/ \
3   1

v = 1

d = 3

Output:
4
/
2
/ \
1   1
/     \
3       1
```
Note:
1. The given d is in range [1, maximum depth of the given tree + 1].
2. The given binary tree has at least one tree node.

[Thoughts]

[Code]

``````1:    TreeNode* addOneRow(TreeNode* root, int v, int d) {
2:      if(root == NULL) return root;
3:
4:      if(d == 1) {
5:        TreeNode* newRoot = new TreeNode(v);
6:        newRoot->left = root;
7:        return newRoot;
8:      }
10:      return root;
11:    }
12:
13:    void addOneRowImpl(TreeNode* node, int v, int level, int& d) {
14:      if(node == NULL) return;
15:
16:      if(level == d - 1) {
17:        TreeNode* left = node->left;
18:        TreeNode* right = node->right;
19:        node->left = new TreeNode(v);
20:        node->left->left = left;
21:        node->right = new TreeNode(v);
22:        node->right->right = right;
23:        return;
24:      }
25: