Cloud_Player's Notes
0%

LeetCode Day1

发表于 更新于
本文字数： 4k 阅读时长 ≈ 4 分钟

LeetCode Day1

万般皆下品，刷题才是真

数组

数组理论基础

二分查找

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        int mid, midvalue;
        while(low <= high)
        {
            mid = (low + high) / 2;
            midvalue = nums[mid];
            if(midvalue == target)  return mid;
            if(midvalue < target) low = mid + 1;
            if(midvalue > target) high = mid - 1;
        }
        return -1;
    }
};

/*
前提：数组为有序数组，数组中无重复元素
代码区间的定义：[low, high]，左闭右闭区间
mid = (low + high) / 2;
可替换为
mid = low + (high - low) / 2;
防止溢出
*/

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        int mid, midvalue;
        while(low <= high)
        {
            mid = low + (high - low) / 2;
            midvalue = nums[mid];
            if(midvalue == target)  return mid;
            if(midvalue < target)   low = mid + 1;
            if(midvalue > target)   high = mid - 1;
        }
        return low;
    }
};

/*
15行的
return low;
可以改成：
if(midvalue < target) return mid + 1;
else return mid;
本题在二分法的基础上加了一个判断插入位置的思考
*/

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result = {-1, -1};
        int low = 0, high = nums.size() - 1;
        int mid, midvalue;
        bool flag = false;
        while(low <= high)
        {
            mid = low + (high - low) / 2;
            midvalue = nums[mid];
            if(midvalue == target) {flag = true; break;}
            if(midvalue < target) low = mid + 1;
            if(midvalue > target) high = mid - 1;
        }
        if(!flag) return result;
        else
        {   
            int left = -1, right = -1;
            int leftlow = 0, lefthigh = mid;
            int rightlow = mid, righthigh = nums.size() - 1;
            int leftmid, leftmidvalue;
            int rightmid, rightmidvalue;
            while(leftlow <= lefthigh)
            {
                leftmid = leftlow + (lefthigh - leftlow) / 2;
                leftmidvalue = nums[leftmid];
                if(leftmidvalue == target)
                {
                    if(leftmid == 0) {left = leftmid; break;}
                    if(leftmid > 0)
                    {
                        if(nums[leftmid - 1] < target) {left = leftmid; break;}
                        else lefthigh = leftmid - 1;
                    } 
                }
                if(leftmidvalue < target) leftlow = leftmid + 1;
            }
            while(rightlow <= righthigh)
            {
                rightmid = rightlow + (righthigh - rightlow) / 2;
                rightmidvalue = nums[rightmid];
                if(rightmidvalue == target)
                {
                    if(rightmid == nums.size() - 1) {right = rightmid; break;}
                    if(rightmid < nums.size() - 1)
                    {
                        if(nums[rightmid + 1] > target) {right = rightmid; break;}
                        else rightlow = rightmid + 1;
                    } 
                }
                if(rightmidvalue > target) righthigh = rightmid - 1;
            }
            result[0] = left; result[1] = right;
        }
        return result;
    }
};

/*
这题数组中出现了重复元素，想法是用三个二分法
先用一个二分法判断数组中有无目标元素
若有，其位置为mid，再在 [0, mid] 与 [mid, nums.size()-1]
这两个区间内分别用二分法找到目标元素与其它元素的边界
*/

/* 官方代码 */
/* 更简洁，将二分的过程封装成了函数，实际只用了两个二分找出左右边界 */
class Solution { 
public:
    int binarySearch(vector<int>& nums, int target, bool lower) {
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
            return vector<int>{leftIdx, rightIdx};
        } 
        return vector<int>{-1, -1};
    }
};

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    long mySqrt(long x) {
        long low = 1, high = x / 2;
        long mid, power2;
        while(low <= high)
        {
            mid = low + (high - low) / 2;
            power2 = mid * mid;
            if(power2 > x) high = mid - 1;
            else if(power2 < x) low = mid + 1;
            else break;
        }
        return power2 > x ? mid - 1 : mid;
    }
};

/* 
简单二分
*/

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num == 1) return true;
        int low = 1, high = num / 2;
        int mid;
        while(low <= high)
        {
            mid = low + (high - low) / 2;
            if((long long)mid * mid == num) return true;
            else if((long long)mid * mid > num) high = mid - 1;
            else low = mid + 1;
        }
        return false;
    }
};

/*
注意 1 这种特殊情况
*/