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

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

[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:   */
``````

### [Leetcode] Find Peak Element, Solution

A peak element is an element that is greater than its neighbors.
Given an input array where `num[i] ≠ num[i+1]`, find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that `num[-1] = num[n] = -∞`.
For example, in array `[1, 2, 3, 1]`, 3 is a peak element and your function should return the index number 2.
Note:
Your solution should be in logarithmic complexity.

[Thoughts]

[Code]
``````1:    int findPeakElement(vector<int>& nums) {
2:      if(nums.size() <= 1) {
3:        return nums.size()-1;
4:      }
5:
6:      nums.insert(nums.begin(), INT_MIN);
7:      nums.push_back(INT_MIN);
8:
9:      int len = nums.size();
10:      int p = 1;
11:      for(; p<len; p++) {
12:        if(nums[p]>nums[p-1] && nums[p]>nums[p+1]) {
13:          break;
14:        }
15:      }
16:
17:      return p-1;
18:    }
``````

### [Leetcode] Fraction to Recurring Decimal, Solution

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

[Thoughts]

[Code]
``````1:    string fractionToDecimal(int num2, int den2) {
2:      if(num2 == 0) return "0";
3:      string result;
4:      if((num2>0) ^ (den2>0)) {
5:        result +='-';
6:      }
7:      long num = abs((long)num2);
8:      long den = abs((long)den2);
9:
10:      // process before point
11:      long div = num/den;
12:      result += to_string(div);
13:
15:      if(num % den != 0) {
16:        result +='.';
17:      } else {
18:        return result;
19:      }
20:
21:      //process after point
22:
23:      map<int, int> rem_index;
24:      long remind= num%den;
25:      while(remind!=0) {
26:        long res = remind*10/den;
27:
28:        if(rem_index.find(remind) == rem_index.end()) {
29:          result += to_string(res);
30:          rem_index[remind] = result.size()-1;
31:        } else {
32:          result.insert(rem_index[remind], 1, '(');
33:          result+=")";
34:          break;
35:        }
36:        remind = remind * 10;
37:        remind = remind% den;
38:
39:      }
40:      return result;
41:    }
``````

### [Leetcode] Number of Islands, Solution

Given a 2d grid map of `'1'`s (land) and `'0'`s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
```11110
11010
11000
00000```
Example 2:
```11000
11000
00100
00011```

[Thoughts]

[Code]
``````1:    int numIslands(vector<vector<char>>& grid) {
2:      int rows = grid.size();
3:      if(rows == 0) return 0;
4:      int cols = grid[0].size();
5:
6:      int islands = 0;
7:      for(int i =0; i< rows; i++) {
8:        for(int j= 0; j< cols; j++) {
9:          if(grid[i][j] == '0') continue;
10:          eliminateIsland(grid, i, j, rows, cols);
11:          islands++;
12:        }
13:      }
14:      return islands;
15:    }
16:
17:    void eliminateIsland(vector<vector<char>>& grid, int x, int y, int& rows, int& cols) {
18:      if(x<0 || x>=rows) return;
19:      if(y<0 || y>=cols) return;
20:      if(grid[x][y] == '0') return;
21:      grid[x][y] ='0';
22:
23:      eliminateIsland(grid, x, y+1, rows, cols);
24:      eliminateIsland(grid, x, y-1, rows, cols);
25:      eliminateIsland(grid, x+1, y, rows, cols);
26:      eliminateIsland(grid, x-1, y, rows, cols);
27:    }
``````

### [Leetcode] Basic Calculator, Solution

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open `(` and closing parentheses `)`, the plus `+` or minus sign `-`non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
```"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
```
Note: Do not use the `eval` built-in library function.

[Thoughts]

[Code]
``````1:    int calculate(string s) {
2:      stack<int> nums, ops;
3:      int num = 0;
4:      int total = 0;
5:      char pre_op = '+';
6:      for(char c : s) {
7:        if(isdigit(c)) {
8:          num = num* 10 + c-'0';
9:        } else {
10:          total += (pre_op == '+' ? num:-num);
11:          num = 0;
12:          if(c == '(') {
13:            nums.push(total);
14:            ops.push(pre_op);
15:            total = 0;
16:            pre_op = '+';
17:          } else if(c == ')') {
18:            char op = ops.top();
19:            int temp = nums.top();
20:            total = (op == '+' ? total:-total) + temp;
21:            ops.pop();
22:            nums.pop();
23:          } else if(c == '+' || c == '-') {
24:            pre_op = c;
25:          }
26:        }
27:      }
28:      total += (pre_op == '+' ? num:-num);
30:    }
``````

### [Leetcode] Summary Ranges, Solution

Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given `[0,1,2,4,5,7]`, return `["0->2","4->5","7"].`

[Thoughts]

[Code]
``````1:    vector<string> summaryRanges(vector<int>& nums) {
2:      vector<string> result;
3:      if(nums.size() <1) return result;
4:
5:      int start = 0, i =1;
6:      for(; i< nums.size(); i++){
7:        if(nums[i] - nums[i-1]==1) continue;
8:
9:        if(i-1 == start) {
10:          result.push_back(to_string(nums[start]));
11:        } else
12:          result.push_back(to_string(nums[start]) + "->" + to_string(nums[i-1]));
13:        start = i;
14:      }
15:
16:      if(i-1 == start) {
17:        result.push_back(to_string(nums[start]));
18:      } else
19:        result.push_back(to_string(nums[start]) + "->" + to_string(nums[i-1]));
20:      return result;
21:    }
``````

### [Leetcode] Search a 2D Matrix II, Solution

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
```[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
```
Given target = `5`, return `true`.
Given target = `20`, return `false`.

[Thoughts]

[Code]
``````1:    bool searchMatrix(vector<vector<int>>& matrix, int target) {
2:      int rows = matrix.size();
3:      if(rows == 0) return false;
4:      int cols = matrix[0].size();
5:
6:      int i = 0, j = cols-1;
7:      while(j>=0 && i< rows) {
8:        if(matrix[i][j] == target) return true;
9:
10:        if(matrix[i][j] < target) i++;
11:        else j--;
12:      }
13:      return false;
14:    }
``````

### [Leetcode] Perfect Squares, Solution

Given a positive integer n, find the least number of perfect square numbers (for example, `1, 4, 9, 16, ...`) which sum to n.
For example, given n = `12`, return `3` because `12 = 4 + 4 + 4`; given n = `13`, return `2` because `13 = 4 + 9`.

[Thoughts]

[Code]
``````1:    int numSquares(int n) {
2:
3:      vector<int> dp(n+1, 0);
4:      for(int i =1; i<= n; i++) {
5:
6:        int min_v = INT_MAX;
7:        for(int j = 1; j*j <= i; j++) {
8:          min_v = min(min_v, dp[i - j*j] +1);
9:        }
10:        dp[i] =min_v;
11:      }
12:
13:      return dp[n];
14:    }
``````

### [Leetcode] Find Median from Data Stream, Solution

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:
`[2,3,4]` , the median is `3`
`[2,3]`, the median is `(2 + 3) / 2 = 2.5`
Design a data structure that supports the following two operations:
• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.
For example:
```addNum(1)
findMedian() -> 1.5
findMedian() -> 2```

[Thoughts]

[Code]
``````1:  class MedianFinder {
2:  public:
3:    priority_queue<int> min_h;
4:    priority_queue<int, std::vector<int>, std::greater<int>> max_h;
5:    /** initialize your data structure here. */
6:    MedianFinder() {
7:
8:    }
9:
10:    void addNum(int num) {
11:      min_h.push(num);
12:      max_h.push(min_h.top());
13:      min_h.pop();
14:      if(min_h.size() < max_h.size()) {
15:        min_h.push(max_h.top());
16:        max_h.pop();
17:      }
18:    }
19:
20:    double findMedian() {
21:      if(min_h.size() > max_h.size()) return min_h.top();
22:      return (double)(min_h.top() + max_h.top())/2;
23:    }
24:  };
25:
26:  /**
27:   * Your MedianFinder object will be instantiated and called as such:
28:   * MedianFinder obj = new MedianFinder();
30:   * double param_2 = obj.findMedian();
31:   */
``````

### [Leetcode] Remove Duplicate Letters, Solution

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example:
Given `"bcabc"`
Return `"abc"`
Given `"cbacdcbc"`
Return `"acdb"`

[Thoughts]

[Code]
``````1:    string removeDuplicateLetters(string s) {
2:      vector<int> count(26, 0);
3:      vector<int> visited(26, 0);
4:
5:      for(char c : s) {
6:        count[c-'a']++;
7:      }
8:      string result= "";
9:      for(char c : s) {
10:        if(visited[c-'a'] == 1) {
11:          count[c-'a']--;
12:          continue;
13:        }
14:        while(result.size() > 0 && c < result.back() && count[result.back()-'a'] >0) {
15:          visited[result.back()-'a'] = 0;
16:          result.pop_back();
17:        }
18:        result += c;
19:        visited[c-'a'] = 1;
20:        count[c-'a']--;
21:      }
22:
23:      return result;
24:    }
``````

### [Leetcode] Maximum Product of Word Lengths, Solution

Given a string array `words`, find the maximum value of `length(word[i]) * length(word[j])` where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:
Given `["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]`
Return `16`
The two words can be `"abcw", "xtfn"`.
Example 2:
Given `["a", "ab", "abc", "d", "cd", "bcd", "abcd"]`
Return `4`
The two words can be `"ab", "cd"`.
Example 3:
Given `["a", "aa", "aaa", "aaaa"]`
Return `0`
No such pair of words.

[Thoughts]

[Code]

``````1:    int maxProduct(vector<string>& words) {
2:
3:      if(words.size() < 2) return 0;
4:      vector<int> counts(words.size(), 0);
5:
6:      for(int k = 0; k< words.size(); k++) {
7:        string word = words[k];
8:        int measure = 0;
9:        for(int i =0; i< word.size(); i++)
10:        {
11:          // set bitmap
12:          measure |= (1<< (word[i]-'a'));
13:        }
14:        counts[k] = measure;
15:      }
16:
17:      int max_v = 0;
18:      for(int i =0; i< words.size(); i++) {
19:        for(int j = i+1; j< words.size(); j++)
20:        {
21:          // use bitmap to check no common char
22:          if((counts[i] & counts[j]) ==0) {
23:            int product= words[i].length()* words[j].length();
24:            max_v = max(max_v, product);
25:          }
26:        }
27:      }
28:      return max_v;
29:    }
``````

### [Leetcode] Power of Three, Solution

Given an integer, write a function to determine if it is a power of three.
Could you do it without using any loop / recursion?

[Thoughts]

[Code]
``````1:    bool isPowerOfThree(int n) {
2:      if(n == 0) return false;
3:
4:      if(n == 1) return true;
5:
6:      return (n%3 ==0) && isPowerOfThree(n/3);
7:    }
``````

followup的问题，如果不用loop或recursion的话，一般都是指数学方法来处理，这里就不花时间了。

### [Leetcode] Reverse Vowels of a String, Solution

Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note:
The vowels does not include the letter "y".

[Thoughts]

[Code]
``````1:    string reverseVowels(string s) {
2:      set<char> vowels{'a', 'o', 'e', 'i', 'u', 'A', 'O', 'E', 'I', 'U'};
3:
4:      for(int i =0, j = s.size()-1; i< j; ) {
5:        if(vowels.find(s[i]) == vowels.end()) {
6:          i++;
7:          continue;
8:        }
9:
10:        if(vowels.find(s[j]) == vowels.end()) {
11:          j--;
12:          continue;
13:        }
14:
15:        swap(s[i], s[j]);
16:        i++;
17:        j--;
18:      }
19:
20:      return s;
21:    }
``````

### [Leetcode] Find All Numbers Disappeared in an Array, Solution

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
```Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]```
[Thoughts]

[Code]
``````1:    vector<int> findDisappearedNumbers(vector<int>& nums) {
2:      vector<int> result(nums.size(), 0);
3:
4:      for(int i =0; i< nums.size(); i++) {
5:        result[nums[i]-1] = 1;
6:      }
7:
8:      for(int i =0; i< nums.size(); i++) {
9:        if(result[i] == 0) {
10:          result.push_back(i+1);
11:        }
12:      }
13:
14:      result.erase(result.begin(), result.begin() + nums.size());
15:      return result;
16:    }
``````

### [Leetcode] Island Perimeter, Solution

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
Example:
```[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Explanation: The perimeter is the 16 yellow stripes in the image below:
```

[Thoughts]

[Code]
``````1:    int islandPerimeter(vector<vector<int>>& grid) {
2:
3:      int rows = grid.size();
4:      if(rows == 0) return 0;
5:      int cols = grid[0].size();
6:
7:      int periMeters = 0;
8:      for(int i =0; i< rows; i++) {
9:        for(int j =0; j< cols; j++) {
10:          if(grid[i][j] == 1) {
11:            periMeters += surWaters(grid, i, j);
12:          }
13:        }
14:      }
15:      return periMeters;
16:    }
17:
18:    int surWaters(vector<vector<int>>& grid, int x, int y) {
19:      int periM = 0;
20:      // x-1, y
21:      if(x-1< 0) periM++;
22:      else {
23:        periM += (1-grid[x-1][y]);
24:      }
25:
26:      //x+1, y
27:      if(x+1 > grid.size() -1) periM++;
28:      else periM += (1-grid[x+1][y]);
29:
30:      // x, y-1
31:      if(y-1 < 0) periM++;
32:      else periM += (1-grid[x][y-1]);
33:
34:      // x, y+1
35:      if(y+1 > grid[0].size() -1) periM++;
36:      else periM += (1-grid[x][y+1]);
37:
38:      return periM;
39:    }
``````

### [Leetcode] Burst Balloons, Solution

Given `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number on it represented by array `nums`. You are asked to burst all the balloons. If the you burst balloon `i` you will get `nums[left] * nums[i] * nums[right]` coins. Here `left` and `right` are adjacent indices of `i`. After the burst, the `left` and `right` then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:
(1) You may imagine `nums[-1] = nums[n] = 1`. They are not real therefore you can not burst them.
(2) 0 ≤ `n` ≤ 500, 0 ≤ `nums[i]` ≤ 100
Example:
Given `[3, 1, 5, 8]`
Return `167`
```    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167```

[Thoughts]
DP题，很有意思。

DP[i][j] = max( DP[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + DP[k+1][j])      i<k<j

[Code]
``````1:    int maxCoins(vector<int>& nums) {
2:
3:      int n = nums.size();
4:      // add boundary to simplify the corner case
5:      nums.insert(nums.begin(), 1);
6:      nums.push_back(1);
7:
8:      vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
9:
10:      for(int len = 1; len<=n; len++) {
11:        for(int left = 1; left<=n-len +1; left++) {
12:          int right = left + len -1;
13:          for(int k =left; k<=right; ++k) {
14:            // K is the Balloons destroyed in the last
15:            dp[left][right] = max(
16:              dp[left][right],
17:              nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right],
18:            );
19:          }
20:        }
21:      }
22:      return dp[1][n];
23:    }
``````

### [Leetcode] Closest Binary Search Tree Value, Solution

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.
[Thoughts]

[Code]
``````1:    int closestValue(TreeNode* root, double target) {
2:      double min = UINT_MAX;
3:      int closeVal = 0;
4:
5:      closest(root, target, min, closeVal);
6:      return closeVal;
7:    }
8:
9:    void closest(TreeNode* root, double target, double& min, int& closeVal) {
10:      if(root == NULL) return;
11:
12:      if(abs(target - root->val) < min) {
13:        closeVal = root->val;
14:        min = abs(target - root->val);
15:      }
16:
17:      if(root->val < target) {
18:        closest(root->right, target, min, closeVal);
19:      }else {
20:        closest(root->left, target, min, closeVal);
21:      }
22:    }
``````

### [Leetcode] Reverse Words in a String, Solution

Given an input string, reverse the string word by word.
For example,
Given s = "`the sky is blue`",
return "`blue is sky the`".
Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.
Clarification:
• What constitutes a word?
A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

[Thoughts]

[Code]

``````1:    void reverseWords(string &s) {
2:      int start = 0;
3:      int end = 0;
4:      string sn="";
5:
6:      // remove the multiple space
7:      for(int i =start; i< s.size();){
8:        if(s[i] == ' ') {
9:          sn.push_back(' ');
10:          while(i < s.size() && s[i] ==' ') {
11:            i++;
12:          }
13:        } else {
14:          sn.push_back(s[i]);
15:          i++;
16:        }
17:      }
18:      s = sn;
19:
20:      // swap the words
21:      while(end < s.size()) {
22:        while(end < s.size() && s[end] ==' ') {
23:          start ++;
24:          end++;
25:        }
26:
27:        while(end < s.size() && s[end] != ' ') end++;
28:
29:        swapW(s, start, end-1);
30:        start = end;
31:      }
32:
33:      swapW(s, 0, s.size()-1);
34:
35:      //remove the leading or trailing spaces
36:      start = s[0] == ' '? 1:0;
37:      end = s[s.size()-1] == ' '? s.size()-2: s.size()-1;
38:      s= s.substr(start, end-start +1);
39:    }
40:
41:    void swapW(string& s, int start, int end) {
42:      for(int i =start, j = end; i<j; i++, j--) {
43:        swap(s[i],s[j]);
44:      }
45:    }
``````