typescript推算斐波那契
字节跳动数据平台前端团队 人气:0写在前面
本文执行环境typescript,版本4.5.4
斐波那契
虽然大家都熟悉斐波那契了,还是简单的说说吧,一个知名的数学数列,地推方式如下
- Fib(0) = 0
- Fib(1) = 1
- Fib(n) = Fib(n-1) + Fib(n-2)
最后得出来的数列就是
0 1 1 2 3 5 8 13 21 34 55 89 ...
实现逻辑
介绍完斐波那契后,再来看看typescript类型推算要解决核心点
- 第0和第1个数返回自身
- 某个数等于前两个数相加
- 推算一个数需要循环或者递归得到前两个值
- 输入的只能是数字,且不能是负数
分析完我们再来看看typescript能够提供哪些,缺少哪些
第一个问题:第0和第1个数返回自身
这个满足,可以通过extends来实现
type GetSelf<T> = T extends 0 | 1 ? T : never; // 测试 type Test0 = GetSelf<0>; // 0 type Test1 = GetSelf<1>; // 1 type Test2 = GetSelf<2>; // 2
第二个问题:某个数等于前两个数相加
这个就开始麻烦了,因为typesript中是没有加法运算的,也就是说 1 + 2 = 的结果typescript并不知道,所以列一个todo
第三个问题:推算一个数需要循环或者递归得到前两个值
看看typescript中有没有递归呢,是有的,比如实现一个链表
type Node<T> = { val: T; next: Node<T>; }
不过怎么跳出循环,另外我们需要的是一个值,而不是返回一个对象,再列一个todo
第四个问题
输入的只能是数字,且不能是负数
限定数字很好做,extends number就可以判断了,判断负数呢?
负数和正数有啥区别呢?
负数多个符号显示,那改造成字符串后的长度和正数不等是吧,尝试
type len1 = '123'['length']; // number type len2 = number[]['length']; // number; type len3 = [1, 2, 3]['length']; // 3 type len4 = [number, string]['length']; // 3
字符串和未定义的数组的长度竟然无法推算,看起来只有元组是可以的
负数比0小,可是typescript中没有比较大小的操作,再列一个todo
结论
我们可以解决第一个问题,同时得知可以通过 length 来获取元祖长度,todo如下
- 加法运算
- 循环或者递归计算,并有跳出条件
- 判断非负数
解决todo
+1操作
虽然上一轮大部分功能没有推算出来,但是得到一个有用的结论,元祖是可以得到length的值。
那 +1操作 是不是可以理解成 PUSH操作 后拿出 length 了?尝试
type Push<T extends Array<number>, P extends number> = [...T, P]; type arr1 = [1, 2]; type arr2 = Push<arr1, 3>; // [1, 2, 3] type len1 = arr1['length'] // 2 type len2 = arr2['length']; // 3
确实实现了 +1操作 ,加法应该是可以解决了,+n 就是循环n次,结束条件就是结果为n
所以加法运算最后可以转成元祖后计算长度,类似 JavaScript的Array(n).fill(0)
,第一步实现 数字转array
数字转array
type ArrOf<T extends number, P extends Array<0> = []> = { ['loop']: ArrOf<T, [...P, 0]>; ['result']: P; }[P['length'] extends T ? 'result' : 'loop']; type arrof1 = ArrOf<5>; // [0, 0, 0, 0, 0]
因为我们需要递归后再跳出条件,最后返回值,所以可以构造一个对象后获取key,而key就是跳出循环的关键,跳出循环的判断就是 元祖的长度等于输入的数
基于以上实现,我们可以得到add的完整实现了
type ADD<A extends number, B extends number> = [...ArrOf<A>, ...ArrOf<B>]['length']; type add1 = ADD<3, 4>; // 7
虽然可以推算出结果,但是给我报了一个warning
A rest element type must be an array type.
我觉得可能他推算不出来返回的是array,所以需要我们声明ArrOf返回的数都是array,类似 Array.from
type ArrFrom<T> = T extends Array<T> ? T : T; type ADD<A extends number, B extends number> = [...ArrFrom<ArrOf<A>>, ...ArrFrom<ArrOf<B>>]['length'];
加法和递归都被搞定了,接下来看看非负数的问题
非负数判断
再重新看看之前的分析,负数有什么特殊的地方,负数多个符号显示,且符号固定是第一位
type str11 = 'abcde'; type str12 = str11[0]; // string
看来并不能通过下标来取巧,那我们只能上 infer 了
type getFirst<T extends string> = T extends `${infer P}${string}` ? P : T; type str11 = 'abcde'; type str12 = getFirst<str11>; // a
所以我们可以把数字转换字符串后求得符号,然后得出负数的判断
type FirstStr<T extends number> = `${T}` extends `${infer P}${string}` ? P : T; type isFu<T extends number> = FirstStr<T> extends '-' ? true : false; type isFu1 = isFu<0>; // false type isFu2 = isFu<12>; // false type isFu3 = isFu<-6>; // true type isFu4 = isFu<-0>; // true
实现斐波那契
所有的部分都就绪了,实现一下斐波那契
type ArrOf<T extends number, P extends Array<0> = []> = { ['loop']: ArrOf<T, [...P, 0]>; ['result']: P; }[P['length'] extends T ? 'result' : 'loop']; // 第8行提示结果可能不是array type ArrFrom<T> = T extends Array<T> ? T : T; type ADD<A extends number, B extends number> = [...ArrFrom<ArrOf<A>>, ...ArrFrom<ArrOf<B>>]['length']; // 第23行提示结果可能不是number type NumberFrom<T> = T extends number ? T : T & number; type ADD2<A extends number, B extends number> = NumberFrom<ADD<A, B>>; type FirstStr<T extends number> = `${T}` extends `${infer P}${string}` ? P : T; // 添加负数判断 type isFu<T extends number> = FirstStr<T> extends '-' ? true : false; type FIB<T extends number, A extends number = 0, B extends number = 1, N extends number = 0> = isFu<T> extends true ? never : T extends 0 | 1 ? T : { ['loop']: FIB<T, B, ADD2<A, B>, ADD2<N, 1>>; ['result']: B; }[T extends ADD2<N, 1> ? 'result' : 'loop']; type FIFU1 = FIB<-6> // never type FI0 = FIB<0> // 0 type FI1 = FIB<1>; // 1 type FI2 = FIB<2>; // 1 type FI3 = FIB<3>; // 2 type FI4 = FIB<4>; // 3 type FI5 = FIB<5>; // 5 type FI6 = FIB<6>; // 8 type FI7 = FIB<7>; // 13 type FI8 = FIB<8>; // 21 type FI9 = FIB<9>; // 34
总结
加载全部内容