TS 类型体操 之 数组的用法与进阶(加法,减法,乘法)
# TS 类型体操 之 数组的用法与进阶(加法,减法,乘法)
之前《成为优秀的 TS 体操高手 之 TS 类型体操前置知识储备》提到了一下数组的用法,在 TS 中主要担任 计数器 的角色。用到的主要是数组的 length
属性
当时简单的讲了一下 。用到的就是 数组的 ['length']
属性就解决了
今天继续讲讲数组 计数器 的深入用法和进阶用法。用到的例题分别是:
# 5153 · IndexOf 和 5317 · LastIndexOf 题目详解
这 2 个题目的需求和 JS 的用法一样,就是获取指定内容在数组中的
索引
在开始之前先来个 JS 版实现看看是什么样的代码
function IndexOf(T, U) {
for (let i = 0; i < T.length; i++) {
// 1. 循环拿到每一项
const item = T[i]
// 2. 判断和U的关系
if (item == U) {
// 3. 相同的返回索引就可以了
return i
}
}
// 4. 如果循环结束了都没匹配到就返回 -1
return -1
}
2
3
4
5
6
7
8
9
10
11
12
13
14
换到 TS,由于我们没有 for 循环,想计算索引就必须借助额外的参数(数组 C,默认是[],也就是长度 0),每一次递归调用的时候数组都 push 一个 1,让数组长度来帮我们统计 当前循环的索引
而且因为我们的数组只是为了统计当前索引,所以我都是用 [1,1,1] 这种数组,自然 C extends 1[]
// 半成品答案
type IndexOf<T extends unknown[], U, C extends 1[] = []> =
T extends [infer F, ...infer R] ? (F extends U ? C['length'] : IndexOf<R, U, [...C, 1]>) : -1
2
3
上面的答案只能应对正常类型,下面的 2 个示例答案就不对了
// 答案是:2,程序运行结果是1
var TestCase1 = IndexOf<[string, 1, number, 'a'], number>
// 答案是:4,程序运行结果是0
var TestCase1 = IndexOf<[string, 1, number, 'a', any], any>
2
3
4
5
因为对于 TestCase1
来说 1 extends number 也是为true
。
对于TestCase2
来说,不等于 never 的都可以 extends 为 any
关于这个问题,可以看看之前写的 《TS 类型体操 之 extends,Equal,Alike 使用场景和实现对比》。深入了解一下 extends 背后的用法和特性
既然单纯的 extends 不能解决问题,那就直接上 Equal(当然不嫌麻烦也可以用 F extends U && U extends F 的方式,我嫌麻烦就简写了,这样会多了很多的三目运算的判断)。
// 正确答案
export type IndexOf<T extends unknown[], U, C extends 1[] = []> =
T extends [infer F, ...infer R] ? (Equal<F,U> extends true ? C['length'] : IndexOf1<R, U, [...C, 1]>) : -1
2
3
题外话:
注意我加了一个 export ,测试用例使用的时候也得加上
import { IndexOf } from './template'
因为 Equal 是工具类封装的,并非 TS 内置的方法,所以我们需要 import 进来 当这个 TS 文件导入了外部的模块时,你可以理解为当前的 TS 文件也被模块限制了(没 import 之前可以理解为全局)
LastIndexOf 解法
和 IndexOf 相比,LastIndexOf 区别是取到最后一个符合规范的索引,也就是要把数组完全循环完(IndexOf 是找到第一个符合的就立刻returen C['length']
了)
所以比起 IndexOf:计数器还得有C extends 1[] = []
,还得新增一个最后一次匹配的索引 L extends number = -1
要注意的点上面也都提到过了,就多加了一个 L 参数,答案就直接放出来了:
export type LastIndexOf<T, U, C extends 1[] = [], L extends number = -1> = T extends [infer F, ...infer Rest]
? Equal<U, F> extends true
? LastIndexOf<Rest, U, [...C, 1], C['length']> // 如果匹配到了,L记录为最新的索引
: LastIndexOf<Rest, U, [...C, 1], L> // 如果不匹配,L还是记录为上次的索引
: L
2
3
4
5
# 数组的加法 - 斐波那契数列
斐波那契数列是这样一个数列:1、1、2、3、5、8、13、21、34
F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*) 当前的数字 = 前面一位数字 + 前面 2 位的数字
实现的需求,传入一个位置,获取该位置对应的数列结果:
// 数列是: 1、1、2、3、5、8、13、21、34
type Result1 = Fibonacci<3> // 2
type Result2 = Fibonacci<8> // 21
2
3
解题思路
- 既然有指定位置,那 计数器 少不了
- 斐波那契数列也要实现一个
- 那么就涉及到 加法,加法的实现其实就是
[...arr1,...arr2]
- 如果需要加法,那么起码得有 2 个数 相加,题目给出只有一个变量,所以我们还得自己多加 2 个变量
- 那么就涉及到 加法,加法的实现其实就是
那就是要加 3 个参数,一个计数器,一个是 2 个数的加法
type Fibonacci<T extends number, C extends 1[] = [], N1 extends 1[] = [], N2 extends 1[] = [1]> =
T extends C['length'] ? N1['length'] : Fibonacci<T, [...C, 1], N2, [...N1, ...N2]>
2
解题细节:
- C 作为计数器(N1,N2 也是计数器),直接限制为元素只有 1 的数组了 所以
C extends 1[] = []
- N1 和 N2 对应的是数列上 F(N-2) 和 F(N-1)
- 当递归继续运行时,N1 的位置被赋上了 N2 的值;而
N2 = N1+N2
。加法就体现在[...N1, ...N2]
# 递归内存溢出问题与数组高阶用法
递归虽然好用,TS 的语法除了 in 循环多数都是靠递归了。不过递归有一个很明显的问题就是 内存溢出,看一道 MinusOne 题目的实现就能遇到了
# 2257 · MinusOne 题目实现
刚才斐波那契数列是加法,而这个是减法,而且只是减 1。只需要合理的利用计数器和比计数器数组多一位的数组,就能很简单的得出相邻的 2 个数字了
看懂这个实现应该没问题,N 在初始的时候就把 C 多一位,所以 N 和 C 的 length 数是相邻的 2 个数(看不懂的还得在看看上面的内容)
type MinusOne<T extends number, C extends 1[] = [], N extends 1[] = [1]> =
T extends N['length'] ? C['length'] : MinusOne<T, [...C, 1], [...N, 1]>
2
然而有这么一个 错误(警告)
Type instantiation is excessively deep and possibly infinite.(2589)
类型实例化过于深入,可能无限。(2589)(你递归调用循环次数太多了,我可能会内存溢出)
经过不严谨的测试,我发现只要数字大于等于 1001
就会有这个报错了
# 数组的另类实现方法(乘法)
如果循环太多会导致内存溢出,那我们只能想办法减少循环。
假设我们只需要一个
长度为 11 的数组
思考一下除了逐 1 递增(递归 10 次),还有什么公式可以快速实现?
观察下面的算式(需要亿点点小学知识)
11 = 1+1+1+...+1
11 = (1 * 10) + 1
103 = 1+1+1+1+1...+1
103 = (1 * 10 * 10) + (0 * 10) + 1 + 1 + 1
只需要把枯燥的加法,升级为乘法,十位数乘 10,百位数乘 100,原先一屏幕都写不下的 +1 就被几个 * 10 轻松搞定
Q:TS 如何实现乘法?
A:乘法无非就是把自己放大多少倍,那么 TS 的乘法可以理解为:[...T,...T,...T]['length']
相当于T['length'] * 3
在看上面的 103 ,个位数剩下多少数字也还得相应的加多少次,讲道理我到 100 我才加了 2 次就完事了,为了个位数,还得加 3 次(递归 3 次),显然不划算
对于这种有限情况(个位数无非就是 0-9 10 种情况),完全可以自己列出来。程序需要3,我就给你返回 [1,1,1]
一步到位
- 把 0-9 的情况列出
type N = {
'0': []
'1': [1]
'2': [1, 1]
'3': [1, 1, 1]
'4': [1, 1, 1, 1]
'5': [1, 1, 1, 1, 1]
'6': [1, 1, 1, 1, 1, 1]
'7': [1, 1, 1, 1, 1, 1, 1]
'8': [1, 1, 1, 1, 1, 1, 1, 1]
'9': [1, 1, 1, 1, 1, 1, 1, 1, 1]
}
type Number3 = N['3'] // [1,1,1]
type Number9 = N['9']['length'] // 9
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Q: 为什么要返回数组?
A: 返回数组相对来说更加灵活。如果某段程序需要计数器直接从 10 开始计算,返回 10 的数组能省下前面的 10 次计数器的循环;如果想拿纯数字,直接基于数组获取 ['length'] 属性就可以了。
0-9 解决后,思考 十位数 * 10;百位数 * 10 * 10 的方案
上面也提到了,乘法无非就是 [...T,...T,...T]
。乘 10,只需要 10 个 ...T
(10 个而已,还属于有限情况哈)
把 N 改造下(每一项多加 10 个 ...T
):
type N<T extends 1[] = []> = {
'0': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T]
'1': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1]
'2': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1, 1]
'3': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1, 1, 1]
'4': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1, 1, 1, 1]
'5': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1, 1, 1, 1, 1]
'6': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1, 1, 1, 1, 1, 1]
'7': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1, 1, 1, 1, 1, 1, 1]
'8': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1, 1, 1, 1, 1, 1, 1, 1]
'9': [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, 1, 1, 1, 1, 1, 1, 1, 1, 1]
}
2
3
4
5
6
7
8
9
10
11
12
看到这里还是很蒙,传入 T 数组有何作用?结合下面的 CountToT
思考一下
type CountToT<T extends string | number, Count extends 1[] = []> =
`${T}` extends `${infer First}${infer Rest}` ? CountToT<Rest, N<Count>[keyof N & First]> : Count
type Number11 = N<[1]>[1] // 11
type Number53 = N<[1,1,1,1,1]>[3] // 53
2
3
4
5
CountToT
作用解释
假设现在需要生成一个 103
长度的数组,作为 TS,我们需要把这个分成 3 个数 1
,0
,3
(字符串的 infer 用法)
- 程序运行后 First 拿到数字 1 后
N<Count>[keyof N & First]>
Count 目前是[]
,而 First 则是 1,所以拿到的结果是 [1]- 进行下一次调用的时候 T 就会拿到
03
,而 Count 拿到的就是 [1]
- 第二次 First 则是拿到了 0
N<Count>[keyof N & First]>
Count 目前是[1]
,而 First 则是 0,结合 N 的实现,[1]
会被放大 10 倍,然后在加上0
的值。所以N<Count>[keyof N & First]>
得到的是长度为 10 的数组 (看懂这一步 10 怎么得出来的很重要!)- Rest 就剩下 3,继续递归调用
- 第三次 First 拿到 3 ,而 Count 是
长度为 10 的数组
N<Count>[keyof N & First]>
这时候执行的时候,会把 10 长度的 放大 10 倍,然后在加上 3 个 1 的数组,就实现了最终结果:长度为 103 的数组
CountToT 的巧妙地点在于是逐个
拿到数字,然后每拼接一个新的数字,前面的数对应要 * 10
T 传入的就已经是数字(这时候我们就能直接生成对应的数组长度了,而且大幅减少递归的次数了),剩下的只需要考虑减 1 的问题
至于减 1,我们就要用到 infer
了。在 TS 前置储备知识的时候就说过 对于字符串的 infer 是特别灵活的,他会自动根据你固定有占位的内容算出来,在分配其他内容给 infer
// type N 的实现 ...
// type CountToT 的实现 ...
// 上面说的2个实现也要的哈,就不复制下来了
type MinusOne<T extends number> =
CountToT<T> extends [...infer M1, 1] ? M1['length'] : 0
2
3
4
5
6
7
8
核心在于 [...infer M1, 1]
。假设 CountToT<10> 生成了一个 长度为 10 的数组([1,1,1...,1])。而 [...infer M1, 1]
后面已经占了一个 1,那么根据 ... 运算符
, M1
就会只包揽前 9 个 1 !!(同理,如果改为 [...infer M1, 1 ,1]
,那么 M1 的长度就是8!)
# 实现一个 TS 的减法,不仅仅只是减 1
那么减 1 实现了,能不能实现一个 减法 ?!
// type N 的实现 ...
// type CountToT 的实现 ...
type Minus<T extends number, M extends number, TA extends 1[] = CountToT<T>,MA extends 1[] = CountToT<M>> =
TA extends [...infer M1, ...MA] ? M1['length'] : MA extends [...infer M2,...TA] ? `-${M2['length']}` : 0
type numberMinus = Minus<100,46> // 54 (数字类型)
type numberMinus = Minus<46,100> // -54 (字符串数字类型)
2
3
4
5
6
7
8
9
10
动态的减法,因为数组并不存在负长度的数组
,所以只能拼成字符串了。
思路跟整篇文章是一样的,不过我加了 TA
和 MA
的变量,因为下面比较经常会用到这 2 个变量,没必要每次比较都动态生成一次数组,太浪费,直接起新变量存起来用就行
# 最后
从数组最一开始的逐 1 递增的计数器;到 斐波那契数列 的 数列加法;研究了数组的 乘法 用于快捷生成百位,千位数的数组,以及结合 infer 的超强匹配实现 TS 减法。对 TS 的数组使用理解更加深刻了,至此,数组用法的探索就到这里了,也是个人对 TS 数组用法理解的一个瓶颈了。
当然对于 TS,或者对于数组来说,肯定还有更多的玩法可以发掘,欢迎一起讨论学习~