Google+ Followers

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]
一个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] Product of Array Except Self, Solution

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

[Thoughts]

这题是个细节题,可以分成三种情况:
  1. 数组中有一个以上的0出现, 比如 [1,2, 0, 0, 3, 4], 最后的结果肯定都是0: [0,0,0,0,0,0]
  2. 数组中有一个0出现,比如[1,2,0,3,4],按照题目的定义,最后的输出结果是[0,0,24,0,0]. 除了0的那一位是有值,其他位都是0
  3. 数组中没有0, 假设数组位[a0, a1, a2, ......], 其中所有数值的乘积为M, 那个数组的输出就是[M/a0, M/a1, M/a2.....].

[Code]
1:    vector<int> productExceptSelf(vector<int>& nums) {  
2:      int64_t product = 1;  
3:        
4:      int zeros = 0;  
5:      for(int i =0; i< nums.size(); i++) {  
6:        if(nums[i] == 0){  
7:          zeros++;  
8:          continue;  
9:        }   
10:        product *= nums[i];  
11:      }  
12:        
13:      vector<int> result;  
14:      for(int i =0; i< nums.size(); i++) {  
15:        if(zeros > 1) {  
16:          result.push_back(0);  
17:          continue;  
18:        } else if( zeros == 1){  
19:          if(nums[i] == 0) result.push_back(product);  
20:          else result.push_back(0);  
21:          continue;  
22:        }  
23:          
24:        result.push_back(product/nums[i]);  
25:      }  
26:        
27:      return result;  
28:    }  

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

这题并不难,扫一遍数组,对于任意两个相邻的数字,看看他们是否连续,不连续的话生成一个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:    }