代码随想录算法训练营第2天 | 977.有序数组的平方 、209.长度最小的子数组、59.螺旋矩阵II

发布于 2022-11-19  430 次阅读


977. 有序数组的平方 - 力扣(LeetCode)

以下思路为经典反例


思路:因为刚做过27. 移除元素 - 力扣(LeetCode),所以第一时间就想到了用快慢指针做这道题,思路很简单,同样也是两个指针,快指针负责遍历,慢指针负责收集,不过这次要求返回一个vector,所以我们要新建一个cnt大小的vector并且赋值为-1(因为前面的数据经过平方以后不可能小于0,这边为了与下面的a[slow++]配合,其实这不是不要的,只是比较简单明了),后面快指针遇到和慢指针一样的就忽略,和慢指针不一样的就让慢指针收集,这样就保证慢指针中收集到的都是不重复的数字

我的AC代码

(虽然AC了,但貌似会错意了,阴差阳错,题目不要求数字不重复)

// 时间复杂度O(n + nlog n) 空间复杂度O(n)
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int cnt = nums.size();
        for(int i = 0; i < cnt; ++i) {
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(), nums.begin() + cnt);
        vector<int>a(cnt,-1);
        int slow = 0;
        int fast = 0;
        for(fast = 0; fast < cnt; ++fast) {
            if(nums[fast] == a[slow]) {
                ++fast;
            }
            else {
                a[slow++]=nums[fast];
            }
        }
        return a;
    }
};

我的AC代码2

以下为正确思路,看了标准答案以后写的

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int cnt = nums.size();
        for(int i = 0; i < cnt; ++i) {
            nums[i] = nums[i] * nums[i];
        }
        vector<int>a(cnt,-1);
        int l = 0;
        int r = cnt-1;
        while(l <= r) {
            if(nums[l] <= nums[r]) {
                a[--cnt] = nums[r];
                --r;
            }
            else {
                a[--cnt] = nums[l];
                ++l;
            }
        }
        return a;
    }
};

标准答案

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j,因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

209. 长度最小的子数组 - 力扣(LeetCode)

思路:因为以前做过,所以第一时间想到了滑动窗口,即一个指针负责右端,一个指针负责左端,当总和小于target的时候,右端不停向右移动,直到总和大于target,然后此时再让左端指针不停向右移动(不要忘了减数据),力图找出最小的连续子数组长度,第一次没AC是因为忘记无解的时候返回0了,很尴尬

我的AC代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int slow = 0;
        int fast = 0;
        int cnt = nums.size();
        int ans = 1e5 + 10;
        for(fast = 0;fast < cnt; ++fast) {
            sum += nums[fast];
            while(sum >= target) {
                ans = min(ans, fast - slow + 1);
                sum -= nums[slow];
                slow++;
            }
        }
        if(ans == 1e5 + 10) {
            ans = 0;
        }
        return ans;
    }
};

标准答案

// 滑动窗口法
// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
            }
        }
        // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

59. 螺旋矩阵 II - 力扣(LeetCode)

思路:这题目第一眼很懵逼,但是思路还是简单的,只要坚持左闭右开的原则,顺时针画一遍就行了,主要是边界处比较难处理,想得挺久的

此处借用一下carl哥的图,这样更易于理解

我的AC代码

//时间复杂度O(n2),空间复杂度O(n2) 感觉也算遍历二维矩阵了吧
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,1));
        int end = n*n;
        int r = 0;
        int c = 0;
        int q = 1;
        if(1 == n) {
            return ans;
        }
        for(int i = 0; i <= end; ) {
            while(c <= (n - q - 1)) {
                ++i;
                ans[r][c] = i;
                ++c;
                if(end == i)
                {
                    return ans;
                }
            }
            while(r <= (n - q - 1)) {
                ++i;
                ans[r][c] = i;
                ++r;
                if(end == i)
                {
                    return ans;
                }
            }
            while(c >= q) {
                ++i;
                ans[r][c] = i;
                --c;
                if(end == i)
                {
                    return ans;
                }
            }
            while(r >= q) {
                ++i;
                ans[r][c] = i;   
                --r;
                if(end == i)
                {
                    return ans;
                }
            }
            ++r;
            ++c;
            ++q;
            if((end - 1) == i){
                ans[r][c] = end;
                return ans;
            }
        }
        return ans;
    }
};

附一个vector初始化二维数组的办法

// 初始化一个 二维的matrix, 行M,列N,且值为0
vector<vector<int>> matrix(M,vector<int>(N));
// 等价于下面的
vector<vector<int> > matrix(M); 
for(int i=0;i<M;i++) {
    matrix[i].resize(N);
}
// 等价于下面的
vector< vector<int> > matrix;
matrix.resize(M);// M行
for(int i=0;i<matrix.size();i++){
    matrix[i].resize(N);// 每一行都是N列
}

// 初始化一个 二维的matrix, 行M,列N,且值自定义为data;
vector<vector<int>> matrix(M,vector<int>(N,data));

我和carl哥代码的最大区别就是我的终止条件不是转几圈,而是数字全部赋完,这也导致一个问题,就是n为奇数时最后一个数字可能无法赋值,循环就永远都无法结束,得加入特判

标准答案

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次,例如n为奇数3,那么loop = 1 只是循环一圈,矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候,起始位置要各自加1, 例如:第一圈起始位置是(0, 0),第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};