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

977.有序数组的平方

tag： #双指针
leetcode 地址：977. 有序数组的平方

代码：

function sortedSquares(nums: number[]): number[] {
    const res = []
    let left = 0, right = nums.length - 1
    while(left <= right) {
        const leftVal = nums[left] * nums[left]
        const rightVal = nums[right] * nums[right]
        if(leftVal <= rightVal) {
            res.unshift(rightVal)
            right--
        }else {
            res.unshift(leftVal)
            left++
        }
    }
    return res
};

思路解析：

• 一开始我想的是找到中间的位置，从中间开始左右对比
• 即实际上是从小到大
• 那么也可以从大到小，即从左右两边向中间靠拢

209.长度最小的子数组

tag： #双指针 #滑动窗口
leetcode 地址：209. 长度最小的子数组

代码：

function minSubArrayLen(target: number, nums: number[]): number {
    let sum = 0, res = Infinity
    let i = 0, j = 0
    while(j < nums.length) {
        sum += nums[j]
        j++
        while( sum >= target) {
            res = Math.min(j - i, res)
            sum -= nums[i]
            i++
        }
    }
    return res === Infinity ? 0 : res
};

思路解析：

• 使用一个滑动窗口，用一个全局变量 sum 保存滑动窗口的值之和
• 每次移动右指针后，判断左指针是否可以被移动
• 使用一个全局变量 res 保存滑动窗口最短长度

59.螺旋矩阵Ⅱ

tag： #模拟 #螺旋矩阵 #顺时针
leetcode 地址：59. 螺旋矩阵 II

代码：

function generateMatrix(n: number): number[][] {
    const arr = new Array(n).fill(0).map(item => new Array(n).fill([]))
    let count = 1
    let left = 0;
    let right = n - 1;
    let top = 0;
    let bottom = n - 1;
    while(count <= n * n) {
        for(let i = left; i <= right; i++) {
            arr[top][i] = count++;
        }
        top++
        for(let i = top; i <= bottom; i++) {
            arr[i][right] = count++;
        }
        right--
        for(let i = right; i >= left; i--) {
            arr[bottom][i] = count++;
        }
        bottom--
        for(let i = bottom; i >= top; i--) {
            arr[i][left] = count++;
        }
        left++
    }
    return arr
}

思路解析：

• 因为该题目是 n * n，因此 while 的判断条件可以使用 count <= n * n
  • 倘若该题目是 m * n，则不能使用 while 条件判断结束
• 模拟顺时针画矩阵的过程:
  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上