[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]
按照数组的结束数字排序，然后从左到右扫描。如果满足b<c的条件，则count+1.


[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]
从左到右遍历字符串，以每一个字符为中心，向左右两边扩展扫描，统计palindromic string。

另外，这题也可以用DP，类似于 http://fisherlei.blogspot.com/2012/12/leetcode-longest-palindromic-substring.html 。

[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 rootforming 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]
把字典转成hashmap，这样查询节省时间。这里用stringstream来读取子字符串，然后在子字符串中处理prefix，第一个被查到的就是最短的那个。

很简单的一道题。可说的东西不多。


[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:    }  

[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]
凡是这种decode的题，基本上都是用栈。当遇到左括号的时候，保留住当前的栈状态，当遇到右括号的时候，弹出当前栈状态，做一番处理。具体看code



[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]
是House Robber的扩展题（http://fisherlei.blogspot.com/2017/07/leetcode-house-robber-solution.html ），唯一的区别就是house 0 和house n-1相邻了。根据题目要求，不能抢劫相邻的房子，所以这个环把它拆开就两种可能：

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

对于#1和#2两种情况，都可以复用House Robber的代码， 最后比较一下这两种可能中，那个收入多即可。

[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:    }  

[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]
一个dp问题。对于任意一个房子，只有两种状态，rob 或 no_rob.

如果定义 rob[i] 为抢劫house i可获得的最大收益，而no_rob[i] 为不抢劫house i可获得的最大收益，递推关系式可表示为

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

如果以 house数组[2,1,1,2]为例，

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

那么最后的最大收益就是在rob 和no_rob中找个最大的，在此例中就是4


[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]
以题中示例为例子，看一下坐标的变化，如下图

在上升通道的时候， row = row -1, col = col +1
在下降通道的时候，row = row +1, col = col -1

当坐标变化超出数组范围的时候，要遵循以下原则调整：
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. 题目不要求保留原有付款关系。

所以，对图做个dfs即可。

[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:  }  

[Leetcode] Missing Ranges, Solution

Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], 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]

这题并不难，扫一遍数组，对于任意两个相邻的数字，看看他们是否连续，不连续的话生成一个range。

需要注意两点：
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:    
26:      if(end - start <= 2) return to_string(start+1);  
27:    
28:      return to_string(start+1) + "->" + to_string(end-1);  
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.

Follow up:
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[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]

首先分析一下什么样的数是最小的数。数总是有0~9的数字组成，高位的数字越小，这个数就越小。

所以，在对一个数做删除数字处理的时候，首先要从高位上把大的数字干掉，尽可能保留小的。

举个例子 num = "143219", k = 4

这个数字可以按照递增和递减分成三段 “1”， “4321”， “9”。递减子段上除了最后一个数字，其他的都可以被删除。

如果递减子段都处理完了，还没有删满k个，那就从最右边删（因为剩下的都是递增区间段了。）

[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]

对于每一个石头，设置一个set用来记录从左边跳过来的步数有哪几种，然后根据这个set再算，从当前石头上，可以调到右边哪些石头上。最后只要判断最后一个石头的set是否为空，就可判断青蛙能否跳过河。

[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]

对于一个三角形，只要满足两边之和大于第三边即可。这题可采用双指针遍历。

首先把数组排序一遍，保证其有序。

其次，遍历数组，每一个数字都作为第三条边的选择，然后在前面的数字中通过双指针来决定第一条边和第二条边。对于任何一个可能的三角形，比如下例，3 + 7 > 9，那么如果第二条边（7）不变，所以第一条边（3）之后的数字都可以是解。

[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:    }  

[Leetcode] Task Scheduler, Solution

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]

这其实是一道数学题。题目已经说了，相同task之间要间隔n个interval，这就意味着任意一个循环子区间的长度是N+1.

这道题就简单了，统计在task表里出现次数最多的task是哪一个，出现了多少次。这里假设是A和C，分别出现了m次。那么我们肯定知道会有 m-1个循环子区间，而每个子区间的长度是N+1（task不够就必须用idle来补上）。而最后一个区间只有A和C各出现一次。

[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:        
16:      return max((int)tasks.size(), ans);  
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 vas 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:      }  
9:      addOneRowImpl(root, v, 1, d);  
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:        
26:      addOneRowImpl(node->left, v, level+1, d);  
27:      addOneRowImpl(node->right, v, level+1, d);    
28:    }