代码随想录leetcode200题之数组

1 介绍

本博客用来记录代码随想录leetcode200题中数组部分的题目。

2 训练

题目1：704二分查找

C++代码如下，

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int res = -1;
        int l = 0, r = nums.size() - 1;
        //找到>=target的下标
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        if (res == -1) return res;
        else return nums[res] == target ? res : -1;
    }
};

python3代码如下，

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        res = -1
        l, r = 0, len(nums) - 1

        while l <= r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                res = mid 
                r = mid - 1
            else:
                l = mid + 1
            
        if res == -1:
            return res 
        else:
            return res if nums[res] == target else -1

题目2：27移除元素

C++代码如下，

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        for (int j = 0; j < nums.size(); ++j) {
            if (nums[j] != val) nums[i++] = nums[j];
        }
        return i;
    }
};

python3代码如下，

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        return i

题目3：977有序数组的平方

C++代码如下，

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        //从最大数开始排
        int n = nums.size();
        int i = 0, j = n - 1;
        vector<int> res(n);

        int k = n - 1;
        while (i <= j) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                res[k] = nums[i] * nums[i];
                i++;
                k--;
            } else {
                res[k] = nums[j] * nums[j];
                j--;
                k--;
            }
        }
        return res;
    }
};

python3代码如下，

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i, j = 0, n - 1
        k = n - 1

        res = [0] * n 

        while i <= j:
            if nums[i] * nums[i] > nums[j] * nums[j]:
                res[k] = nums[i] * nums[i]
                i += 1
                k -= 1
            else:
                res[k] = nums[j] * nums[j]
                j -= 1
                k -= 1
        return res

题目4：209长度最小的子数组

C++代码如下，

//往大了讲，与子数组的最大和类似
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //滑动窗口法
        int res = INT_MAX;
        int s = 0;
        for (int r = 0, l = 0; r < nums.size(); ++r) {
            s += nums[r];
            while (s >= target) {
                res = min(res, r - l + 1);
                s -= nums[l++];
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

python3代码如下，

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        s = 0
        l, r = 0, 0
        n = len(nums)
        res = 1e10
        
        while r < n:
            s += nums[r]

            while s >= target:
                res = min(res, r - l + 1)
                s -= nums[l]
                l += 1

            r += 1

        return res if res != 1e10 else 0

题目5：59螺旋矩阵 II

C++代码如下，

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));

        int val = 1;
        for (int k = 0; k <= n / 2; k += 1) {

            //起点(0 + k, 0 + k)
            int x0 = k, y0 = k;
            int length = n - 2 * k;
            
            //向右
            for (int step = 0; step < length - 1; ++step) {
                int x = x0;
                int y = y0 + step;
                res[x][y] = val++; 
            }

            //向下
            x0 = x0;
            y0 = y0 + length - 1;
            for (int step = 0; step < length - 1; ++step) {
                int x = x0 + step;
                int y = y0;
                res[x][y] = val++;
            }

            //向左<--
            x0 = x0 + length - 1;
            y0 = y0;
            for (int step = 0; step < length - 1; ++step) {
                int x = x0;
                int y = y0 - step;
                res[x][y] = val++;
            }

            //向上
            x0 = x0;
            y0 = y0 - length + 1;
            for (int step = 0; step < length - 1; ++step) {
                int x = x0 - step;
                int y = y0;
                res[x][y] = val++;
            }

            //最后一步
            if (length == 1) {
                res[x0][y0] = val;
            }
        }
        return res;
    }
};

python3代码如下，

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0] * n for _ in range(n)]

        val = 1
        for k in range(n // 2 + 1):
            x0, y0 = k, k
            length = n - 2 * k

            #向右走-->
            for step in range(length-1):
                x, y = x0, y0 + step 
                res[x][y] = val 
                val += 1
            
            x0, y0 = x0, y0 + length - 1
            #向下走
            for step in range(length-1):
                x, y = x0 + step, y0 
                res[x][y] = val 
                val += 1
            
            x0, y0 = x0 + length - 1, y0
            #向左走<--
            for step in range(length-1):
                x, y = x0, y0 - step 
                res[x][y] = val 
                val += 1
            
            x0, y0 = x0, y0 - length + 1
            #向上走
            for step in range(length-1):
                x, y = x0 - step, y0 
                res[x][y] = val 
                val += 1
            
            if length == 1:
                res[x0][y0] = val 
                val += 1
        
        return res