【算法训练营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;
    }
};

看完代码随想录后的想法

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

原文地址：http://www.cnblogs.com/BarcelonaTong/p/16790226.html