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