## Sunday, August 9, 2020

Share the pdf in case someone else interests in. Not for money, just for fun and my personal interests in this technology.

## 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]`.
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.
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]

[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]
``````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:      }
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[i, j] 是the length of max square,这个square的最右下角是 (i,j)，那么

1）从DP[i-1, j]表述的square上加一行
2）从DP[i, j-1]表述的square上加一列
3）从DP[i-1, j-1]表述的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]

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

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