水中的鱼

Sunday, August 9, 2020

Free download for "Introduction to Blockchain"

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

Download link： here. I wrote it in chinese, so only for chinese readers.

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:

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:

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

click to show more hints.

Hints:

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.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
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:    }