Algorithm training camp DAY2_Squaring of ordered arrays, subarrays with the smallest length, spiral matrix II

LeetCode | 977. Squaring an Ordered Array

topic:

Given an array of integers nums sorted in non-decreasing order, return a new array consisting of the square of each number, also sorted in non-decreasing order.

977. Squaring an Ordered Arrayhttps://leetcode.cn/problems/squares-of-a-sorted-array/

think:

  • When I first thought about the solution, I didn't think about how to deal with the situation where the square of the negative number becomes larger, so that "0" will be stuck in the middle of the numbers;
  • Later, I thought that the array may have negative numbers, so after squaring, it shows that the two ends are large and the middle is small. Therefore, the double pointer method can be used to compare the sizes from the two ends, and then take them out and put them into the final array;

answer:  

1. The first way of writing (for loop)

// Solution one
var sortedSquares = function(nums) {
    // set two pointers
    let right = nums.length - 1;
    let left = 0;
    // new array
    let newArr = new Array()
    for(let i = nums.length - 1; i >= 0; i--){
        if(nums[left]*nums[left] < nums[right]*nums[right]){
            newArr[i] = nums[right]*nums[right];
            right--;
        }else{
            newArr[i] = nums[left]*nums[left];
            left++;
        }
    }
    return newArr
}

2. The second way of writing (while loop)

// Solution 2 (Small understanding is different, the difference is not big)
var sortedSquares = function(nums) {
    // create a new array
    let newArr = new Array()
    let i = nums.length -1;
    let left = 0;
    let right = nums.length -1;
    while(left <= right){
        if(nums[left]*nums[left] - nums[right]*nums[right] < 0){
            newArr[i--] = nums[right]*nums[right]
            right--;
        }else{
            newArr[i--] = nums[left]*nums[left]
            left++;
        }
    };
    return newArr
};

Summary of double-pointer method ideas:

  • Question 27 also uses the double-pointer method to remove elements. Put the two pointers on the same side, one fast and one slow. The slow pointer is used to remember the position, and the fast pointer is used to find new elements;
    • And this question is to put two pointers on both sides, compare the two pointers at the same time, and take out the ones that meet the conditions first;
    • If the two pointers are placed on the same side in this question, there will be many more comparisons, and errors and omissions are prone to occur;
  • At present, I think that double pointers can be considered when comparison is required, and at the same time, think about the shape of the model that needs to be compared, so as to determine the position of the pointer;

LeetCode | 209. Minimum Length Subarray

topic:

Given an array of n positive integers and a positive integer target. Find the continuous subarray [numsl, numsl+1, ..., numsr-1, numsr] with the smallest length satisfying its sum ≥ target in this array, and return its length. Returns 0 if no matching subarray exists.

209. Minimum Length Subarrayhttps://leetcode.cn/problems/minimum-size-subarray-sum/

think:

  • I have never been exposed to the idea of ​​sliding windows, and I have seen few questions. When I saw this question, I was completely confused. What puzzled me were:
    • What is a continuous subarray? Must the value of each element be continuous?
    • How to filter out all arrays greater than or equal to target, and then compare them?
  • After watching the two videos, I still have doubts:
    • Why does the combination of for+while reduce the time complexity?
    • Can you really ensure that the screening does not leak?
  • I finally figured it out after drawing a picture, and I can only say it’s wonderful;

answer:

var minSubArrayLen = function (target, nums) {
    // let result = Number.MAX_VALUE;
    let result = nums.length + 1;
    let sum = 0;
    // set start pointer
    let i = 0;
    // set termination pointer
    for(let j = 0; j < nums.length; j++){
        sum += nums[j];
        while(sum >= target){
            let sumL = j - i + 1;
            result = Math.min(result, sumL);
            sum -= nums[i];
            i++;
        }
    }
    // Note that when there is no condition, it needs to return 0
    if(result == nums.length + 1){
        return 0
    }else{
        return result
    }
}

Summary of sliding window ideas:

  • It is a kind of double-pointer method. Compared with the previous two double-pointer method questions, this question is to keep the "window" in the middle of the two pointers in a state that satisfies ≥ target, and then move it;
  • Compared with the two for loops of the violent solution, an element only needs to be operated twice, so the time complexity is O(2n)→O(n);

LeetCode | 59. Spiral Matrix II

topic:

Given a positive integer n, generate an n×n square matrix matrix containing all elements from 1 to n², and the elements are spirally arranged in clockwise order.

59. Spiral Matrix IIhttps://leetcode.cn/problems/spiral-matrix-ii/

think:

  • Types that have not been touched, and are not clear about two-dimensional arrays before;
  • After understanding, I know that it is a mock question, and the overall difficulty is not too big, just be careful not to be confused, and clearly write the judgment conditions;

answer:

var generateMatrix = function(n) {
    // Set initial position coordinates
    let startX = startY = 0;
    // Set the number of turns of the loop
    let loop = 1
    let count = 1
    // Create a 2D array
    let nums = new Array(n).fill(0).map(()=>new Array(n).fill(0))
    // As long as the number of cycles of the cycle is less than n/2, the cycle must continue
    while(loop <= n/2){
        let i = startX;
        let j = startY;
        // first edge
        for(; j < n - loop; j++){
            nums[startX][j] = count++
        }
        // second side
        for(; i < n - loop; i++){
            nums[i][j] = count++
        }
        // third side
        for(; j > startY; j--){
            nums[i][j] = count++
        }
        // fourth side
        for(; i > startX; i--){
            nums[i][startY] = count++
        }
        // after one lap
        startX++;
        startY++;
        loop++;
    }
    // if odd number circle
    if(n % 2 == 1){
        nums[startX][startY] = count
    }
    return nums
}

Summary of ideas:

  • Adhere to the principle of loop invariance;
  • Find the right method to traverse, don't wrap yourself in it;

 

Tags: Algorithm leetcode

Posted by bloo on Sat, 31 Dec 2022 14:42:36 +0300