写在前面 本文执行环境typescript,版本4.7.4
能否将元组 [3, 1, 2, 4] 通过泛型转换成 [1, 2, 3, 4]
如何实现快排?
• 遍历元组
• 元组每个值的大小比较
• 每次比较中挑选出符合条件的值,也就是实现 Filter
在typescript类型中没有比较符,那如何判断 5 和 6 谁更大?
typescript类型不知道,所以需要找到在typescript中已经存在的递增数列,通过这个数列来实现
怎么理解呢
类似有 张三 和 李四 两个人,要比较他们谁的位置靠前,需要有一个他们排队的数列,然后依次查看,先看到 张三,那么 张三 的位置明显靠前
typescript中有这样的递增数列吗?
有的:元组下标(取元祖长度,元祖push的时候长度是递增的数列),只需要递归元组,就可以实现依次点名
• 无限递归,直到匹配到 A 或者 B
• 先匹配到 A 返回true(表示A小于或等于B),否则返回false
type SmallerThan<
A extends number,
B extends number,
T extends number[] = []
> = T['length'] extends A ? true :
T['length'] extends B ? false :
SmallerThan<A, B, [...T, 0]>;
逻辑同理
• 无限递归,直到匹配到 A 或者 B
• 先匹配到 A 返回false,否则返回true(表示A大于或等于B)
type LargerThan<
A extends number,
B extends number,
T extends number[] = []
> = T['length'] extends A ? false :
T['length'] extends B ? true :
LargerThan<A, B, [...T, 0]>;
当然也可以依赖 SmallerThan 泛型来实现
• 与SmallerThan的布尔值取反
type LargerThan<
A extends number,
B extends number,
T extends number[] = []
> = SmallerThan<A, B, T> extends true ? false : true;
• 根据元组长度递归,直到递归次数与元祖长度相等
• 当满足条件(比如:大于等于某个值),将值存储到新元组中,否则不操作
• 依赖上面实现的大小值比较 分别实现 对应的Filter
基于已有的 LargerThan 泛型实现 FilterLargerThan
type FilterLargerThan<
T extends number[],
A extends number,
Z extends number[] = [],
R extends number[] = []
> = T['length'] extends R['length'] ?
Z : FilterLargerThan<
T,
A,
LargerThan<T[R['length']], A> extends true ? [...Z, T[R['length']]] : Z,
[...R, 0]
>;
同理,基于已有的 SmallerThan 泛型实现 FilterSmallerThan
type FilterSmallerThan<
T extends number[],
A extends number,
Z extends number[] = [],
R extends number[] = []
> = T['length'] extends R['length'] ?
Z : FilterSmallerThan<
T,
A,
SmallerThan<T[R['length']], A> extends true ? [...Z, T[R['length']]] : Z,
[...R, 0]
>;
Filter写的很重复了,根据DRY原则(don't repeat yourself),需要将泛型作为参数传进去,来避免冗余重复的代码
如何把泛型作为参数传入,然后在参数中限定?
嗯...好问题
// 目标是实现这种
type Test<A extends number, T extends ?> = T<A>;
貌似不太行,那变个思路:
实现一个泛型对象,每个键值对实现对应的处理,最后只需要传入这个对象的key来获取泛
型,在参数的限定可以变成对key的限定,通过keyof 对象即可实现
• 实现一个泛型对象Demo
• 每个键值对实现对应的处理,如 a: F
• 传入这个对象的key来获取泛型,如 T extends keyof Demo
type F<A extends number> = A;
type Demo<A extends number> = {
a: F<A>;
}
type Test<A extends number, T extends keyof Demo<number>> = Demo<A>[T];
type t1 = Test<1, 'a'>;
• 根据上述原则,将对应的泛型组合成泛型对象 Compare
• SmallerThan 实现之前的 SmallerThan 泛型
• LargerThan 实现之前的 LargerThan 泛型
type Compare<A extends number, B extends number, T extends number[] = []> = {
['SmallerThan']:
T['length'] extends A ? true :
T['length'] extends B ? false :
Compare<A, B, [...T, 0]>['SmallerThan'];
['LargerThan']:
T['length'] extends A ? false :
T['length'] extends B ? true :
Compare<A, B, [...T, 0]>['LargerThan'];
}
• 将对应的泛型改成 Compare
• key需要手动传入,即为字符串 SmallerThan 和 LargerThan
type Filter<
T extends number[],
A extends number,
key extends keyof Compare<number, number>,
Z extends number[] = [],
R extends number[] = [],
> = T['length'] extends R['length'] ?
Z : Filter<
T,
A,
key,
Compare<T[R['length']], A>[key] extends true ? [...Z, T[R['length']]] : Z,
[...R, 0]
>;
• 递归元组,直到拆解为长度 0 或者 1 的元祖
• 元组长度小于等于 1 的时候返回自身
• 默认取第一项作为对比值,并用泛型 UNSHIFT 移除第一项
• 通过filter和第一项比较筛选出对应的新元祖
type UNSHIFT<T extends number[]> = T extends [number, ...infer U] ? U: [];
// 确保 Smaller 和 Larger 为元祖/数组
type IsArray<T> = T extends number[] ? T : [];
// 快排
type QuickSort<
T extends number[],
Smaller extends number[] = IsArray<Filter<UNSHIFT<T>, T[0], 'SmallerThan'>>,
Larger extends number[] = IsArray<Filter<UNSHIFT<T>, T[0], 'LargerThan'>>
> = T['length'] extends 0 | 1 ?
T : [
...QuickSort<Smaller>,
T[0],
...QuickSort<Larger>
];
type ARR1 = [5, 2, 4, 1, 0, 6];
type test1 = QuickSort<ARR1>;
// [0, 1, 2, 4, 5, 6]
type ARR2 = [3, 2, 7, 1, 0, 6, 9, 5, 8, 4];
type test2 = QuickSort<ARR2>;
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
type ARR3 = [1, 1, 0, 1, 1, 0, 0];
type test3 = QuickSort<ARR3>;
// [0, 0, 0, 1, 1, 1, 1]
看起来一切正常,可以发现遗漏了负数
测试负数的时候问题出现了
因为最开始的大小值对比,是从0开始无限递归的
结束条件是命中其中一个数,然而负数是永远不会命中,这就是致命bug!
负数的特点:多了一个符号,也就是 "-"
• 转换成字符串后取第一个字符判断是否为 "-"
• 通过 infer 来获取第一个字符
type isFuShu<T extends number> = `${T}` extends `${infer P}${string}` ?
P extends '-' : true : false;
type i1 = isFuShu<6>; // false
type i2 = isFuShu<-6>; // true
但是这样拿到的是字符串,还要把字符串转成数字
和大小比较的逻辑一样
• 无限递归,每次递归传入新元组
• 元组长度(模板字符串) 等于 参数后结束递归,并返回元组长度
type ToNumber<S extends string, R extends number[] = []> =
S extends `${R['length']}` ?
R['length'] : ToNumber<S, [...R, 0]>;
判断是负数后要拿到负数的值
• 和负数符号判断类似,获取除开符号之后的字符串
• 字符串通过泛型 ToNumber 转数字
type GetFushu<T extends number> = `${T}` extends `${string}${infer U}` ?
ToNumber<U> : 0;
• 非负数返回自身,负数通过泛型 GetFushu 来获取
type GetAbs<T extends number> = isFuShu<T> extends true ? GetFushu<T> : T;
负数的对比和正数相反,且正数一定比负数大
• 判断比较的值是负数还是非负数
• 非负数通过泛型 CompareV2 比较大小
• 负数获取绝对值后,通过泛型 CompareV2 取反比较大小
• 非负数一定大于负数
• 泛型 SmallerThan 实现非负数的比较,泛型SmallerThanV2 实现负数和非负数的比较
• 泛型 LargerThan 和泛型 LargerThanV2 同理
type CompareV2<A extends number, B extends number, T extends number[] = []> = {
['SmallerThan']:
T['length'] extends A ? true :
T['length'] extends B ? false :
CompareV2<GetAbs<A>, GetAbs<B>, [...T, 0]>['SmallerThan'];
['SmallerThanV2']:
isFuShu<A> extends true ?
(isFuShu<B> extends true ?
CompareV2<A, B>['LargerThan'] :
true) :
(isFuShu<B> extends true ?
false :
CompareV2<A, B>['SmallerThan']);
['LargerThan']:
T['length'] extends A ? false :
T['length'] extends B ? true :
CompareV2<GetAbs<A>, GetAbs<B>, [...T, 0]>['LargerThan'];
['LargerThanV2']:
isFuShu<A> extends true ?
(isFuShu<B> extends true ?
CompareV2<A, B>['SmallerThan'] :
false) :
(isFuShu<B> extends true ?
true :
CompareV2<A, B>['LargerThan']);
}
测试用例
type h1 = CompareV2<-8, -6>['SmallerThanV2']; // true
type h2 = CompareV2<8, -6>['SmallerThanV2']; // false
type h3 = CompareV2<6, 8>['SmallerThanV2']; // true
type h4 = CompareV2<-8, 6>['SmallerThanV2']; // true
type i1 = CompareV2<-8, -6>['LargerThanV2']; // false
type i2 = CompareV2<8, -6>['LargerThanV2']; // true
type i3 = CompareV2<6, 8>['LargerThanV2']; // false
type i4 = CompareV2<-8, 6>['LargerThanV2']; // false
重构泛型 FilterV2(更换 Compare -> CompareV2)
type FilterV2<
T extends number[],
A extends number,
key extends keyof CompareV2<number, number>,
Z extends number[] = [],
R extends number[] = [],
> = T['length'] extends R['length'] ?
Z : FilterV2<
T,
A,
key,
CompareV2<T[R['length']], A>[key] extends true ? [...Z, T[R['length']]] : Z,
[...R, 0]
>;
// 快排
type QuickSortV2<
T extends any[],
Smaller extends number[] = IsArray<FilterV2<UNSHIFT<T>, T[0], 'SmallerThanV2'>>,
Larger extends number[] = IsArray<FilterV2<UNSHIFT<T>, T[0], 'LargerThanV2'>>
> = T['length'] extends 0 | 1 ?
T : [
...QuickSortV2<Smaller>,
T[0],
...QuickSortV2<Larger>
];
type ARR4 = [-5, -2, -4, -1, 0, -6];
type test4 = QuickSortV2<ARR4>;
// [-6, -5, -4, -2, -1, 0]
type ARR5 = [-5, -2, 4, -1, 0, -6, 2, -3, 7];
type test5 = QuickSortV2<ARR5>;
// [-6, -5, -3, -2, -1, 0, 2, 4, 7]
type ARR6 = [3, -2, 7, -1, 0, -6, 9, -5, 8, -4];
type test6 = QuickSortV2<ARR6>;
// [-6, -5, -4, -2, -1, 0, 3, 7, 8, 9]
来自:https://zhuanlan.zhihu.com/p/564256981
有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。
程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法
使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。
给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。
racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。
JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题
这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。
什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a
将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!