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

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] 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:   */  

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

click to show spoilers.

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:        
14:      //add point  
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

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

[Thoughts]
贪心算法，遍历二维数组，每次只要发现一块land，就BFS其周边，把所有与之连接的land都变成0。BFS完即可island数加一。


[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);  
29:      return total;  
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]
一道实现题，本身并没有难度，处理好相关的merge即可。

[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]
双指针搜索。只不过因为数组的特殊排序，要从最右上角开始搜索，比如上例中的15.


[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]
一个一维的DP，比较简单。具体看code


[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)
addNum(2)
findMedian() -> 1.5
addNum(3) 
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();  
29:   * obj.addNum(num);  
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]
这里面比较有意思的是，只需要判断两个words是否有重复字符，并不需要知道具体重复的次数，所以用bitmap来做，很方便。

一个integer是32个bit，而英文字母只有26个，所以在第一轮循环中，先处理word，把26个字母是否出现映射到bitmap上。在第二轮循环中，对于bitmap不重复的words，计算长度的乘积，并保留最大值。


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

Follow up:
Could you do it without using any loop / recursion?

[Thoughts]
不断的用3来除，如果余数不为0，则判否。


[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]
双指针扫描。一个从头部，一个从尾部，发现vowel就swap。

[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]
题目里面其实提示复用已有的returned list，所以对数字做一遍统计，把缺失的数字放到returned list的尾部，在返回结果前，把原数组中的数字清除掉即可。


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

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

[Thoughts]
遍历二维数组，对于每一个land点，统计边数，最后统计周长即可。

[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题，很有意思。

假设K是range(i,j)中最后一个被戳破的气球，那么我们可以得到

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

在计算的过程中从底向上，len是1到n来计算。


[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]
遍历二叉搜索树，在遍历的过程中，对于遍历节点记录closest。


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

click to show clarification.

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]
这是比较琐碎的一道实现题。先把字符串中的多余空格清除掉，然后对于每一个word做reverse，最后再对整个string做一遍reverse即可。


[Code]
注意，这里remove multiple spaces的循环和swap words的循环，可以merge成一个loop，这里分成两个是为了保证可读性。

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