• TypeScript算法题实战——数组篇（二分法、双指针、滑动窗口、螺旋矩阵的TS解法）

    TypeScript 是由微软开发的一款开源的编程语言，TypeScript 是 Javascript 的超集，遵循最新的 ES6、ES5 规范，TypeScript 扩展了 JavaScript 的语法。TypeScript 更像后端 Java、C#这样的面向对象语言，可以让 JavaScript 开发大型企业项目。谷歌也在大力支持 Typescript 的推广，谷歌的 angular2.x+ 就是基于 Typescript 语法，最新的 Vue 、React 也可以集成 TypeScript。Nodejs 框架中的 Nestjs、midway 中用的就是 TypeScript 语法。

    本系列博文将通过一些力扣算法题目，边学习TypeScipt边实战算法，这篇将通过一些经典算法题熟悉TS语言数组的一些基本操作。（部分算法思想参考于程序员Carl:代码随想录）

    目录

    零、常规数组操作

    // arr 初始化
let arr:Array<number> = new Array<number>();
// let arr = [1, 2, 3];
 
arr = [1, 2, 3, 7, 5, 9, 1]; // 给数组直接赋值
console.log("数组", arr,  "长度为:", arr.length);
 
// 向数组中增加元素
console.log("向数组 尾 添加一个元素4, 修改后的数组长度为: " + arr.push(4));
console.log("向数组 头 添加一个元素0, 修改后的数组长度为: " + arr.unshift(0));
console.log(arr);
 
console.log("向数组下标为2插入 一个 元素 99: " + arr.splice(2, 0, 99));
console.log(arr);
console.log("向数组下标为2插入 3个 元素 88,77,66: " + arr.splice(2, 0, 88, 77, 66));
console.log(arr);
 
// 从数组中删除元素
console.log("从数组 尾 删除一个元素: " + arr.pop());
console.log("从数组 头 删除一个元素: " + arr.shift());
console.log(arr);
 
console.log("删除数组 下标为4 的元素: " + arr.splice(4, 1));
console.log(arr);
console.log("删除数组中从 下标为2开始后3个 元素: " + arr.splice(2, 3));
console.log(arr);
 
// 清空数组的几种方式
arr.length = 0;
arr = []; // 只是更改数组的引用地址, 原数组内存将等待垃圾回收
arr.splice(0, arr.length);
 
arr = [1, 2, 3, 7, 5, 9, 1];
// 获取数组中某个元素
console.log("获取数组 下标为0 的元素: " + arr[0]);
console.log("获取数组 下标为100 的元素: " + arr[100]); // 当该元素没有的时候, 会返回一个undefined类型
 
// 修改数组中的某个元素
arr[0] = 111;
// arr[-10] = 0; // 我们可以给一个非法下标赋值, 且仍然不会报错, 但我们并不推荐这么做, 这样会把一个数组类型转换为复杂类型
arr[10] = 999; // 当给一个超出当前数组长度的下标元素赋值时, 该数组将会自动补齐数组长度, 且中间未赋值的数组元素为undefined类型
console.log(arr, arr[9], arr.length);
 
// 查找
console.log("从数组中查找 [元素为3] 的下标: ", arr.indexOf(3));
console.log("从数组中查找 [元素为53] 的下标: ", arr.indexOf(53)); // 当找不到时会返回-1
 
console.log("数组中是否包含 值为3 的元素", arr.includes(3));
 
// 查找数组中(从左往右)第一个大于5的数组元素
let item:number = arr.find((val:number, index:number, array:Array<number>)=>{
    return val > 5;
});
console.log("数组中(从左往右)第一个大于5的数组元素", item);
// 查找数组中(从左往右)第一个大于5的数组元素的下标
let index:number = arr.findIndex((val:number, index:number, array:Array<number>)=>{
    return val > 5;
});
console.log("数组中(从左往右)第一个大于5的数组元素的下标", index);
 
// 排序
console.log("升序排列后的数组: ", arr.sort(function(a, b) {return a - b}));
console.log("降序排列后的数组: ", arr.sort(function(a, b) {return b - a}));
 
arr = [1, 99, 88, 111, 200, 4, 5, 7, 222, 555, 30];
console.log("按字符排序后的数组: ", arr.sort());
console.log("反转数组顺序", arr.reverse());
 
// 遍历数组
for(let i:number = 0; i < arr.length; i++) {
    console.log(arr[i]);
}
 
for(let i in arr) {
    console.log(`下标${i}, 元素${arr[i]}`);
}
 
for(let val of arr) {
    console.log(`元素${val}`);
}
 
// 迭代数组
arr.forEach((val:number, index:number, arr:Array<number>)=>{
    console.log(`元素:${val}, 下标${index}, 数组本身${arr}`);
});
 
let delArr:Array<number> = [1, 3, 5, 7, 12, 14, 19, 20, 25, 30];
// 删除数组中符合条件的某几个元素
let delTempArr:Array<number> = [];
for(let i:number = 0; i < delArr.length; i++) {
    if(delArr[i] % 2 == 0) {
        delTempArr.push(delArr[i]);
    }
}
delArr = delTempArr;
console.log(delArr);
 
// 获取一个新数组, 该数组中的元素值原数组值的10倍
let arr1:Array<number> = arr.map((val:number, index:number, array:Array<number>)=>{
    return val * 10;
});
console.log(arr1);
 
// 获取一个新数组, 该数组中的元素为原数组中所有大于10的值
let arr2:Array<number> = arr.filter((val:number, index:number, array:Array<number>)=>{
    return val > 10;
});
console.log(arr2);
 
console.log(arr);
let sum = arr.reduce((total, val:number, index:number, array:Array<number>)=>{
    console.log(index, val, total);
    return total + val;
});
console.log("总和", sum);
 
// 判断该数组是否 每个元素都大于0, 该方法一旦判定为假将不会再迭代
let isHas:boolean = arr.every((val:number, index:number, array:Array<number>)=>{
    return val > 0;
});
console.log("判断该数组是否 每个元素都大于0", isHas);
// 判断该数组是否 每个元素都小于200
let isHas0:boolean = arr.every((val:number, index:number, array:Array<number>)=>{
    console.log(val < 200);
    return val < 200;
});
console.log("判断该数组是否 每个元素都小于200", isHas0);
 
// 判断该数组中是否 存在大于100的元素, 该方法一旦判定为真将不会再迭代
let isHas1:boolean = arr.some((val:number, index:number, array:Array<number>)=>{
    console.log(val > 100);
    return val > 100;
});
console.log("该数组中是否存在大于100的元素", isHas1);
 
// 连接两个数组到一个新数组
let arr0 = [-1, 2, 4, 6, 7, 999];
let arrConcat:Array<number> = arr.concat(arr0);
console.log("arr和arr0连接后的新数组", arrConcat);
 
// 将数组元素填充为某个值, 可用作初始化数组
let arr3:Array<number> = new Array<number>(10);
arr3.fill(1);
console.log("数组每个元素初始化为1", arr3);
 
// 将数组元素转换为字符串
let arr4:Array<string> = ["hello", ",", "my" , " ", "word!"];
console.log("将数组元素转换为字符串", arr4.join(""), "用逗号连接成字符串", arr4.join(","));
// 将字符串转换为数组
let str:string = "你好,我的朋友!";
console.log(str.split(""));
 
// 获取子数组
let arr6 = ["111", "333", "str", "is", "fff", "sos"];
console.log("下标从0到3的子数组", arr6.slice(0, 4));

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155

    一、二分查找

    力扣链接：https://leetcode.cn/problems/binary-search/

    1.1、题目描述

    给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

    1.2、示例

    IO示例：

    示例 1:

    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4

    示例 2:

    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1

    1.3、题解

    数组为有序数组，同时题目还强调数组中无重复元素，所以可以直接用传统二分法。但是要注意的是 ts的number类型如left: number不是int类型，所有数字都是浮点数，而没有int或者float类型，所以我们需要使用Math.floor()向下取整。

    function search(nums: number[], target: number): number {
    let index: number = -1;
    let left: number = 0;
    let right: number = nums.length - 1;
    while(left <= right){
        let middle: number = Math.floor((left + right) / 2);  // Math.floor向下取整
        if(nums[middle] > target){
            right = middle - 1;
        }
        else if(nums[middle] < target){
            left = middle + 1;
        }
        else{
            index = middle ;
            break;
        }
    }
    return index;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    二、移除元素

    力扣链接：https://leetcode.cn/problems/remove-element/

    2.1、题目描述

    题目描述：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
    不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    2.2、示例

    示例 1：
    输入：nums = [3,2,2,3], val = 3
    输出：2, nums = [2,2]
    解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

    示例 2：
    输入：nums = [0,1,2,2,3,0,4,2], val = 2
    输出：5, nums = [0,1,4,0,3]
    解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

    2.3、题解

    使用双指针法：

    function removeElement(nums: number[], val: number): number {
    let left: number = -1;
    let right: number = -1;
    let res: number = 0;

    while(right < nums.length-1){
        right ++;
        if(nums[right] != val){
            res ++;
            left ++;
            nums[left] = nums[right];
        }
    }

    return res;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    三、有序数组的平方

    力扣链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

    3.1、题目描述

    给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

    3.2、示例

    示例 1：
    输入：nums = [-4,-1,0,3,10]
    输出：[0,1,9,16,100]
    解释：平方后，数组变为 [16,1,0,9,100]
    排序后，数组变为 [0,1,9,16,100]

    示例 2：
    输入：nums = [-7,-3,2,3,11]
    输出：[4,9,9,49,121]

    3.3、题解

    先将数字乘以平方，数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。然后使用双指针。

    function sortedSquares(nums: number[]): number[] {
    let left: number = 0;
    let right: number = nums.length-1;
    let res: number[] = [];
    for(let i: number = 0; i < nums.length; i++){
        nums[i] = nums[i] * nums[i];
    }
    for(let i: number = nums.length - 1; i >= 0; i--){
        if(nums[left] < nums[right]){
            res[i] = nums[right];
            right --;
        }
        else{
            res[i] = nums[left];
            left ++;
        }
    }
    return res;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    四、长度最长的子数组

    力扣链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

    4.1、题目描述

    给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

    4.2、示例

    这里是引用
    示例 1：
    输入：target = 7, nums = [2,3,1,2,4,3]
    输出：2
    解释：子数组 [4,3] 是该条件下的长度最小的子数组。

    示例 2：
    输入：target = 4, nums = [1,4,4]
    输出：1

    示例 3：
    输入：target = 11, nums = [1,1,1,1,1,1,1,1]
    输出：0

    4.3、题解

    使用滑动窗口法，本质上也是双指针的操作，tmplength记录滑动窗口目前的大小（用right-left其实也可以直接计算），sum记录滑动窗口当前的和值，minlength记录最小的窗口大小。

    function minSubArrayLen(target: number, nums: number[]): number {
    let left: number = 0;
    let right: number = 0;
    let minlength: number = -1;
    let sum: number = 0;
    let tmplength: number = 0;
    while(right < nums.length){
       sum = sum + nums[right];
       right ++;
       tmplength ++;
       while(sum >= target){
           if(minlength == -1)
            minlength = tmplength;
          else if(minlength > tmplength){
              minlength = tmplength;
          }
          sum = sum - nums[left];
          left ++;
          tmplength --;
       }
    }
    if(minlength == -1) 
        return 0;
    return minlength;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    五、螺旋矩阵 II

    力扣链接：https://leetcode.cn/problems/spiral-matrix-ii/

    5.1、题目描述

    给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

    5.2、示例

    示例 1：
    在这里插入图片描述
    输入：n = 3
    输出：[[1,2,3],[8,9,4],[7,6,5]]

    示例 2：
    输入：n = 1
    输出：[[1]]

    5.3、题解

    需要创建二维数组，这里使用到了Array在ts中的接口，使用方法可以详见：https://blog.csdn.net/qq_28550263/article/details/121201774
    我们使用模拟法，模拟螺旋的形态：

    function generateMatrix(n: number): number[][] {
    let top: number = 0;
    let bottom: number = n - 1;
    let left: number = 0;
    let right: number = n - 1;
    const resArr: number[][] = new Array(n).fill(1).map(i => new Array(n).fill(1));
    let k: number = 1 ;
    while(k < n * n + 1){
        for(let j = left; j <= right; j++, k++)  //从左到右
            resArr[top][j] = k;
        top ++;
        for(let i = top; i <= bottom; i++, k++) //从上到下
            resArr[i][right] = k;
        right --;
        for(let j = right; j >= left; j--, k++) //从右到左
            resArr[bottom][j] = k;
        bottom --;
        for(let i = bottom; i>= top; i--, k++) //从下到上
            resArr[i][left] = k;
        left ++;
    }
    return resArr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
  • 相关阅读:
    每日三题 9.09
    小程序实现后台数据交互及WXS的使用
    Java创建对象的最佳方式：单例模式（Singleton）
    CSS之hover的使用、+、~
    文心一言vsGPT-4全面对比
    如何将Linux上部署的5.7MySql数据库编码修改utf8（最新版）
    性能测试的概念到底是什么？---《跟着高楼学习性能测试--进阶高级性能工程师》系列
    树莓派部署YOLOv5目标检测（详细篇）
    c++23中的新功能之十七显示this的应用
    Project Reactor源码阅读-Scheduler
  • 原文地址：https://blog.csdn.net/air__Heaven/article/details/126977287