第二天——数组（977.有序数组的平台、209.长度最小的子数组、59.螺旋矩阵）

977.有序数组的平方(opens new window)

学习链接

个人想法

解题代码

1. 暴力map sort

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    let newNums = nums.map(item => item > 0 ? item : (item * -1)).sort((a,b)=>a-b)
    return newNums.map(item => item * item)
};

1. 双指针法

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    let left = 0
    let right = nums.length - 1
    let ans = []
    while (left <= right){
        if(nums[left] * nums[left]> nums[right] * nums[right]){
            ans.unshift(nums[left]*nums[left])
            left ++
        } else {
            ans.unshift(nums[right]*nums[right])
            right --
        }
    }
    return ans
};

// 优化： array.unshift 性能太垃圾，可以array.push 再 reverse

209.长度最小的子数组

学习链接

个人想法

1. 暴力遍历，从开头i开始，找寻满足条件的数组长度，遍历后取Math.min

2. 滑动窗口，找到一个合适的数组长度后一直移动这个窗口，直到找到最合适的

解题思路

1. 暴力遍历

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let ans = Infinity
    for(let i = 0; i < nums.length; i++){
        let sum = 0;
        for(let j = i; j<nums.length; j++){
            sum += nums[j]
            if(sum >= target){
                ans = Math.min(ans, j - i + 1)
                break;
            }
        }
    }
    return ans === Infinity ? 0 : ans
};

1. 滑动窗口，妙点在于一直移动窗口位置

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
   let ans = Infinity
   let i = 0;
   let j =0;
   let sum = 0
   while(j < nums.length){
    sum += nums[j]
    while(sum >= target){ // 注意这里用while每次计算，第一次写这里出现问题
        ans = Math.min(ans, j - i + 1)
        sum -= nums[i]
        i++
    }
    j++
   }
   return ans === Infinity ? 0 :ans
};

相关问题

/**
 * @param {number[]} fruits
 * @return {number}
 */
var totalFruit = function(fruits) {
    let ans = 0;
    let i = 0;
   
    let n = 0; // 记录bucket[0]上次的位置
    let bucket = [fruits[i]]
    for(let j = 0; j < fruits.length; j++){
        if(!bucket.includes(fruits[j])){
            if(bucket.length === 1){
                bucket.push(fruits[j])
            } else{
                i = n
                bucket[0] = fruits[j-1]
                bucket[1] = fruits[j]
            }
        }
        if(fruits[j] !== fruits[n]){
            n = j // 更新bucket[0]上次的位置
        }
        ans = Math.max(ans,j-i+1)
    }
    return ans
};

59.螺旋矩阵II

学习链接

个人思路

解题代码

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let x = 0;
    let y = 0
    let loop = Math.floor(n/2) // 旋转次数
    let mid = Math.floor(n/2) // 中间值位置，n为偶数就没有，n为奇数单独赋值
    let offset = 1 // 每层填几个数
    let count = 1 // 填的数字
    let res = new Array(n).fill(0).map(()=>new Array(n).fill(0))
    while( loop -- ){
        let row = x;
        let col = y
        // 第一行从左到右
        for(col;col < n-offset; col++){
            res[row][col] = count ++ 
        }
        // 右边从上到下
        for(row; row < n-offset; row++){
            res[row][col] = count ++ 
        }
        // 模拟填充下行从右到左(左闭右开)
        for (; col > y; col--) {
            res[row][col] = count++;
        }
        // 模拟填充左列从下到上(左闭右开)
        for (; row > x; row--) {
            res[row][col] = count++;
        }
        x++
        y++
        offset += 1
    }
    if(n%2===1){
        res[mid][mid] = count
    }
    return res
};