[LeetCode] Search a 2D Matrix, 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 from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

» Solve this problem

[Thoughts]
做两次二分就好了，首先二分第一列，找出target所在的行，然后二分该行。

[Code]

1:       bool searchMatrix(vector<vector<int> > &matrix, int target) {  
2:            int row = matrix.size();  
3:            if(row ==0) return false;  
4:            int col = matrix[0].size();  
5:            if(col ==0) return false;      
6:            if(target< matrix[0][0]) return false;  
7:            int start = 0, end = row-1;  
8:            while(start<= end)  
9:            {  
10:                 int mid = (start+end)/2;  
11:                 if(matrix[mid][0] == target)  
12:                      return true;  
13:                 else if(matrix[mid][0] < target)  
14:                      start = mid+1;  
15:                 else  
16:                      end = mid-1;  
17:            }  
18:            int targetRow = end;  
19:            start =0;  
20:            end = col-1;  
21:            while(start <=end)  
22:            {  
23:                 int mid = (start+end)/2;  
24:                 if(matrix[targetRow][mid] == target)  
25:                      return true;  
26:                 else if(matrix[targetRow][mid] < target)  
27:                      start = mid+1;  
28:                 else  
29:                      end = mid-1;  
30:            }  
31:            return false;  
32:       }  

注意，
二分的条件应该是（start<=end）， 而不是（start<end）。

[LeetCode] Merge Two Sorted Lists, Solution

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
» Solve this problem

[Thoughts]
简单的实现，也没什么可说的。

[Code]

1:    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
2:      if(l1 == NULL) return l2;  
3:      if(l2 == NULL) return l1;  
4:      ListNode *head = new ListNode(-1);  
5:      ListNode *p = head;  
6:      while(l1 != NULL && l2!=NULL)  
7:      {  
8:          if(l1->val < l2->val)  
9:          {  
10:             p->next = l1;  
11:             l1= l1->next;  
12:          }  
13:          else  
14:          {  
15:             p->next = l2;  
16:             l2 = l2->next;  
17:          }  
18:          p = p->next;  
19:      }  
20:      if(l1 != NULL)  
21:          p->next = l1;  
22:      if(l2 != NULL)  
23:          p->next = l2;  
24:      p = head->next;  
25:      delete head;  
26:      return p;      
27:    }  

Update 04/13/13 refactor code for succinct

1:       ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
2:            ListNode* head = new ListNode(-1);  
3:            ListNode* p = head;  
4:            while(l1!=NULL || l2!= NULL)  
5:            {  
6:                 int val1 = l1==NULL?INT_MAX:l1->val;  
7:                 int val2 = l2==NULL? INT_MAX:l2->val;  
8:                 if(val1<=val2)  
9:                 {  
10:                      p->next = l1;          
11:                      l1=l1->next;  
12:                 }  
13:                 else  
14:                 {  
15:                      p->next = l2;  
16:                      l2 = l2->next;  
17:                 }  
18:                 p= p->next;  
19:            }  
20:            p = head->next;  
21:            delete head;  
22:            return p;  
23:       }  

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

[LeetCode] Two Sum, Solution

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

» Solve this problem

[Thoughts]
两种解法。
解法一， hash
从左往右扫描一遍，然后将数及坐标，存到map中。然后再扫描一遍即可。时间复杂度O(n)

解法二，双指针扫描
将数组排序，然后双指针从前后往中间扫描。时间复杂度O(n*lgn)。因为是要求返回原数组的下标，所以在排序的时候还得有额外的数组来存储下标信息， 也挺麻烦。

解法三，暴力搜索
这个倒是最省事的。时间复杂度O(n*n)

解法一实现如下：

1:    vector<int> twoSum(vector<int> &numbers, int target) {  
2:      map<int, int> mapping;  
3:      vector<int> result;  
4:      for(int i =0; i< numbers.size(); i++)  
5:      {  
6:        mapping[numbers[i]]=i;  
7:      }  
8:      for(int i =0; i< numbers.size(); i++)  
9:      {  
10:        int searched = target - numbers[i];  
11:        if(mapping.find(searched) != mapping.end())  
12:        {  
13:          result.push_back(i+1);  
14:          result.push_back(mapping[searched]+1);  
15:          break;  
16:        }  
17:      }  
18:      return result;  
19:    }  

解法二

1:       struct Node  
2:       {  
3:            int val;  
4:            int index;      
5:            Node(int pVal, int pIndex):val(pVal), index(pIndex){}  
6:       };  
7:       static bool compare(const Node &left, const Node &right)  
8:       {  
9:            return left.val < right.val;  
10:       }  
11:       vector<int> twoSum(vector<int> &numbers, int target) {  
12:            vector<Node> elements;  
13:            for(int i =0; i< numbers.size(); i++)  
14:            {  
15:                 elements.push_back(Node(numbers[i], i));  
16:            }  
17:            std::sort(elements.begin(), elements.end(), compare);  
18:            int start = 0, end = numbers.size()-1;  
19:            vector<int> result;  
20:            while(start < end)  
21:            {  
22:                 int sum = elements[start].val + elements[end].val;  
23:                 if(sum == target)  
24:                 {  
25:                      result.push_back(elements[start].index+1);  
26:                      if(elements[start].index < elements[end].index)  
27:                           result.push_back(elements[end].index+1);  
28:                      else  
29:                           result.insert(result.begin(),elements[end].index+1);  
30:                      break;  
31:                 }  
32:                 else if(sum > target)  
33:                      end--;  
34:                 else  
35:                      start++;                 
36:            }  
37:            return result;  
38:       }  

解法三，两个循环嵌套搜索，不写了。

[LeetCode] Palindrome Partitioning II, Solution

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

» Solve this problem

[Thoughts]
凡是求最优解的，一般都是走DP的路线。这一题也不例外。首先求dp函数，

定义函数
D[i,n] = 区间[i,n]之间最小的cut数，n为字符串长度

 a   b   a   b   b   b   a   b   b   a   b   a
                     i                                  n
如果现在求[i,n]之间的最优解？应该是多少？简单看一看，至少有下面一个解


 a   b   a   b   b   b   a   b   b   a   b   a
                     i                   j   j+1     n

此时  D[i,n] = min(D[i, j] + D[j+1,n])  i<=j <n。这是个二维的函数，实际写代码时维护比较麻烦。所以要转换成一维DP。如果每次，从i往右扫描，每找到一个回文就算一次DP的话，就可以转换为
D[i] = 区间[i,n]之间最小的cut数，n为字符串长度， 则,

D[i] = min(1+D[j+1] )    i<=j <n

有个转移函数之后，一个问题出现了，就是如何判断[i,j]是否是回文？每次都从i到j比较一遍？太浪费了，这里也是一个DP问题。
定义函数
P[i][j] = true if [i,j]为回文

那么
P[i][j] = str[i] == str[j] && P[i+1][j-1];

基于以上分析，实现如下：

1:       int minCut(string s) {  
2:            int len = s.size();  
3:            int D[len+1];  
4:            bool P[len][len];  
5:            //the worst case is cutting by each char  
6:            for(int i = 0; i <= len; i++)   
7:            D[i] = len-i;  
8:            for(int i = 0; i < len; i++)  
9:            for(int j = 0; j < len; j++)  
10:            P[i][j] = false;  
11:            for(int i = len-1; i >= 0; i--){  
12:                 for(int j = i; j < len; j++){  
13:                      if(s[i] == s[j] && (j-i<2 || P[i+1][j-1])){  
14:                           P[i][j] = true;  
15:                           D[i] = min(D[i],D[j+1]+1);  
16:                      }  
17:                 }  
18:            }  
19:            return D[0]-1;  
20:       }  

或者可以考虑使用回溯+剪枝，比如：

1:    int minCut(string s) {  
2:      int min = INT_MAX;  
3:      DFS(s, 0, 0, min);  
4:      return min;  
5:    }  
6:    void DFS(string &s, int start, int depth, int& min)  
7:    {     
8:      if(start == s.size())  
9:      {  
10:        if(min> depth-1)  
11:          min = depth-1;  
12:        return;  
13:      }  
14:      for(int i = s.size()-1; i>=start; i--)  //find the biggest palindrome first
15:      {  
16:        if(isPalindrome(s, start, i))  
17:        {        
18:          DFS(s, i+1, depth+1, min);  
19:        }  
20:        if(min!=INT_MAX)  //if get result, then stop search.
21:          break;  
22:      }  
23:    }  
24:    bool isPalindrome(string &s, int start, int end)  
25:    {  
26:      while(start< end)  
27:      {  
28:        if(s[start] != s[end])  
29:          return false;  
30:        start++; end--;  
31:      }  
32:      return true;  
33:    }  

[LeetCode] Palindrome Partitioning, Solution

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

» Solve this problem

[Thoughts]
这种需要输出所有结果的基本上都是DFS的解法。实现如下。

[Code]

1:       vector<vector<string>> partition(string s) {  
2:            vector<vector<string>> result;  
3:            vector<string> output;  
4:            DFS(s, 0, output, result);  
5:            return result;  
6:       }  
7:       void DFS(string &s, int start, vector<string>& output, vector<vector<string>> &result)  
8:       {      
9:            if(start == s.size())  
10:            {  
11:                 result.push_back(output);  
12:                 return;  
13:            }  
14:            for(int i = start; i< s.size(); i++)  
15:            {    
16:                 if(isPalindrome(s, start, i))  
17:                 {  
18:                      output.push_back(s.substr(start, i-start+1));  
19:                      DFS(s, i+1, output, result);  
20:                      output.pop_back();  
21:                 }  
22:            }  
23:       }  
24:       bool isPalindrome(string &s, int start, int end)  
25:       {  
26:            while(start< end)  
27:            {  
28:                 if(s[start] != s[end])  
29:                 return false;  
30:                 start++; end--;  
31:            }  
32:            return true;  
33:       }  

[LeetCode] Surrounded Regions, Solution

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

» Solve this problem

[解题思路]
刚拿到这个题，首先得想法就是BFS。对于每一个O，扫描其相邻节点，然后标示之，如果一个联通区域中有任何一个O在边界上，则保留之，否则清除该联通域。实现代码如下：

1:    vector<int> xIndex;  
2:    vector<int> yIndex;  
3:    map<int, int> visited;  
4:    void solve(vector<vector<char>> &board) {  
5:      int row = board.size();  
6:      if(row == 0) return;  
7:      int col = board[0].size();  
8:      for(int i =0; i < row; i++)  
9:      {  
10:        for(int j =0; j< col; j++)  
11:        {  
12:          if(board[i][j] == 'X' || IsVisited(i*row+j)) continue;  
13:          visited.clear();  
14:          bool surranded = true;  
15:          xIndex.clear();  
16:          xIndex.push_back(i);  
17:          yIndex.clear();  
18:          yIndex.push_back(j);  
19:          int k =0;  
20:          while(k<xIndex.size())  
21:          {  
22:            int x = xIndex[k];  
23:            int y = yIndex[k];     
24:            visited[x*row +y] =1;  
25:            if(IsInBoundary(x, y, row, col)) surranded = false;  
26:            if(x<row-1 && board[x+1][y] == 'O' && !IsVisited((x+1)*row+y)) {xIndex.push_back(x+1); yIndex.push_back(y);}  
27:            if(y<col-1 && board[x][y+1] == 'O' && !IsVisited(x*row+y+1)) {xIndex.push_back(x); yIndex.push_back(y+1);}  
28:            k++;  
29:          }  
30:          if(surranded) //clean the surranded mask  
31:          {  
32:            for(int m = 0; m<xIndex.size(); m++)  
33:            {  
34:              board[xIndex[m]][yIndex[m]] = 'X';    
35:            }  
36:          }  
37:        }  
38:      }  
39:    }  
40:    bool IsInBoundary(int x, int y, int row, int col)  
41:    {  
42:      if(x ==0 || x == row-1) return true;  
43:      if(y ==0 || y == col-1) return true;  
44:      return false;  
45:    }  
46:    bool IsVisited(int index)  
47:    {  
48:      if(visited.find(index) == visited.end()) return false;  
49:      return true;  
50:    }  

小数据可以过，但是大数据提示Memory Limit Exceeded，代码中唯一用到的就是visited这个map，所以，系统期望的方法应该是不需要辅助空间的。

转换一下思路，真的需要开辟一个map在存储访问信息吗？其实这个可以省掉的，既然已经知道连通区域必须至少一个元素是在四边，那么一开始直接从四边开始扫描就好了，所以无法connect到得元素都是应该被清除的。所以，算法如下：
1. 从四条边上的O元素开始BFS，所有相连的O都赋个新值，比如‘Y’
2. 扫描整个数组，所有现存的O元素全部置为X，所有Y元素置为O
打完收工。代码实现如下：

1:       vector<int> xIndex;  
2:       vector<int> yIndex;  
3:       void solve(vector<vector<char>> &board) {  
4:            int row = board.size();  
5:            if(row == 0) return;  
6:            int col = board[0].size();  
7:            xIndex.clear();  
8:            yIndex.clear();            
9:            for(int i =0; i< row; i++)  
10:            {  
11:                 if(board[i][0] == 'O')  
12:                 {  
13:                      xIndex.push_back(i);  
14:                      yIndex.push_back(0);  
15:                 }  
16:                 if(board[i][col-1] == 'O')  
17:                 {  
18:                      xIndex.push_back(i);  
19:                      yIndex.push_back(col-1);  
20:                 }  
21:            }  
22:            for(int i =0; i< col; i++)  
23:            {  
24:                 if(board[0][i] == 'O')  
25:                 {  
26:                      xIndex.push_back(0);  
27:                      yIndex.push_back(i);  
28:                 }  
29:                 if(board[row-1][i] == 'O')  
30:                 {  
31:                      xIndex.push_back(row-1);  
32:                      yIndex.push_back(i);  
33:                 }  
34:            }            
35:            int k =0;  
36:            while(k<xIndex.size())  
37:            {  
38:                 int x = xIndex[k];  
39:                 int y = yIndex[k];     
40:                 board[x][y] = 'Y';  
41:                 if(x>0 && board[x-1][y] == 'O' ) {xIndex.push_back(x-1); yIndex.push_back(y);}  
42:                 if(x<row-1 && board[x+1][y] == 'O' ) {xIndex.push_back(x+1); yIndex.push_back(y);}                 
43:                 if(y>0 && board[x][y-1] == 'O' ) {xIndex.push_back(x); yIndex.push_back(y-1);}  
44:                 if(y<col-1 && board[x][y+1] == 'O' ) {xIndex.push_back(x); yIndex.push_back(y+1);}  
45:                 k++;  
46:            }  
47:            for(int i =0; i< row; i++)  
48:            {  
49:                 for(int j =0; j< col; j++)  
50:                 {  
51:                      if(board[i][j] =='O') board[i][j] = 'X';  
52:                      if(board[i][j] == 'Y') board[i][j] = 'O';  
53:                 }  
54:            }            
55:       }