跳到主要内容

数组

二分法​

题号704. 二分查找

什么时候用二分法​

题目的前提有有序数组、无重复元素

二分法写法中有两种写法

  1. 左闭右闭
  2. 左闭右开
  3. 左开右闭(不常用)

写法的选择​

​ 补充个人经验，如果题目要求是问某个值在不在区间里，用左闭右闭区间(while l <= r)，每个mid做大于、小于、等于三次判断，在等于时输出，循环结束未输出说明不在区间里；如果题目要求“找到第一个大于/小于x的下标”，用左闭右开区间(while l < r)，每个mid做大于、小于等于两次判断，不在循环体里输出，循环结束返回l或r(l=r，不要返回mid)，就是所求下标。

写法一 左闭右闭​
/* 方法一：使用左閉右閉*/

function search(nums: number[], target: number): number {
   // right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
    let mid, left = 0, right = nums.length - 1;
    // 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
    while (left <= right) {
        // 位运算 + 防止大数溢出
        mid = left + ((right - left) >> 1);
        // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1；如果右边界更新为mid，那中间数还在下次查找范围内
        if (nums[mid] > target) {
            right = mid - 1;  // 去左面闭区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右面闭区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};
写法二 左闭右开​
/* 方法二：使用左閉右開*/

function search(nums: number[], target: number): number {
  // right是数组最后一个数的下标+1，nums[right]不在查找范围内，是左闭右开区间
    let mid, left = 0, right = nums.length;    
    // 当left=right时，由于nums[right]不在查找范围，所以不必包括此情况
    while (left < right) {
        // 位运算 + 防止大数溢出
        mid = left + ((right - left) >> 1);
        // 如果中间值大于目标值，中间值不应在下次查找的范围内，但中间值的前一个值应在；
        // 由于right本来就不在查找范围内，所以将右边界更新为中间值，如果更新右边界为mid-1则将中间值的前一个值也踢出了下次寻找范围
        if (nums[mid] > target) {
            right = mid;  // 去左区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};

移除元素​

题号27. 移除元素

思考

  1. 这道题没有要求返回数组，是因为数组中的元素无法真正删除，只能靠后一个元素覆盖前一个元素。
  2. 双指针法(快慢指针法)在数组和链表中是很常见的，很多考察数组和链表的问题都可以使用双指针法解决
解法一 暴力解法​
function removeElement(nums: number[], val: number): number {
    // 暴力解法
    let size = nums.length
    for(let i=0;i<size;i++){
        if(nums[i]===val){ // 发现需要移除的元素，就将数组集体向前移动一位
                for (let j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
    }
    return size
};
解法二 快慢指针​
function removeElement(nums: number[], val: number): number {
// 快慢指针
    let slow = 0
    for(let fast = 0;fast<nums.length;fast++){
        if(nums[fast]!==val){
            nums[slow++]=nums[fast]//这一行其实是简化了写法
            /* 
            可以理解成
            nums[slow]=nums[fast]
            slow++
            */
        }
    }
    return slow
};

有序数组的平方​

题号977. 有序数组的平方

思考

  1. 一开始直接想到暴力法，直接把所有算出来之后用sort排序就可以了
  2. 没有想到双指针，要想到双指针需要了解因为题目出现负数所以其实数组的趋势是先下降在上升所以可以左右指针
解法一 暴力解法​
function sortedSquares(nums: number[]): number[] {
    for(let i = 0;i<nums.length;i++){
        nums[i] = nums[i]**2
    }
    nums.sort((a,b)=>a-b)
    return nums
};
解法二 双指针​
function sortedSquares(nums: number[]): number[] {
    const ans: number[] = [];
    let left = 0,
        right = nums.length - 1;

    while (left <= right) {
        // 右侧的元素不需要取绝对值，nums 为非递减排序的整数数组
        // 在同为负数的情况下，左侧的平方值一定大于右侧的平方值
        if (Math.abs(nums[left]) > nums[right]) {
            // 使用 Array.prototype.unshift() 直接在数组的首项插入当前最大值
            ans.unshift(nums[left] ** 2);
            left++;
        } else {
            ans.unshift(nums[right] ** 2);
            right--;
        }
    }

    return ans;
};

长度最小的子数组​

题号209. 长度最小的子数组

思考

  1. 暴力解法，两个for循环第二for循环中的变量以设成i，这样就是一个区段了。后续遍历就行了
  2. 滑动窗口（没想到）

什么是滑动窗口​

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

实现滑动窗口，主要确定如下三点：

  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。

解法一 暴力解法​
function minSubArrayLen(target: number, nums: number[]): number {
    let result = Infinity; // 初始值设置为无穷大
    let sum = 0;
    let subLength = 0;
    for (let i = 0; i < nums.length; i++) {
        sum = 0;
        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum >= target) {
                subLength = j - i + 1;
                result = Math.min(result, subLength); // 更新为更短的子序列长度
                break;
            }
        }
    }
    return result === Infinity ? 0 : result; // 如果 result 仍然是无穷大，说明没有符合条件的子序列，返回 0
}

解法二 滑动窗口​
function minSubArrayLen(target: number, nums: number[]): number {
    let left: number = 0, right: number = 0;
    let res: number = nums.length + 1;
    let sum: number = 0;
    while (right < nums.length) {
        sum += nums[right];
        if (sum >= target) {
            // 不断移动左指针，直到不能再缩小为止
            while (sum - nums[left] >= target) {
                sum -= nums[left++];
            }
            res = Math.min(res, right - left + 1);
        }
        right++;
    }
    return res === nums.length + 1 ? 0 : res;
};

螺旋矩阵​

题目59. 螺旋矩阵 II

思考

  1. 这道题目最重要的是有循环不变量
function generateMatrix(n: number): number[][] {
    let loopNum: number = Math.floor(n / 2);
    const resArr: number[][] = new Array(n).fill(1).map(i => new Array(n));
    let chunkNum: number = n - 1;
    let startX: number = 0;
    let startY: number = 0;
    let value: number = 1;
    let x: number, y: number;
    while (loopNum--) {
        x = startX;
        y = startY;
        while (x < startX + chunkNum) {
            resArr[y][x] = value;
            x++;
            value++;
        }
        while (y < startY + chunkNum) {
            resArr[y][x] = value;
            y++;
            value++;
        }
        while (x > startX) {
            resArr[y][x] = value;
            x--;
            value++;
        }
        while (y > startY) {
            resArr[y][x] = value;
            y--;
            value++;
        }
        startX++;
        startY++;
        chunkNum -= 2;
    }
    if (n % 2 === 1) {
        resArr[startX][startY] = value;
    }
    return resArr;
};
方法二​
function generateMatrix(n: number): number[][] {
    let l=0,r=n-1,t=0,b=n-1,num=1,tar=n*n
    let mat = new Array(n).fill(1).map(i=>new Array(n))
   while(num <= tar){
            for(let i = l; i <= r; i++) mat[t][i] = num++; // left to right.
            t++;
            for(let i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.
            r--;
            for(let i = r; i >= l; i--) mat[b][i] = num++; // right to left.
            b--;
            for(let i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
            l++;
        }
        return mat;
};