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:代码随想录）
零、常规数组操作
代码语言：javascript复制// 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));一、二分查找
力扣链接：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;
};二、移除元素
力扣链接：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、题解
使用双指针法：
代码语言：javascript复制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;
};三、有序数组的平方
力扣链接：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、题解
先将数字乘以平方，数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。然后使用双指针。
代码语言：javascript复制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;
};四、长度最长的子数组
力扣链接：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记录最小的窗口大小。
代码语言：javascript复制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;
};五、螺旋矩阵 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中的接口，我们使用模拟法，模拟螺旋的形态：
代码语言：javascript复制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;
};
