leetcode Ch1-Search

一、 Binary Search

 1 int binarySearch(vector<int> &array, int target) 
 2 {
 3     int lo = 0, hi = array.size() - 1;
 4     while (lo <= hi)
 5     {
 6         int mid = lo + (hi - lo) / 2;
 7         if (array[mid] > target)
 8             hi = mid - 1;
 9         else if (array[mid] < target)
10             lo = mid + 1;
11         else return mid;
12     }
13     return -1;
14 }

View Code

注意是　while(lo<=hi)

当然，也不是绝对的，这只是我的习惯写法。while里是 < 还是 <= 取决于hi/right 的初值和赋值。

/首先要把握下面几个要点：    
//right=n-1 => while(left <= right) => right=middle-1;    
//right=n   => while(left <  right) => right=middle;

ref to july

二、 Search Insert Position

 1 class Solution
 2 {
 3 public:
 4     int searchInsert(vector<int> &nums,int target)
 5     {
 6         int lo=0,hi=nums.size()-1;
 7         while(lo<=hi)
 8         {
 9             int mid=lo+(hi-lo)/2;
10             if(nums[mid]>target)
11                 hi=mid-1;
12             else if(nums[mid]<target)
13                 lo=mid+1;
14             else return mid;
15         }
16         return lo;
17     }
18 };

View Code

当循环结束时，如果没有找到目标元素，那么lo一定停在恰好比目标大的元素的index上，hi一定停在恰好比目标小的index上.

【简单理解的话，因为如果找不到目标元素，那么退出循环时必定是lo>hi的。此时lo指向大于target的元素，hi指向小于target的元素】

详细查看自己以前写的分析： ref

三、

1. Search for a Range

 1 class Solution
 2 {
 3 public:
 4     vector<int> searchRange(vector<int> &nums,int target)
 5     {
 6         vector<int> res(2,-1);
 7         int lo=0,hi=nums.size()-1;
 8         while(lo<=hi)
 9         {    
10             int mid=lo+(hi-lo)/2;
11             if(nums[mid]>target)
12                 hi=mid-1;
13             else if(nums[mid]<target)
14                 lo=mid+1;
15             else    
16             {
17                 res[0]=lowerbound(nums,lo,mid,target);
18                 res[1]=upperbound(nums,mid,hi,target)-1;
19                 return res; //千万别遗漏
20             }
21         }
22         return res;
23     }
24     int upperbound(vector<int> &nums,int left,int right,int target)
25     {
26         int lo=left,hi=right;
27         while(lo<=hi)
28         {
29             int mid=lo+(hi-lo)/2;
30             if(nums[mid]>target)
31                 hi=mid-1;
32             else if(nums[mid]<=target)
33                 lo=mid+1;
34         }
35         return lo;
36     }
37     int lowerbound(vector<int> &nums,int left,int right,int target)
38     {
39         int lo=left,hi=right;
40         while(lo<=hi)
41         {
42             int mid=lo+(hi-lo)/2;
43             if(nums[mid]>=target)
44                 hi=mid-1;
45             else if(nums[mid]<target)
46                 lo=mid+1;
47         }
48         return hi+1;
49     }
50 };

View Code

注意Line17,18处，范围分别缩小成(lo,mid)和(mid,hi)了。

upperbound和lowerbound的原理详见以前的分析，第1题后面那一大段总结。

#2: upperBound返回的是第一个大于target元素的位置；lowerBound返回的是第一个小于等于target元素的位置。

所以对于一个nums中有的元素，返回其range应该是 [lowerBound, upperBound - 1]

另外，还有一点需要特别注意：Line19千万不能遗漏，如果遗漏了就成了TLE。

update 15.8.21

上述的upperBound和lowerBound中的“大于”，“小于等于”是库函数里的定义。我可以不用管那么多，就分别用lowerBound和upperBound分别返回target在数组中的第一个和最后一个的位置即可。清晰自然。

 1 vector<int> searchRange(vector<int>& nums, int target) {
 2     vector<int> result(2, -1);
 3     int lo = 0, hi = nums.size() - 1;
 4     while (lo <= hi) {
 5         int mid = lo + (hi - lo) / 2;
 6         if (nums[mid] < target) {
 7             lo = mid + 1;
 8         } else if (nums[mid] > target) {
 9             hi = mid - 1;
10         } else {    
11             result[0] = lowerBound(nums, target);
12             result[1] = upperBound(nums, target);
13             return result;
14         }
15     }
16     return result;
17 }
18 
19 int upperBound(vector<int>& nums, int target) {
20     int lo = 0, hi = nums.size() - 1;
21     while (lo <= hi) {
22         int mid = lo + (hi - lo) / 2;
23         if (nums[mid] <= target) {
24             lo = mid + 1;
25         } else {
26             hi = mid - 1;
27         }
28     }
29     return lo - 1;
30 }
31 int lowerBound(vector<int>& nums, int target) {
32     int lo = 0, hi = nums.size() - 1;
33     while (lo <= hi) {
34         int mid = lo + (hi - lo) / 2;
35         if (nums[mid] < target) {
36             lo = mid + 1;
37         } else {
38             hi = mid - 1;
39         }
40     }
41     return hi + 1;
42 }

View Code

在upperBound函数里，当nums[mid] == target时就当没看到，继续把lo向右移动。因此当退出while循环时，lo所指向的就是最后一个元素的位置+1处。返回lo - 1即为最后一个target的位置；

同理，lowerBound里，当nums[mid] == target时就当没看到，继续把hi向左移动。因此当退出while循环时，hi所指向的就是第一个元素的位置-1处。返回hi + 1即为第一个target的位置。

2. Binary Search [lintcode]

 1 class Solution {
 2 public:
 3     int binarySearch(vector<int> &array, int target) {
 4         int lo=0,hi=array.size()-1;
 5         while(lo<=hi)
 6         {
 7             int mid=lo+(hi-lo)/2;
 8             if(array[mid]>target)
 9                 hi=mid-1;
10             else if(array[mid]<target)
11                 lo=mid+1;
12             else
13             {
14                 return lowerbound(array,lo,mid,target);
15             }
16         }
17         return -1;
18     }
19     int lowerbound(vector<int> &array,int left,int right,int target)
20     {
21         int lo=left,hi=right;
22         while(lo<=hi)
23         {
24             int mid=lo+(hi-lo)/2;
25             if(array[mid]>=target)
26                 hi=mid-1;
27             else lo=mid+1;
28         }
29         return hi+1;
30     }
31 };

View Code

一开始以为是普通的binary search，后来发现它是要返回第一个target的位置（即有可能有duplicates）。借助lowerbound函数即可。

四、

1. Search in Rotated Sorted Array

O(logN)：

 1 class Solution
 2 {
 3 public:
 4     int search(vector<int> &nums,int target)
 5     {
 6         int lo=0,hi=nums.size()-1;
 7         while(lo<=hi)
 8         {
 9             int mid=lo+(hi-lo)/2;
10             if(nums[mid]==target) return mid;
11             if(nums[mid]<nums[hi])//说明右半段有序
12             {
13                 if(target>nums[mid] && target<=nums[hi])
14                     lo=mid+1;
15                 else hi=mid-1;
16             }
17             else //说明左半段有序
18             {
19                 if(target<nums[mid] && target>=nums[lo])
20                     hi=mid-1;
21                 else lo=mid+1;
22             }
23         }
24         return -1;
25     }
26 };

View Code

另一种方法：利用下面3. Find Minimum先把min的index找出来，然后根据target在哪个范围来对其进行binarySearch。

2. Search in Rotated Sorted Array II

1 class Solution {
2 public:
3     bool search(vector<int>& nums, int target) {
4         for(int i=0;i<nums.size();i++)
5             if(nums[i]==target) return true;
6         return false;
7     }
8 };

View Code

由于允许有duplicates，会导致没有办法像I中那样根据A[mid]和A[left]、A[right]的比较来确定是哪一半有序，应该在哪一半查找。

导致最坏时间复杂度变为O(n)。因此用最简单的遍历来实现就可以。

而普通情况下为O(logN),只在最坏情况下为O(N)的，可参考该问题下第一个答案。

3. Find Minimum in Rotated Sorted Array

code 1:

 1 class Solution {
 2 public:
 3     int findMin(vector<int> &nums) {
 4         int lo = 0, hi = nums.size() - 1;    
 5         int target = nums[hi];    
 6         while (lo + 1 < hi) {
 7             int mid = lo + (hi - lo) / 2;
 8             if (nums[mid] > target) {
 9                 lo = mid;
10             } else {
11                 hi = mid;
12             }
13         }
14         return min(nums[lo], nums[hi]);
15     }
16 };

View Code

NCH版本的binarySearch。用这种版本的binarySearch的好处是，在lo和hi中必有一个是最终结果，所以只需要在这两个里比较一下即可。而如果用我之前的BinarySearch版本，需要纠结和考虑究竟是返回lo还是hi。

用这种版本的BinarySearch需要注意的地方在于

1. while (lo + 1 < hi)

2. lo = mid; hi = mid;

另外，在退出while循环时，lo在左边，紧接着hi在lo右边，hi = lo + 1。并不是之前那样hi小lo大。

code 2:

 1 class Solution {
 2 public:
 3     int findMin(vector<int> &nums) {
 4         int lo = 0, hi = nums.size() - 1;
 5         int target = nums[hi];
 6         while (lo <= hi) {
 7             int mid = lo + (hi - lo) / 2;
 8             if (nums[mid] > target) {
 9                 lo = mid + 1;
10             } else {
11                 hi = mid - 1;
12             }
13         }
14         return nums[lo];        
15     }
16 };

View Code

4. Find Minimum in Rotated Sorted Array II

可以直接线性遍历一遍，最坏时间复杂度最快也只能是O(N).

五、

1. Search a 2D Matrix

 1 class Solution
 2 {
 3 public:
 4     bool searchMatrix(vector<vector<int>> &matrix, int target) {
 5         if(matrix.empty()) return -1;
 6         int m = matrix.size(), n = matrix[0].size();
 7         int lo = 0, hi = m * n - 1;
 8         while(lo <= hi) {
 9             int mid = lo + (hi - lo) / 2;
10             int x = mid / n;
11             int y = mid % n;
12             if (matrix[x][y] < target) {
13                 lo = mid + 1;
14             } else if (matrix[x][y] > target) {
15                 hi = mid - 1;
16             } else return true;
17         }
18         return false;
19     }
20 };

View Code

一开始写的很复杂，先找行数再找列数，代码长又易出错。后来参考soulmach，将二维问题转化为一维问题，瞬间简洁。

另外，以后要注意coding style了。

2. Search a 2D Matrix II [lintcode]

 1 class Solution {
 2 public:
 3     int searchMatrix(vector<vector<int> > &matrix, int target) {
 4         if (matrix.empty()) return 0;
 5         int count = 0;
 6         int m = matrix.size(), n = matrix[0].size();
 7         int row = 0, col = n - 1;
 8         while (row < m && col >= 0) {
 9             if (matrix[row][col] < target) {
10                 row++;
11             } else if (matrix[row][col] > target) {
12                 col--;
13             } else {
14                 count++;
15                 row++; //或者 col--也行
16             }
17         }
18         return count;
19     }
20 };

View Code

时间复杂度O(m+n). 这也是剑指offer上一道题。思路就是以右上角元素作为起点，向左下方走。每次可以删掉一行或一列。

六、

1. Sqrt(x)

 1 class Solution
 2 {
 3 public:
 4     int mySqrt(int x) {
 5         if(x < 2) return x;
 6         int lo = 1, hi = x;
 7         while(lo <= hi) {
 8             int mid = lo + ((hi - lo) >> 1);
 9             if(mid < x / mid) {
10                 lo = mid + 1;
11             } else if (mid > x / mid){
12                 hi = mid - 1;
13             } else return mid;
14         }
15         return hi;
16     }
17 };

View Code

2. Pow(x, n)

 1 class Solution{
 2 public:
 3     double myPow(double x, int n) {
 4         return (n > 0? power(x , n) : 1.0 / power(x , -n));
 5     }
 6     double power(double x, int n) {
 7         if (n == 0) return 1;
 8         double v = power(x , n / 2);
 9         if (n % 2 == 1) return (v * v * x);
10         else return (v * v);
11     }
12 };

View Code

七、

1. First Bad Version [lintcode]

 1 class Solution {
 2 public:
 3     int findFirstBadVersion(int n) {
 4         int lo = 1, hi = n;
 5         while (lo + 1 < hi) {
 6             int mid = lo + (hi - lo) / 2;
 7             if (VersionControl::isBadVersion(mid) == false) {
 8                 lo = mid;
 9             } else {
10                 hi = mid;
11             }
12         }
13         if (VersionControl::isBadVersion(lo) == true) {
14             return lo;
15         } else {
16             return hi;
17         }
18         return -1;
19     }
20 };

View Code

2. Find Peak Element

 1 class Solution {
 2 public:
 3     int findPeakElement(vector<int> &nums) {
 4         int lo = 0, hi = nums.size() - 1;
 5         while (lo + 1 < hi) {
 6             int mid = lo + (hi - lo) / 2;
 7             if (nums[mid] < nums[mid - 1]) {
 8                 hi = mid;
 9             } else if (nums[mid] < nums[mid + 1]) {
10                 lo = mid;
11             } else {// nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]
12                 return mid;
13             }
14         }
15         return nums[lo] < nums[hi] ? hi : lo;
16     }
17 };

View Code

能进入Line 5的while循环说明至少有3个元素。

八、

1. Remove Duplicates from Sorted Array

 1 class Solution {
 2 public:
 3     int removeDuplicates(vector<int> &nums) {
 4         if (nums.size() < 2) {
 5             return nums.size();
 6         }
 7         int index = 1;
 8         for (int i = 1; i < nums.size(); i++) {
 9             if (nums[i] != nums[i - 1]) {
10                 nums[index++] = nums[i]; 
11             }
12         }
13         return index;
14     }
15 };

View Code

2. Remove Duplicates from Sorted Array II

code 1: [推荐]

 1 class Solution {
 2 public:
 3     int removeDuplicates(vector<int> &nums) {
 4         int n = nums.size();
 5         int k = 2;
 6         if (n <= k) {
 7             return n;
 8         }
 9         int index = 1, cnt = 1;
10         for (int i = 1; i < n; i++) {
11             if (nums[i] != nums[i - 1]) {
12                 cnt = 1;
13                 nums[index++] = nums[i];
14             } else {
15                 if (cnt < k) {
16                     cnt++;
17                     nums[index++] = nums[i];
18                 }
19             }
20         }
21         return index;
22     }
23 };

View Code

该代码是通用版代码。k表示单个元素最多能允许duplicate的个数。将k改为1即可用于上一题。

code 2:

 1 class Solution {
 2 public:
 3     int removeDuplicates(vector<int> &nums) {
 4         int n = nums.size();
 5         int k = 2;
 6         if (n <= k) {
 7             return n;
 8         }
 9         int index = 1, j = 1;
10         int cnt = 1;
11         while (j < n) {
12             if (nums[j] != nums[j - 1]) {
13                 cnt = 1;
14                 nums[index++] = nums[j];
15             } else {
16                 if (cnt < k) {
17                     nums[index++] = nums[j];
18                     cnt++;
19                 }
20             }
21             j++;
22         }
23         return index;
24     }
25 };

View Code

ref

九、 Merge Sorted Array

 1 class Solution {
 2 public:
 3     void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
 4         int i = m - 1, j = n - 1, k = m + n - 1;
 5         while (i >= 0 && j >= 0) {
 6             nums1[k--] = (nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--]);
 7         }
 8         while (j >= 0) {
 9             nums1[k--] = nums2[j--];
10         }
11     }
12 };

View Code

十、 Median of Two Sorted Arrays

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
 4         int m = nums1.size(), n = nums2.size();
 5         if ((m + n) % 2 == 1) {
 6             return findKth(nums1, 0, m - 1, nums2, 0, n - 1, (m + n) / 2 + 1);
 7         } else {
 8             return (findKth(nums1, 0 ,m - 1, nums2, 0, n - 1, (m + n) / 2) 
 9             + findKth(nums1, 0, m - 1, nums2, 0, n - 1, (m + n) / 2 + 1)) / 2.0;
10         }
11     }
12     int findKth(vector<int> &nums1, int aL, int aR, vector<int> &nums2, int bL, int bR, int k) {
13         if (aL > aR) {
14             return nums2[bL + k - 1];
15         } 
16         if (bL > bR) {
17             return nums1[aL + k - 1];
18         }
19         int aMid = (aL + aR) / 2;
20         int bMid = (bL + bR) / 2;
21         if (nums1[aMid] < nums2[bMid]) {
22             if (k <= (aMid - aL + bMid - bL + 1)) {
23                 return findKth(nums1, aL, aR, nums2, bL, bMid - 1, k);
24             } else {
25                 return findKth(nums1, aMid + 1, aR, nums2, bL, bR, k - (aMid - aL + 1));        
26             }
27         } else {
28             if (k <= (aMid - aL + bMid - bL + 1)) {
29                 return findKth(nums1, aL, aMid - 1, nums2, bL, bR, k);
30             } else {
31                 return findKth(nums1, aL, aR, nums2, bMid + 1, bR, k - (bMid - bL + 1));
32             }
33         }
34     }    
35 };

View Code

每次取两数组的中间点进行比较。

若A数组的中间点的值 < B数组的中间点的值，则

　　如果k很小，则剔除B数组的后半段；（这里的k很小指的是：k <= (A中点以左的长度 + B中点以左的长度 + 1)）

　　如果k很大，则剔除A数组的前半段；

同理，若A数组的中间点的值 > B数组的中间点的值，也类似地讨论。

ref 有讲解。

需要注意的点：

Line22 & 28 ：严格一致。

Line 23,25,29,31：原则就是，当k小时，就去掉较大的数组的较大的半段（后半段）；当k大时，就去掉较小的数组的较小的半段（前半段）。

Line21 ： <或<=均可。

十一、三步翻转法：

1. Recover Rotated Sorted Array

 1 class Solution {
 2 public:
 3     void recoverRotatedSortedArray(vector<int> &nums) {
 4         int i = 0;
 5         for (; i < nums.size() - 1; i++) {
 6             if (nums[i] > nums[i + 1]) {
 7                 break;   
 8             }
 9         }
10         reverse(nums, 0, i);
11         reverse(nums, i + 1, nums.size() - 1);
12         reverse(nums, 0, nums.size() - 1);
13     }
14     void reverse(vector<int> &nums, int start, int end) {
15         while (start < end) {
16             int tmp = nums[start];
17             nums[start] = nums[end];
18             nums[end] = tmp;
19             start++;
20             end--;
21         }
22     }
23 };

View Code

注意：必须用自己实现的reverse函数，不能用sort，因为sort的时间复杂度是O(nlogn)，而题目要求是O(n);

2. Rotate String

 1 class Solution {
 2 public:
 3     string rotateString(string A, int offset) {
 4         int len = A.length();
 5         if (len <= 0) {
 6             return A;
 7         }
 8         offset = offset % len;
 9         reverse(A, 0, len - 1 - offset);
10         reverse(A, len - offset, len - 1);
11         reverse(A, 0, len - 1);
12         return A;
13     }
14     void reverse(string &str, int start, int end) {
15         while (start < end) {
16             int tmp = str[start];
17             str[start] = str[end];
18             str[end] = tmp;
19             start++;
20             end--;
21         }
22     }
23 };

View Code

注意小细节：

(1). offset需要取余； (2). 当len == 0 时需要作特殊处理。corner case.

3. Rotate Array

 1 class Solution {
 2 public:
 3     void rotate(vector<int>& nums, int k) {
 4         k = k % nums.size();
 5         reverse(nums, 0, nums.size() - 1 - k);
 6         reverse(nums, nums.size() - k, nums.size() - 1);
 7         reverse(nums, 0, nums.size() - 1);
 8     }
 9     void reverse(vector<int> &nums, int start, int end) {
10         while (start < end) {
11             int tmp = nums[start];
12             nums[start] = nums[end];
13             nums[end] = tmp;
14             start++;
15             end--;
16         }
17     }
18 };

View Code

和上一题一样。

4. Reverse Words in a String

方法一：空间O(n), 时间O(n)

 1 class Solution {
 2 public:
 3     void reverseWords(string &s) {
 4         string result;
 5         for (int i = s.size() - 1; i >= 0;)    {
 6             while (i >= 0 && s[i] == ' ') {
 7                 i--;
 8             }
 9             if (i < 0) {
10                 break;
11             }
12             if (!result.empty()) {
13                 result += ' ';
14             }
15             string word;
16             while (i >= 0 && s[i] != ' ') {    
17                 word += s[i];
18                 i--;
19             }
20             reverse(word.begin(), word.end());
21             result += word;
22         }
23         s = result;
24     }
25 };

View Code

注意：Line 9 千万不能少，这句代码的意义在于，抛弃开头的那些leading spaces。

ref

方法二：空间O(1) [in-place], 时间O(n).

 1 class Solution {
 2 public:
 3     void reverseWords(string &s) {
 4         reverse(s, 0, s.size() - 1);
 5         int index = 0;
 6         for (int i = 0; i < s.size(); i++) {
 7             if (s[i] != ' ') {
 8                 if (index != 0) {
 9                     s[index++] = ' ';
10                 }
11                 int j = i;
12                 while (j < s.size() && s[j] != ' ') {
13                     s[index++] = s[j++];
14                 }
15                 reverse(s, index - (j - i), index - 1);
16                 i = j;
17             }
18         }
19         s.resize(index);
20     }
21     void reverse(string &str, int start, int end) {
22         while (start < end) {
23             int tmp = str[start];
24             str[start] = str[end];
25             str[end] = tmp;
26             start++;
27             end--;
28         }
29     }
30 };

View Code

ref

5. Reverse Words in a String II

 1 class Solution {
 2 public:
 3     void reverseWords(string &s) {
 4         reverse(s, 0, s.size() - 1);
 5         int index = 0;
 6         for (int j = 0; j <= s.size(); j++) {
 7             if (j == s.size() || s[j] == ' ') {
 8                 reverse(s, index, j - 1);
 9                 index = j + 1;
10             }
11         }
12     }
13     void reverse(string &str, int start, int end) {
14         while (start < end) {
15             int tmp = str[start];
16             str[start] = str[end];
17             str[end] = tmp;
18             start++;
19             end--;
20         }
21     }
22 };

View Code

注意：这里让j从0一直循环到s.size(), 原因在于将“遇到空格”和“遇到句末”统一到一个if里，使代码简洁。

题目描述 ref