本博客记录的是 LeetCode 31 到 40 题的题解

之前很少使用的语法

31. Next Permutation

C++ code

class Solution {
public:
    // 有点类似于找规律的题目，直接多写几个就可以找到规律了
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), l = nums.size() - 1, r = nums.size() - 1;
        for (int i = n - 2; i >= 0; i -- ) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
            l -= 1;
        }
        int i = l, j = r;
        while (i < j) {
            swap(nums[i], nums[j]);
            i ++, j --;
        }
        if (l == 0) {
            return;
        } else {
            for (int i = l; i <= r; i ++ ) {
                if (nums[i] > nums[l - 1]) {
                    swap(nums[i], nums[l - 1]);
                    break;
                }
            }
        }
        
    }
};

python code

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        l, r = n - 1, n - 1
        for i in range(n - 2, -1, -1):
            if nums[i] >= nums[i + 1]:  # 这里需要有个等号
                l -= 1
            else:
                break
        i, j = l, r
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i, j = i + 1, j - 1
        if l == 0:
            return
        else:
            print(nums)
            for i in range(l, n):
                if nums[i] > nums[l - 1]:
                    nums[i], nums[l - 1] = nums[l - 1], nums[i]
                    break
            print(nums)
            return

33. Search in Rotated Sorted Array

两次二分，第一次是找旋转点，第二次是在有序数组中找target

c++代码

class Solution {
public:
    int get_idx(vector<int>& nums, int l, int r, int target) {
        int mid;
        if (target > nums[r] || target < nums[l]){
            return -1;
        } else {
            while (l < r) {
                mid = l + r + 1 >> 1;
                if (nums[mid] <= target) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            if (nums[l] == target) {
                return l;
            } else {
                return -1;
            }
        }
        
    }


    int search(vector<int>& nums, int target) {
        // 首先，二分找分界点
        int n = nums.size();
        if (nums[0] <= nums[n - 1]) {    // 没有旋转
            return get_idx(nums, 0, n - 1, target);
        } else {    // 旋转了，需要二分找分界点 mid 
            int l = 0, r = n - 1, mid, x = nums[0];
            while (l < r) {
                mid = l + r >> 1;
                if (nums[mid] < x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            printf("split mid=%d\n", l);
            if (target > nums[n - 1]) {
                return get_idx(nums, 0, l - 1, target);
            } else {
                return get_idx(nums, l, n - 1, target);
            }
        }
    }
};

python 代码

class Solution:
    def get_idx(self, nums, l, r, target):
        if nums[l] > target or nums[r] < target:
            return -1
        while l < r:
            mid = (l + r + 1) // 2
            if nums[mid] <= target:
                l = mid
            else:
                r = mid - 1
        return l if nums[l] == target else -1

    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if nums[0] <= nums[n - 1]:  # no rotation
            return self.get_idx(nums, 0, n - 1, target)
        else:
            l, r = 0, n - 1
            while l < r:
                mid = (l + r) // 2
                if nums[mid] < nums[0]:
                    r = mid
                else:
                    l = mid + 1
            if nums[n - 1] >= target:
                return self.get_idx(nums, l, n - 1, target)
            else:
                return self.get_idx(nums, 0, l - 1, target)

34. Find First and Last Position of Element in Sorted Array

二分查找的基础题目

c++ 代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (nums.size() <= 0) {
            return vector<int>{-1, -1};
        }
        int x = target;
        int l, r, mid, n = nums.size();
        l = 0, r = n - 1;
        // 大于等于 x 的最小值
        while (l < r) {
            mid = l + r >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int res1, res2;
        if (nums[l] != target) {
            return vector<int> {-1, -1};
        }
        res.push_back(l);
        // 小于等于 x 的最大值
        l = 0, r = n - 1;
        while (l < r) {
            mid = l + r + 1 >> 1;
            if (nums[mid] <= x) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        res.push_back(l);
        return res;
    }
};

python 代码

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        if n == 0 or target > nums[-1] or target < nums[0]:
            return [-1, -1]
        
        # higher target min value
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        if nums[l] != target:
            return [-1, -1]
        res = [l]

        # lower target max value
        l, r = 0, n - 1
        while l < r:
            mid = (l + r + 1) // 2
            if nums[mid] <= target:
                l = mid
            else:
                r = mid - 1
        res.append(l)
        
        return res

35. Search Insert Position

就是寻找大于等于 target 的最小值所在的位置，相当于 34 题一半的代码量

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 寻找大于等于 target 的最小值所在的位置
        n = len(nums)
        if nums[-1] < target:
            return n
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        return l