[Leetcode] Course Schedule, Solution

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

[Thoughts]
首先，用一个hashmap来保存课程之间的dependence。然后做DFS检查课程中是否有环存在，如果有环，则不可能。


[Code]

1:    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {  
2:      unordered_map<int, vector<int>> deps(numCourses);  
3:        
4:      for(auto pair : prerequisites) {  
5:        deps[pair.first].push_back(pair.second);  
6:      }  
7:        
8:      vector<int> visited(numCourses, 0);  
9:      for(int i =0 ; i< numCourses; i++) {  
10:        if(isCycle(i, deps, visited)) return false;  
11:      }  
12:      return true;  
13:    }  
14:      
15:    bool isCycle(int start, unordered_map<int, vector<int>>& deps, vector<int>& visited) {  
16:      if(visited[start] == 1) return true;  
17:    
18:      visited[start] =1;  
19:    
20:      for(auto edge: deps[start]) {  
21:        if(isCycle(edge, deps, visited)) return true;  
22:          
23:      }  
24:      visited[start] =0;  
25:      return false;  
26:    }  

[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] Expression Add Operators, Solution

---

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or *between the digits so they evaluate to the target value.

Examples: 

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

[Thoughts]

这道题除了DFS，我还没想出更好的办法。需要注意的是如何处理*号。每当尝试用*号的时候，要注意处理上一次计算。比如第二个例子 “232”，当处理到2+3的时候，值是5，这时候对于下一个数字2，如果用*号，就得把上一次计算回滚，(5 - 3) + 3*2。

除此之外，没有难点。


[Code]

1:    vector<string> addOperators(string num, int target) {  
2:      vector<string> result;  
3:      if(num.size() == 0) return result;  
4:        
5:      nextStep(num, 0, target, 0, "", 0, result);  
6:      return result;  
7:    }  
8:      
9:    void nextStep(string& numStr, int cur_index, int& target, long value, string equation, long pre_num, vector<string>& result) {  
10:      if(value == target && cur_index == numStr.size()) {  
11:        result.push_back(equation);  
12:        return;  
13:      }  
14:        
15:      for(int i = 1; i< numStr.size() - cur_index +1; i++) {  
16:        if(i >1 && numStr[cur_index] == '0') break;  
17:        string temp = numStr.substr(cur_index, i);  
18:        long num = stol(temp);  
19:          
20:        if(cur_index == 0){  
21:          nextStep(numStr, cur_index +i, target, num, temp, num, result);  
22:          continue;  
23:        }  
24:          
25:        nextStep(numStr, cur_index +i, target, value + num, equation + '+' + temp, num, result);  
26:        nextStep(numStr, cur_index +i, target, value - num, equation + '-' + temp, -num, result);  
27:        nextStep(numStr, cur_index +i, target, value - pre_num + pre_num * num, equation + '*' + temp, pre_num * num, result);  
28:      }  
29:    }  

[Leetcode] Binary Tree Paths, Solution

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

[Thought]

这个主要就是实现题。对树进行深度遍历，在遍历的过程中保存访问节点，当遍历到叶节点的时候，打印出来路径即可。

[Code]

1:  class Solution {  
2:  public:  
3:    vector<string> binaryTreePaths(TreeNode* root) {  
4:      vector<string> paths;  
5:      vector<int> nodes;  
6:      getAllPaths(root, nodes, paths);       
7:      return paths;  
8:    }  
9:    void getAllPaths(TreeNode* node, vector<int>& nodes,vector<string>& paths) {  
10:      if(node == NULL) {  
11:        return;  
12:      }  
13:      if(node->left== NULL && node->right == NULL) {  
14:        stringstream ss;  
15:        for(int i =0; i< nodes.size(); i++) {  
16:          ss << nodes[i] << "->";  
17:        }  
18:        ss << node->val;  
19:        paths.push_back(ss.str());  
20:        return;  
21:      }  
22:      nodes.push_back(node->val);  
23:      getAllPaths(node->left, nodes, paths);  
24:      getAllPaths(node->right, nodes, paths);  
25:      nodes.pop_back();  
26:    }  
27:  };  

Github: https://github.com/codingtmd/leetcode/blob/master/src/Binary%20Tree%20Paths.cpp

[LeetCode] Unique Binary Search Trees II, Solution

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem


[Thoughts]
分析请参看http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html
思路是一致的。划分左右子树，然后递归构造。

[Code]

1:       vector<TreeNode *> generateTrees(int n) {   
2:            if(n ==0) return generate(1,0);  
3:            return generate(1, n);  
4:       }       
5:       vector<TreeNode *> generate(int start, int end)  
6:       {  
7:            vector<TreeNode *> subTree;  
8:            if(start>end)  
9:            {  
10:                 subTree.push_back(NULL);  
11:                 return subTree;  
12:            }  
13:            for(int i =start; i<=end; i++)  
14:            {  
15:                 vector<TreeNode*> leftSubs = generate(start, i-1);  
16:                 vector<TreeNode*> rightSubs = generate(i+1, end);  
17:                 for(int j = 0; j< leftSubs.size(); j++)  
18:                 {  
19:                      for(int k=0; k<rightSubs.size(); k++)  
20:                      {  
21:                           TreeNode *node = new TreeNode(i);  
22:                           node->left = leftSubs[j];  
23:                           node->right = rightSubs[k];  
24:                           subTree.push_back(node);  
25:                      }  
26:                 }  
27:            }  
28:            return subTree;  
29:       }      

[Note]
写完第一个版本之后，立即发现一个严重的问题。上面的function存在大量的对象拷贝，因为所有变量都是在栈上开辟，所以返回值的时候都需要通过拷贝构造函数来重构vector，面试中这个疏忽是不应该的。

修改版，这里应该用指针及堆来存储变量。

1:       vector<TreeNode *> generateTrees(int n) {   
2:            if(n ==0) return *generate(1,0);  
3:            return *generate(1, n);  
4:       }  
5:       vector<TreeNode *>* generate(int start, int end)  
6:       {  
7:            vector<TreeNode *> *subTree = new vector<TreeNode*>();  
8:            if(start>end)  
9:            {  
10:                 subTree->push_back(NULL);  
11:                 return subTree;  
12:            }  
13:            for(int i =start; i<=end; i++)  
14:            {  
15:                 vector<TreeNode*> *leftSubs = generate(start, i-1);  
16:                 vector<TreeNode*> *rightSubs = generate(i+1, end);  
17:                 for(int j = 0; j< leftSubs->size(); j++)  
18:                 {  
19:                      for(int k=0; k<rightSubs->size(); k++)  
20:                      {  
21:                           TreeNode *node = new TreeNode(i);  
22:                           node->left = (*leftSubs)[j];  
23:                           node->right = (*rightSubs)[k];  
24:                           subTree->push_back(node);  
25:                      }  
26:                 }  
27:            }  
28:            return subTree;  
29:       }      

[LeetCode] Palindrome Partitioning, Solution

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

» Solve this problem

[Thoughts]
这种需要输出所有结果的基本上都是DFS的解法。实现如下。

[Code]

1:       vector<vector<string>> partition(string s) {  
2:            vector<vector<string>> result;  
3:            vector<string> output;  
4:            DFS(s, 0, output, result);  
5:            return result;  
6:       }  
7:       void DFS(string &s, int start, vector<string>& output, vector<vector<string>> &result)  
8:       {      
9:            if(start == s.size())  
10:            {  
11:                 result.push_back(output);  
12:                 return;  
13:            }  
14:            for(int i = start; i< s.size(); i++)  
15:            {    
16:                 if(isPalindrome(s, start, i))  
17:                 {  
18:                      output.push_back(s.substr(start, i-start+1));  
19:                      DFS(s, i+1, output, result);  
20:                      output.pop_back();  
21:                 }  
22:            }  
23:       }  
24:       bool isPalindrome(string &s, int start, int end)  
25:       {  
26:            while(start< end)  
27:            {  
28:                 if(s[start] != s[end])  
29:                 return false;  
30:                 start++; end--;  
31:            }  
32:            return true;  
33:       }  

[LeetCode] Permutations II 解题报告

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

» Solve this problem

[解题思路]
跟 Permutations的解法一样，就是要考虑“去重”。先对数组进行排序，这样在DFS的时候，可以先判断前面的一个数是否和自己相等，相等的时候则前面的数必须使用了，自己才能使用，这样就不会产生重复的排列了。

与Permitations的code相比，只加了3行，Line 8，23，24。

[Code]

1:    vector<vector<int> > permuteUnique(vector<int> &num) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<vector<int> > coll;  
5:      vector<int> solution;  
6:      if(num.size() ==0) return coll;  
7:      vector<int> visited(num.size(), 0);  
8:      sort(num.begin(), num.end());  
9:      GeneratePermute(num, 0, visited, solution, coll);  
10:      return coll;  
11:    }  
12:    void GeneratePermute(vector<int> & num, int step, vector<int>& visited, vector<int>& solution, vector<vector<int> >& coll)  
13:    {  
14:      if(step == num.size())  
15:      {  
16:        coll.push_back(solution);  
17:        return;  
18:      }  
19:      for(int i =0; i< num.size(); i++)  
20:      {  
21:        if(visited[i] == 0)  
22:        {  
23:          if(i>0 && num[i] == num[i-1] && visited[i-1] ==0)  
24:            continue;  
25:          visited[i] = 1;  
26:          solution.push_back(num[i]);  
27:          GeneratePermute(num, step+1, visited, solution, coll);  
28:          solution.pop_back();  
29:          visited[i] =0;  
30:        }  
31:      }  
32:    }  

[Note]
Line 23: Don't miss “&& visited[i-1] ==0”. Or, the inner recursion will skip using duplicate number.