[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] Sum Root to Leaf Numbers, Solution

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

» Solve this problem


[Thoughts]
Recursion. Similar as [LeetCode] Binary Tree Maximum Path Sum Solution, the difference here is only adding a track variable to sum all the paths.

[Code]

1:       int sumNumbers(TreeNode *root) {  
2:            int sum=0, path =0;            
3:            GenerateSum(root, sum, path);  
4:            return sum;  
5:       }  
6:       void GenerateSum(TreeNode *root, int& sum, int path)  
7:       {  
8:            if(root == NULL) return;      
9:            path = path*10 +root->val;  
10:            if(root->left == NULL && root->right == NULL)  
11:            {  
12:                 sum+=path;  
13:                 return;  
14:            }  
15:            GenerateSum(root->left, sum, path);  
16:            GenerateSum(root->right, sum, path);  
17:       }  

[LeetCode] Count and Say, Solution

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

» Solve this problem

[Thoughts]
string-operation. The only trick thing is Line11. seq[seq.size()] always '\0'. It will help to save an "if" statement.


[Code]

1:    string countAndSay(int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string seq = "1";  
5:      int it = 1;  
6:      while(it<n)  
7:      {  
8:        stringstream newSeq;  
9:        char last = seq[0];  
10:        int count =0;  
11:        for(int i =0; i<= seq.size();i++)  
12:        {  
13:          if(seq[i] ==last)  
14:          {  
15:            count ++;  
16:            continue;  
17:          }  
18:          else  
19:          {  
20:            newSeq<<count<<last;  
21:            last = seq[i];   
22:            count =1;  
23:          }  
24:        }  
25:        seq = newSeq.str();  
26:        it++;  
27:      }  
28:      return seq;  
29:    }  

[LeetCode] Search Insert Position 解题报告

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

» Solve this problem

[解题思路]
跟经典的二分查找相比，只是多了一个条件：
if(mid>left && A[mid]>target && A[mid-1]<target)


[Code]

1:  int searchInsert(int A[], int n, int target) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int l=0, r=n-1;  
5:      while(l<=r)  
6:      {  
7:        int mid = (l+r)/2;  
8:        if(A[mid] == target) return mid;  
9:        if(mid>l && A[mid]>target && A[mid-1]<target ) return mid;  
10:        if(A[mid] > target)  
11:        {  
12:          r= mid-1;  
13:        }  
14:        else  
15:        {  
16:          l=mid+1;  
17:        }        
18:      }  
19:      return l;  
20:    }  

[LeetCode] Search in Rotated Sorted Array II 解题报告

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

» Solve this problem

[解题思路]
确实有影响。比如，上一题(http://fisherlei.blogspot.com/2013/01/leetcode-search-in-rotated-sorted-array.html)的程序中默认如果A[m]>=A[l],那么[l,m]为递增序列的假设就不能成立了，比如如下数据
[1,3,1,1,1]
所以，要是想增强该假设，有两个选择
1. 对于每一个递增序列，遍历之，确认。
2. 找到pivot点，然后确定对应序列搜索。


不写代码了。


Update: 3/18/2013. add the implementation
重新想了一下，其实不需要这么复杂。如果A[m]>=A[l]不能确定递增，那就把它拆分成两个条件
1. A[m]>A[l]  递增
2. A[m] ==A[l] 确定不了，那就l++，往下看一步即可。

实现如下

1:       bool search(int A[], int n, int target) {  
2:            int start = 0;  
3:            int end = n-1;  
4:            while(start <= end)  
5:            {  
6:                 int mid = (start+end)/2;  
7:                 if(A[mid] == target) return true;  
8:                 if(A[start] < A[mid])  
9:                 {  
10:                      if(target>=A[start] && target<A[mid])  
11:                           end = mid-1;  
12:                      else   
13:                           start = mid+1;  
14:                 }  
15:                 else if(A[start] > A[mid])  
16:                 {  
17:                      if(target>A[mid] && target<=A[end])  
18:                           start = mid+1;  
19:                      else  
20:                           end = mid-1;  
21:                 }  
22:                 else //skip duplicate one, A[start] == A[mid]  
23:                      start++;  
24:            }  
25:            return false;  
26:       }  

[LeetCode] Search in Rotated Sorted Array 解题报告

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

» Solve this problem


[解题思想]
同样是二分，难度主要在于左右边界的确定。需要结合两个不等式：
1. A[m] ? A[left]
2. A[m] ? target
具体逻辑看code。

[Code]

1:       int search(int A[], int n, int target) {   
2:            // Start typing your C/C++ solution below   
3:            // DO NOT write int main() function   
4:            int l = 0, r = n-1;   
5:            while(l<=r)   
6:            {   
7:                 int m = (l+r)/2;   
8:                 if(A[m] == target) return m;   
9:                 if(A[m]>= A[l])   
10:                 {   
11:                      if(A[l]<=target && target<= A[m])   
12:                      r=m-1;   
13:                      else   
14:                      l = m+1;       
15:                 }   
16:                 else   
17:                 {   
18:                      if(A[m] >= target || target>= A[l])   
19:                      r = m-1;    
20:                      else   
21:                      l = m+1;   
22:                 }   
23:            }   
24:            return -1;   
25:       }   

Update 08/23/2014
See the comments from reader. Add a graph and also change the code a bit for readability(See highlight code in red).

The general idea is, to use some in-equations to distinguish below 3 conditions, and decide the new range of binary search.

1:       int search(int A[], int n, int target) {    
2:            int l = 0, r = n-1;    
3:            while(l<=r)    
4:            {    
5:                 int m = (l+r)/2;    
6:                 if(A[m] == target) return m;    
7:                 if(A[m]>= A[l])    
8:                 {    
9:                      if(A[l]<=target && target< A[m])    
10:                           r=m-1;    
11:                      else    
12:                           l = m+1;      
13:                 }    
14:                 else    
15:                 {    
16:                      if(A[m]< target && target<=A[r])    
17:                           l = m+1;    
18:                      else    
19:                           r = m-1;   
20:                 }    
21:            }    
22:            return -1;    
23:       }    

[LeetCode] Search for a Range 解题报告

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

» Solve this problem


[解题思路]
首先二分，然后根据二分的坐标分别往前和往后找找即可。

[Code]

1:       vector<int> searchRange(int A[], int n, int target) {  
2:            // Start typing your C/C++ solution below  
3:            // DO NOT write int main() function  
4:            vector<int> range;  
5:            int index = searchTarget(A, 0, n-1, target);  
6:            if(index == -1)  
7:            {  
8:                 range.push_back(-1);  
9:                 range.push_back(-1);  
10:            }  
11:            else  
12:            {  
13:                 int is = index;  
14:                 while(is>0 && A[is-1] == A[index]) is--;  
15:                 int ie = index;  
16:                 while(ie<n-1 && A[ie+1] == A[index]) ie++;  
17:                 range.push_back(is);  
18:                 range.push_back(ie);        
19:            }  
20:            return range;  
21:       }  
22:       int searchTarget(int A[], int start, int end, int target)  
23:       {  
24:            if(start > end) return -1;  
25:            int mid = (start+end)/2;  
26:            if(A[mid] == target) return mid;  
27:            if(A[mid]<target)  
28:            return searchTarget(A, mid+1, end, target);  
29:            else  
30:            return searchTarget(A, start, mid-1, target);      
31:       }  

[Note]
1. Line 6
错误的写成，"if(index = -1)", 少了个=号，结果老是输出[-1,-1].


Update: 07/15/2013 Refactor the code
看了一下评论，Jarvis很关注最差时间复杂度。其实从题目上来说，它更关注是平均复杂度。上面的算法在最差情况下复杂度是O(n)，但是平均复杂度是O(lgn)。
如果想实现最差复杂度也是O(lgn)，也很简单，做两次二分就可以了，第一次二分找出最左边的边界，第二次二分找出最右边的边界，这样，无论平均还是最差都是O(lgn)。

实现如下：

1:    vector<int> searchRange(int A[], int n, int target) {  
2:      vector<int> result;  
3:      result.push_back(-1);  
4:      result.push_back(-1);    
5:      // find the low bound of the range, O(lgn)  
6:      int start =0, end =n-1;  
7:      while(start < end)  
8:      {  
9:        int mid = (start + end)/2;  
10:        if(A[mid] < target)  
11:        {  
12:          start = mid + 1;  
13:          continue;  
14:        }  
15:        end = mid;  
16:      }      
17:      int low_bound = A[start] == target? start:-1;  
18:      if(low_bound == -1)  
19:      {  
20:        return result;  
21:      }  
22:      // find the high bound of the range, O(lgn)  
23:      start =low_bound, end =n;  
24:      while(start < end)  
25:      {  
26:        int mid = (start + end)/2;  
27:        if(A[mid] > target)  
28:        {  
29:          end = mid;  
30:          continue;  
31:        }            
32:        start = mid+1;  
33:      }  
34:      int high_bound = start-1;  
35:      result.clear();  
36:      result.push_back(low_bound);  
37:      result.push_back(high_bound);  
38:      return result;      
39:    }