Google+ Followers

Monday, August 7, 2017

[Leetcode] Flatten 2D Vector, Solution

Implement an iterator to flatten a 2d vector.
For example,
Given 2d vector =
[
  [1,2],
  [3],
  [4,5,6]
]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].
Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

[Thoughts]
实现题,按层从左到右遍历。

[Code]
1:  class Vector2D {  
2:  public:  
3:    vector<vector<int>> data;  
4:    int x = 0;  
5:    int y = 0;  
6:    int total = 0;  
7:    int visited = 0;  
8:    Vector2D(vector<vector<int>>& vec2d) {  
9:      data = vec2d;  
10:      for(auto list : vec2d) {  
11:        total += list.size();  
12:      }  
13:    }  
14:    
15:    int next() {  
16:      while(data[x].size() == 0) {x++;}  
17:        
18:      int cur = data[x][y];  
19:      if(y+1 == data[x].size()) {  
20:        x = x+1;  
21:        y = 0;  
22:      } else {  
23:        y++;  
24:      }  
25:      visited ++;  
26:      return cur;  
27:    }  
28:    
29:    bool hasNext() {  
30:      if(visited < total) return true;  
31:        
32:      return false;  
33:    }  
34:  };  
35:    
36:  /**  
37:   * Your Vector2D object will be instantiated and called as such:  
38:   * Vector2D i(vec2d);  
39:   * while (i.hasNext()) cout << i.next();  
40:   */  






[Leetcode] Kth Smallest Element in a BST, Solution

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note: 
You may assume k is always valid, 1 ? k ? BST's total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

[Thoughts]
递归遍历二叉树,在遍历过程中算kth。


[Code]
1:    int kthSmallest(TreeNode* root, int k) {  
2:      int count = 0;  
3:        
4:      return kthSmallestImpl(root, count, k);  
5:        
6:    }  
7:      
8:    int kthSmallestImpl(TreeNode* root, int& count, int k) {  
9:      if(root == NULL) return -1;  
10:        
11:      int lr = kthSmallestImpl(root->left, count, k);  
12:      count++;  
13:      if(count == k) {  
14:        return root->val;  
15:      }  
16:        
17:      int rr = kthSmallestImpl(root->right, count, k);  
18:      return lr != -1 ? lr : rr;  
19:    }  

[Leetcode] Basic Calculator II, Solution

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +-*/ operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.

[Thoughts]
没有括号,简单了很多。实现看code

[Code]
1:    int calculate(string s) {  
2:      istringstream in(s+ "+");  
3:        
4:      int num, total = 0, n;  
5:      char op;  
6:      in>>num;  
7:      while(in>>op) {  
8:        if(op == '+' || op == '-'){  
9:          total += num;  
10:          in>>num;  
11:          num = op=='-'? -num:num;  
12:        } else {  
13:          in>>n;  
14:          if(op == '*') {  
15:            num *=n;  
16:          } else {  
17:            num /=n;  
18:          }  
19:        }  
20:      }  
21:      return total;  
22:    }  


[Leetcode] Maximal Square, Solution

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.


[Thoughts]
这是个DP问题,定义

DP[i, j] 是the length of max square,这个square的最右下角是 (i,j),那么

如果matrix[i][j] == 0, DP[i, j]也是0,因为square 不存在

如果matrix[i][j] == 1, 那么DP[i, j]就有如下三种可能



1)从DP[i-1, j]表述的square上加一行
2)从DP[i, j-1]表述的square上加一列
3)从DP[i-1, j-1]表述的square上加一行和一列

从三种可能中选出最小的那一个就是maximal square。

[Code]
1:    int maximalSquare(vector<vector<char>>& matrix) {  
2:      if(matrix.size() == 0) return 0;  
3:        
4:      int row = matrix.size();  
5:      int col = matrix[0].size();  
6:      vector<vector<int>> dp(row+1, vector<int>(col+1, 0));  
7:        
8:      int maxLen = 0;  
9:      for(int i =1; i<=row; i++) {  
10:        for(int j =1; j<= col; j++) {  
11:          if(matrix[i-1][j-1] == '1') {  
12:            dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])+1 ;  
13:            maxLen = max(maxLen, dp[i][j]);  
14:          }  
15:        }  
16:      }  
17:      return maxLen*maxLen;  
18:    }  


[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.
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] One Edit Distance, Solution

Given two strings S and T, determine if they are both one edit distance apart.

[Thoughts]
这是个简化版。只要考虑几种可能, 如果s.length == t.length,只要看看不相同的字符是否超过一个即可。如果s.length < t.length,看看在s中插入一个字符是否能解决问题。

[Code]
1:    bool isOneEditDistance(string s, string t) {  
2:      int lena = s.size();  
3:      int lenb = t.size();  
4:      if(lenb > lena) return isOneEditDistance(t, s);  
5:      if(lena - lenb > 1) return false;  
6:        
7:      int diff = 0;  
8:      for(int i =0, j = 0; i< s.size() && j< t.size() && diff < 2; i++, j++) {  
9:        if(s[i] != t[j]) {  
10:          diff++;  
11:          if(lena != lenb) t.insert(j, 1, s[i]);  
12:        }  
13:      }  
14:        
15:      if((lena != lenb) && diff <2) return true;  
16:      if((lena == lenb) && diff ==1) return true;  
17:      return false;  
18:    }  

[Leetcode] Min Stack, Solution

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.
[Thoughts]
这其实需要一个栈和数组的联合数据结构。数组用于存储数据,而栈用于记录当前最小值,用于服务getMin().

[Code]
1:  class MinStack {  
2:      
3:    stack<int> min_index;  
4:    vector<int> values;  
5:      
6:  public:  
7:      
8:      
9:    /** initialize your data structure here. */  
10:    MinStack() {  
11:        
12:    }  
13:      
14:    void push(int x) {  
15:      if(values.size() == 0) {  
16:        values.push_back(x);  
17:        min_index.push(values.size()-1);  
18:        return;  
19:      }  
20:        
21:      int cur_min = min_index.top();  
22:      values.push_back(x);  
23:      if(x > values[cur_min]) {  
24:        min_index.push(cur_min);  
25:      } else {  
26:        min_index.push(values.size()-1);  
27:      }  
28:        
29:    }  
30:      
31:    void pop() {  
32:      values.pop_back();  
33:      min_index.pop();  
34:    }  
35:      
36:    int top() {  
37:      return values[values.size()-1];  
38:    }  
39:      
40:    int getMin() {  
41:      return values[min_index.top()];  
42:    }  
43:  };  
44:    
45:  /**  
46:   * Your MinStack object will be instantiated and called as such:  
47:   * MinStack obj = new MinStack();  
48:   * obj.push(x);  
49:   * obj.pop();  
50:   * int param_3 = obj.top();  
51:   * int param_4 = obj.getMin();  
52:   */