[Algorithm training camp day2] LeetCode977. Square of ordered array 209. Subarray with the smallest length 59. Spiral matrix II

[Algorithm training camp day2] LeetCode977. Square of ordered array 209. Subarray with the smallest length 59. Spiral matrix II

LeetCode977. Square of sorted arrays

Topic link: 977. Square of Sorted Arrays

first attempt

I saw the suggestion to use double pointers, so I started thinking about double pointers. The first idea was to find the position of the positive and negative boundaries of the array elements, and then one of the double pointers was to the left and the other to the right to update the size. There is a little bit of thinking here, thinking that the size of the output result array is unknown, so it cannot be updated from the tail. In fact, the output and input array sizes are the same, so take a warning here. Then start coding. It will be more troublesome to write the double pointer expanded from the middle. First, a for loop is needed to find the position of the positive and negative boundaries. Secondly, in the process of double pointer expansion, it is difficult to judge which side goes to the end of the array first. , which may cause the problem that the subscript of the array is out of bounds, so the first encoding is conservative, and there is no deliberate abbreviation for the sake of brevity, and the last pass is 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;
    }
};

Then I feel that these if s in the while loop should be merged, so I have the following code, but an error like ERROR: AddressSanitizer: heap-buffer-overflow is reported. It seems that the array subscript is out of bounds. After thinking about it, I feel that it is the only possibility. The out-of-bounds is here (left == -1 || -nums[left] >= nums[right]), but I remember there is a short-circuit mechanism for logical OR in C++ syntax? Here is a question.

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;
    }
};

Thoughts after reading the code

As explained above, knowing the size of the output array, it is indeed possible to update the array from the end, and the double pointers starting from both ends are easier to determine the conditions of the end, and there is no need to consider the situation that the array subscript is out of bounds, coding is not difficult, code comparison Concise, once again 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. Subarray with the smallest length

Topic link: 209. Minimum Length Subarray

first attempt

This question is still not fully understood, put the code up first, and then update it when you understand it thoroughly.

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;
    }
};

Thoughts after reading the code

After listening to the video, I feel dizzy, and I can ac again, but I still feel that my understanding is not detailed enough.

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. Spiral Matrix II

Topic link: 59. Spiral Matrix II

first attempt

The first idea is that a for loop traverses the square of 1 to n, and then i and j are the matrix subscripts. Each time either i changes by 1 or j changes by 1, so only need to find the law of i and j changes to complete the assignment, try After a while, I couldn't find a very simple rule.

In an instant, I have an idea. You can use the matrix subscripts as coordinates and combine them into a coordinate system. Four areas are divided by the two diagonals of the square matrix. Each area has the same coordinate change, so it can be more intuitive. Observe and calculate the law, again 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;
    }
};

Thoughts after reading the code

After reading the problem solution, I feel that the method of problem solving is more universal, and my algorithm combines some situations by finding rules and finally reduces the amount of code, but increases a lot of thinking.

Posted by qo2o on Thu, 13 Oct 2022 21:03:38 +0300