• 欢迎光临~

【算法训练营day2】LeetCode977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵II

开发技术 开发技术 2022-10-13 次浏览

【算法训练营day2】LeetCode977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵II

LeetCode977. 有序数组的平方

题目链接:977. 有序数组的平方

初次尝试

上来看到建议使用双指针,于是就朝着双指针开始思考,第一想法是一定要找到数组元素正负分界的位置,然后双指针一个向左,一个向右比大小更新。这里有一点思维定势了,以为输出的结果数组的大小是未知的,所以不能从尾部更新,其实输出和输入数组大小是一样的,这里引以为戒。然后就开始coding,从中间展开的双指针写起来会更麻烦一点,首先需要一个for循环找到正负分界的位置,其次在双指针展开的过程中,不好判断哪边先走到数组尽头了,可能产生数组下标越界的问题,所以第一次编码比较保守,没有刻意为了简洁缩写,最后一遍ac。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int numslen = nums.size(), i;
        vector<int> ans(numslen);

        for (i = 0; i < numslen; i++) {
            if(nums[i] >= 0) break;
        }

        int left = i - 1, right = i, count = 0;
        while (left > -1 || right < numslen) {
            if (left > -1 && right < numslen) {
                if (-nums[left] >= nums[right]) {
                    ans[count] = nums[right] * nums[right];
                    count++;
                    right++;
                }
                else {
                    ans[count] = nums[left] * nums[left];
                    count++;
                    left--;
                }
            }
            else if (left == -1) {
                ans[count] = nums[right] * nums[right];
                count++;
                right++;
            }
            else if (right == numslen) {
                ans[count] = nums[left] * nums[left];
                count++;
                left--;
            }
        } 

        return ans;
    }
};

然后感觉while循环里这些if应该是可以合并的,于是有了下面这段代码,但是报了ERROR: AddressSanitizer: heap-buffer-overflow这样的错,好像是数组下标越界了,思考后感觉唯一可能越界的就是这里(left == -1 || -nums[left] >= nums[right]),但是我记得C++语法中逻辑或运算有短路机制?这里留一个疑问。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int numslen = nums.size(), i;
        vector<int> ans(numslen);

        for (i = 0; i < numslen; i++) {
            if(nums[i] >= 0) break;
        }

        int left = i - 1, right = i, count = 0;
        while (left > -1 || right < numslen) {
            if (left == -1 || -nums[left] >= nums[right]) {
                ans[count] = nums[right] * nums[right];
                count++;
                right++;
            }
            else if (right == numslen || -nums[left] < nums[right]) {
                ans[count] = nums[left] * nums[left];
                count++;
                left--;
            }
        } 

        return ans;
    }
};

看完代码随想录后的想法

上文交代过了,已知输出数组大小,确实可以从最后更新数组,而且从两头开始的双指针更容易判定结束的条件,也不需要考虑数组下标越界的情况,coding不难,代码比较简洁,一遍ac。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int numslen = nums.size();
        vector<int> ans(numslen);

        int left = 0, right = numslen - 1;
        while (left <= right) {
            if (nums[left] * nums[left] < nums[right] * nums[right]) {
                ans[numslen-1] = nums[right] * nums[right];
                numslen--;
                right--;
            }
            else {
                ans[numslen-1] = nums[left] * nums[left];
                numslen--;
                left++;
            }
        }

        return ans;
    }
};

LeetCode209. 长度最小的子数组

题目链接:209. 长度最小的子数组

初次尝试

此题仍未完全理解,先把代码放上来,等理解透彻了再更新此处。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int numsSize = nums.size();
        int left = 0, right = 0, sum = 0, ans = INT_MAX;

        while (right < numsSize) {
            sum += nums[right];
            if (sum >= target) {
                ans = min(ans, right - left + 1);
                left++;
                right = left;
                sum = 0;
            }
            else right++;
        }

        return ans == INT_MAX? 0 : ans;
    }
};

看完代码随想录后的想法

听完视频晕晕乎乎的,能一遍ac,但是仍然感觉理解的不够细致。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int numsSize = nums.size();
        int left = 0, right = 0, sum = 0, ans = INT_MAX;

        for (; right < numsSize; right++) {
            sum += nums[right];
            while (sum >= target) {
                ans = min(ans, right - left + 1);
                sum -= nums[left++];
            }
        }

        return ans == INT_MAX ? 0 : ans;
    }
};

LeetCode59. 螺旋矩阵II

题目链接:59. 螺旋矩阵II

初次尝试

第一想法是一个for循环遍历1到n的平方,然后i和j为矩阵下标,每次不是i变化1就是j变化1,所以只需要找到i和j变化的规律就可以完成赋值,试了一下,没有找到很简洁的规律。

一瞬间突然有思路了,可以把矩阵下标当成坐标,组合成一个坐标系,通过正方形矩阵两条对角线划分出四个区域,每个区域是同样的坐标变化,这样就能比较直观的观察并计算出规律,一遍ac。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int row = 0, col = 0;

        for (int num = 1; num <= n * n; num++) {
            ans[row][col] = num;
            if (row <= col && col < n - 1 - row) {
                col++;
            }
            else if (row < col && col >= n - 1 - row) {
                row++;
            }
            else if (row >= col && col > n - 1 - row) {
                col--;
            }
            else if (row > col && col <= n - 1 - row) {
                if (row == col + 1) {
                    col++;
                }
                else {
                    row--;
                }
            }
        }

        return ans;
    }
};

看完代码随想录后的想法

看完题解,感觉题解的方法思考起来更具有普遍性,而我的算法是通过找规律合并了一些情况最终减少了代码量,但是增加了不少思考量。

喜欢 (0)