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

[Leetcode] Meeting Rooms II, Solution

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

[Thoughts]
简单的说，把每一个interval铺到时间轴上，统计每个开始点、结束点的room number，然后再做一遍统计，看看在各个时间点上，最大的room number是什么。


[Code]

1:    int minMeetingRooms(vector<Interval>& intervals) {  
2:      map<int, int> deltas;  
3:      for(auto interval : intervals) {  
4:        deltas[interval.start]++;  
5:        deltas[interval.end]--;  
6:      }  
7:        
8:      int max_room = 0, rooms = 0;  
9:      for(auto delta : deltas) {  
10:        rooms += delta.second;  
11:        max_room = max(max_room, rooms);  
12:      }  
13:      return max_room;  
14:    }  

[Leetcode] Game of Life, Solution

According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up: 

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

[Thoughts]
这是个模拟题。把整个过程分成两步，第一步先计算所有cell的当前值，然后再计算下一步状态。


[Code]

1:    void gameOfLife(vector<vector<int>>& board) {  
2:      int raws = board.size();  
3:      if(raws == 0) return;  
4:      int columns = board[0].size();  
5:        
6:      // calculate the neighbors first  
7:      for(int i =0; i< raws; i++) {  
8:        for(int j = 0; j< columns; j++) {  
9:          int neighbors = 0;  
10:          // 3X3 neighbors  
11:          for(int k = i-1; k<= i+1; k++) {  
12:            if(k<0 || k>raws-1) continue;  
13:            for(int l = j-1; l<=j+1; l++) {  
14:              if(l<0 || l> columns -1) continue;  
15:              if(k ==i && l == j) continue;  
16:              neighbors+= board[k][l]%10;  
17:            }  
18:          }  
19:            
20:          board[i][j] = neighbors*10 + board[i][j];  
21:        }    
22:      }  
23:    
24:      // decide current value  
25:      for(int i =0; i< raws; i++) {  
26:        for(int j = 0; j< columns; j++) {  
27:          int neighbors = board[i][j] /10;  
28:          int cur = board[i][j] %10;  
29:          if(cur == 1) {  
30:            if(neighbors < 2 || neighbors>3) {  
31:              board[i][j] = 0;  
32:              continue;  
33:            }  
34:          } else {  
35:            if(neighbors ==3){   
36:              board[i][j] = 1;  
37:              continue;  
38:            }  
39:          }  
40:          board[i][j] = cur;  
41:        }    
42:      }  
43:    }  

[Leetcode] Diagonal Traverse, Solution

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

Note:

1. The total number of elements of the given matrix will not exceed 10,000.

[Thoughts]
以题中示例为例子，看一下坐标的变化，如下图

在上升通道的时候， row = row -1, col = col +1
在下降通道的时候，row = row +1, col = col -1

当坐标变化超出数组范围的时候，要遵循以下原则调整：
1. 如果row < 0, row = 0, 变换通道
2. 如果col < 0, col = 0, 变换通道
3. 如果 col > N, col = N-1, row = row +2;
4. 如果 row > M, row = M-1. col = col +2;

[Code]

1:    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {  
2:      if(matrix.size() == 0 || matrix[0].size() == 0) return {};  
3:        
4:      vector<int> result;  
5:        
6:      vector<pair<int, int>> move_delta{{-1, 1}, {1, -1}};  
7:        
8:      int rows = matrix.size(), cols = matrix[0].size();  
9:      int row = 0, col = 0, m = 0;  
10:      for(int i = 0; i< rows * cols; i++) {  
11:        result.push_back(matrix[row][col]);  
12:        row += move_delta[m].first;  
13:        col += move_delta[m].second;  
14:          
15:        if(row >= rows) {  
16:          row = rows-1;  
17:          col = col +2;  
18:          m = 1-m;  
19:        }  
20:          
21:        if(col >= cols) {  
22:          col = cols -1;  
23:          row = row + 2;  
24:          m = 1-m;  
25:        }  
26:          
27:        if(row < 0) {  
28:          row = 0;  
29:          m = 1-m;  
30:        }  
31:          
32:        if(col < 0) {  
33:          col = 0;  
34:          m = 1-m;  
35:        }  
36:      }  
37:      return result;  
38:    }  

[Leetcode] Frog Jump, Solution

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

• The number of stones is ≥ 2 and is < 1,100.
• Each stone's position will be a non-negative integer < 231.
• The first stone's position is always 0.

Example 1:

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

[Thoughts]

对于每一个石头，设置一个set用来记录从左边跳过来的步数有哪几种，然后根据这个set再算，从当前石头上，可以调到右边哪些石头上。最后只要判断最后一个石头的set是否为空，就可判断青蛙能否跳过河。

[Code]

1:    bool canCross(vector<int>& stones) {  
2:      map<int, set<int>> jumps;  
3:        
4:      for(int i =0; i< stones.size(); i++) {  
5:        jumps[stones[i]] = {};  
6:      }  
7:        
8:      jumps[0].insert(0);  
9:        
10:      for(int i =0; i< stones.size()-1; i++) {  
11:        int index = stones[i];  
12:        if(jumps[index].size() == 0) continue;  
13:        for(auto step : jumps[index]) {  
14:          for(int j = step-1; j<= step+1; j++) {  
15:            if(j<0) continue;  
16:            if(jumps.find(index+j) != jumps.end())  
17:              jumps[index+j].insert(j);  
18:          }  
19:        }  
20:      }  
21:        
22:      return jumps[stones[stones.size()-1]].size() != 0;  
23:    }  

[Leetcode] Ternary Expression Parser, Solution

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Note:

1. The length of the given string is ≤ 10000.
2. Each number will contain only one digit.
3. The conditional expressions group right-to-left (as usual in most languages).
4. The condition will always be either T or F. That is, the condition will never be a digit.
5. The result of the expression will always evaluate to either a digit 0-9, T or F.

Example 1:

Input: "T?2:3"

Output: "2"

Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"

Example 3:

Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"

[Thoughts]

从右往左扫，发现？号就处理掉，最后的结果就是。


[Code]

1:    string parseTernary(string expression) {  
2:      int len = expression.size();  
3:        
4:      if(len == 0) return expression;  
5:        
6:      for(int i = len-1; i>=0; i--) {  
7:        if(expression[i] != '?') continue;  
8:          
9:        int index = i;  
10:        char result;  
11:        if(expression[index-1] == 'T'){  
12:          result = expression[index+1];  
13:        }else {  
14:          result = expression[index+3];  
15:        }  
16:          
17:        expression.erase(index -1, 5);  
18:        expression.insert(index-1, 1, result);  
19:      }  
20:      return expression;  
21:    }  

[LeetCode] Binary Tree Preorder Traversal, Solution

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
[Thoughts]
PreOrder:
1. visit node
2. visit node->left
3. visit node->right
对于递归的解法很清晰，
function preorder(root)

if root == NULL return;
print root;
preoder(node->left);
preOrder(node->right);

将该递归函数转换成非递归的话，一般都要借助于栈。
 
[Code]

1:  vector<int> preorderTraversal(TreeNode *root) {  
2:       stack<TreeNode*> tStack;  
3:       vector<int> result;  
4:       while(tStack.size()>0 || root != NULL)  
5:       {  
6:            if(root != NULL)  
7:            {  
8:                 result.push_back(root->val);  
9:                 if(root->right !=NULL)  
10:                 tStack.push(root->right);  
11:                 root = root->left;  
12:            }  
13:            else  
14:            {  
15:                 root = tStack.top();  
16:                 tStack.pop();  
17:            }  
18:       }  
19:       return result;  
20:  }  

Update 08/20/2014. Another way to use stack

1:       vector<int> preorderTraversal(TreeNode *root) {  
2:            stack<TreeNode*> stack;  
3:            vector<int> result;  
4:            TreeNode* cur = root;  
5:            while(cur != NULL || stack.size() != 0)  
6:            {  
7:                 while(cur != NULL)  
8:                 {  
9:                      result.push_back(cur->val);  
10:                      stack.push(cur);  
11:                      cur = cur->left;  
12:                 }  
13:                 cur = stack.top();  
14:                 stack.pop();  
15:                 cur = cur->right;  
16:            }  
17:            return result;  
18:       }  

[LeetCode] Linked List Cycle, Solution

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

 

[Thoughts]

设定两个指针，一个每次走一步，一个每次走两步，如果链表上有环的话，两个指针必定能相遇。否则，则无环

[Code]

 1     bool hasCycle(ListNode *head) {
 2         if(head == NULL) return false;
 3         ListNode* first = head;
 4         ListNode* second = head->next;
 5         
 6         while(first != NULL && second != NULL)
 7         {
 8             if(first == second) return true;
 9             first = first->next;
10             second = second->next;
11             if(second == NULL)
12                 return false;
13             second = second->next;
14         }
15         return false;
16     }

[LeetCode] Spiral Matrix II, Solution

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

» Solve this problem

[Thoughts]
与Spriral Matrix（http://fisherlei.blogspot.com/2013/01/leetcode-spiral-matrix.html）类似，区别在于一个用递归来剥皮，一个用递归来构造。Code可以复用。

[Code]
红色部分为改动部分。可以看出来，与Spriral Matrix的code相比，改动非常小。

1:       vector<vector<int> > generateMatrix(int n) {  
2:            vector<vector<int>> matrix(n);  
3:            for(int i =0; i< n; i++)  
4:            {  
5:                 matrix[i].resize(n);  
6:            }  
7:            generate_order(matrix, 0, n, 0, n, 1);            
8:            return matrix;  
9:       }  
10:       void generate_order(   
11:       vector<vector<int> > &matrix,   
12:       int row_s, int row_len,   
13:       int col_s, int col_len,      
14:       int val)   
15:       {   
16:            if(row_len<=0 || col_len <=0) return;   
17:            if(row_len ==1)   
18:            {   
19:                 for(int i =col_s; i< col_s+col_len; i++)   
20:                     matrix[row_s][i] = val++;       
21:                 return;   
22:            }   
23:            if(col_len ==1)   
24:            {   
25:                 for(int i =row_s; i<row_s + row_len; i++)   
26:                     matrix[i][col_s] = val++;       
27:                 return;   
28:            }   
29:            for(int i =col_s; i<col_s+col_len-1; i++) //up  
30:                 matrix[row_s][i] = val++;   
31:            for(int i =row_s; i<row_s+row_len-1; i++)  //right  
32:                 matrix[i][col_s+col_len-1] = val++;  
33:            for(int i =col_s; i<col_s+col_len-1; i++) //bottom  
34:                 matrix[row_s+row_len-1][2*col_s+ col_len-1 -i] = val++;  
35:            for(int i =row_s; i<row_s+row_len-1; i++) //left  
36:                 matrix[2*row_s+row_len-1-i][col_s] = val++;  
37:            generate_order(matrix, row_s+1, row_len-2, col_s+1, col_len-2, val);   
38:       }  

[LeetCode] Merge Intervals, Solution

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

» Solve this problem

[Thoughts]
复用一下Insert Intervals的解法即可，http://fisherlei.blogspot.com/2012/12/leetcode-insert-interval.html
创建一个新的interval集合，然后每次从旧的里面取一个interval出来，然后插入到新的集合中。

[Code]
黄色高亮部分是复用的Code.

1:       vector<Interval> merge(vector<Interval> &intervals) {            
2:            vector<Interval> result;  
3:            for(int i =0; i< intervals.size(); i++)  
4:            {  
5:                 insert(result, intervals[i]);  
6:            }  
7:            return result;  
8:       }  
9:       void insert(vector<Interval> &intervals, Interval newInterval) {        
10:            vector<Interval>::iterator it = intervals.begin();   
11:            while(it!= intervals.end())   
12:            {   
13:                 if(newInterval.end<it->start)   
14:                 {   
15:                      intervals.insert(it, newInterval);   
16:                      return;   
17:                 }   
18:                 else if(newInterval.start > it->end)   
19:                 {   
20:                      it++;   
21:                      continue;   
22:                 }   
23:                 else   
24:                 {   
25:                      newInterval.start = min(newInterval.start, it->start);   
26:                      newInterval.end = max(newInterval.end, it->end);   
27:                      it =intervals.erase(it);             
28:                 }           
29:            }   
30:            intervals.insert(intervals.end(), newInterval);    
31:       }   

[LeetCode] Regular Expression Matching, Solution

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true

» Solve this problem

[Thoughts]
与Wildcard Maching同一题。
http://fisherlei.blogspot.com/2013/01/leetcode-wildcard-matching.html

[LeetCode] Longest Valid Parentheses, Solution

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

» Solve this problem

[Thoughts]
维护一个栈，每次维护上一个可能的左边际。


[Code]

1:       int longestValidParentheses(string s) {  
2:            const char* str = s.c_str();  
3:            int nMax=0;  
4:            const char *p = str;  
5:            vector<const char*> sta;  
6:            while(*p !='\0')  
7:            {  
8:                 if(*p == '(')  
9:                 {  
10:                      sta.push_back(p);                      
11:                 }  
12:                 else  
13:                 {  
14:                      if(!sta.empty() && *sta.back()=='(')  
15:                      {  
16:                           sta.pop_back();  
17:                           nMax = max(nMax, p-(sta.empty()?str-1:sta.back()));  
18:                      }  
19:                      else  
20:                      {  
21:                           sta.push_back(p);  
22:                      }  
23:                 }  
24:                 p++;  
25:            }  
26:            return nMax;  
27:       }  

[Yahoo] Cloest palindrome number, Solution

Given an integer, print the closest number to it that is a palindrome - eg, the number "1224" would return "1221".

[Thoughts]

pseudo code: (with two examples in parentheses)

- Convert the number into string. (1224, 39999)


- take half of the string. ( "12", "399" )


- copy first half to second half in reverse order (take care of no of chars)
  ( "12" -> "1221", "399" -> "39993" )


- convert to number and measure the abs. difference with original number - diff1
  ( |1221 - 1224| = 3, |39993-39999| = 6)


- add 1 to half string and now copy first half to second half in reverse order
  ( 12+1 = 13, 399 + 1 = 400, 13-> 1331, 400->40004)


- convert to number and measure the abs. difference with original number - diff2
  ( |1331-1224| = 107, |40004-39999| = 5 )


- if diff1<diff2 return first number else return second number
  ( 1221, 40004)

[LeetCode] Decode Ways, Solution

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

» Solve this problem

[Thoughts]

Similar as "[LeetCode] Climbing Stairs, Solution". DP. Just add some logic to compare character.

Transformation function as:
Count[i] = Count[i-1]  if S[i-1] is a valid char
       or   = Count[i-1]+ Count[i-2]  if S[i-1] and S[i-2] together is still a valid char.

[Code]

1:    int numDecodings(string s) {  
2:      if(s.empty() || s[0] =='0') return 0;      
3:      if(s.size() ==1) return check(s[0]);  
4:      int fn=0, fn_1=0, fn_2=1;      
5:      fn_1 = (check(s[0]) * check(s[1]))+check(s[0], s[1]);       
6:      for(int i=2; i< s.size(); i++)  
7:      {    
8:        if(check(s[i])) fn+= fn_1;         
9:        if(check(s[i-1], s[i])) fn+=fn_2;  
10:        if(fn ==0)   
11:          return 0;  
12:        fn_2 = fn_1;  
13:        fn_1 = fn;  
14:        fn=0;     
15:      }  
16:      return fn_1;  
17:    }  
18:    int check(char one)   
19:    {  
20:      return (one != '0') ? 1 : 0;      
21:    }  
22:    int check(char one, char two)  
23:    {  
24:      return (one == '1' || (one == '2' && two <= '6'))  
25:      ? 1 : 0;      
26:    }