Leetcode_14 天算法入门_day1

Posted on | Edited on | In ,
| 3.1k | 26 mins.

来试试 Leetcode 14 天算法入门的难度。

第一天的主题是二分查找，给了 3 道简单题。

704. Binary Search

Analysis

注意退出循环的条件是left <= right。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, mid;
        while(left <= right) {
            /* You can also write this way to avoid overflows.
            mid = (right - left) / 2 + left;
            */
            mid = (left + right) / 2;
            if(nums[mid] > target) {
                right = mid - 1;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] == target) return mid;
            
        }
        return -1;
    }
};

278. First Bad Version

Analysis

这个题一开始想到的是直接循环，结果不出所料的超时了，然后又改成了二分。话说，好像没有看清楚题目的条件：You should minimize the number of calls to the API.。之所以要返回 left，是因为 left 一定是 bad version。但是，mid 在每次循环后，就不一定是 bad version 了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n, mid;
        while(left <= right) {
            mid = (right - left) / 2 + left;
            if(isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            } 
        }
        return left;
    }
};

35. Search Insert Position

Analysis

一开始被这个题绕进去了，以为要把找到没找到的情况单独的拿出来讨论。实际上，按照二分查找的思路，mid 最后只有两种结果：

  1. 找到了 target 的位置。
  2. 找到了最后一个小于 target 的值的位置。

所以根据不同情况返回 target 的位置或 target 要插入的位置就可以了。

实际上，这个原理应该是 lower_bound() 函数的实现原理，只不过，lower_bound() 函数返回的位置信息应该是查找不到后的 left（如果没查找到，最终 right 一定会小于 left，因为只有这样才能退出循环），而这个值其实也就是插入的位置。
其实也就是说，找到了，就返回 mid，没找到，就返回 left。

Code

version 1

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

version 2

1
2
3
4
5
6
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};

version 3

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

Summary

一次性连续 3 做道同知识点的题目，对巩固这个知识点倒是很有帮助。二分查找返回的下标确实是一个容易让人迷惑的点，可能会有人喜欢把循环的条件写成left < right，这样写应该也是可以的，不过返回值可能需要相应的做出调整。

Buy me a coffee ? :)
0%