ARTICLE DETAIL

资讯详情

深耕网站建设与运营推广的一线实战洞察。

type-challenges 题解:Compare Array Length——在类型层面用递归比较两个数组的长度

type-challenges 题解:Compare Array Length——在类型层面用递归比较两个数组的长度 示例工程【免费下载链接】type-challengesCollection of TypeScript type challenges with online judge项目地址https://gitcode.com/GitHub_Trending/ty/type-challenges点击查看免费下载导读CompareArrayLength是 type-challenges 仓库中一道 medium 难度、标签为recursion与array的类型体操题目编号 34007由 alviner 提出核心任务是在不借助运行时的情况下仅凭 TypeScript 类型系统判断两个元组T与U的长短关系分别返回1、-1或0。本文以 题目 README 为骨架结合该题目的 template.ts 模板与 test-cases.ts 测试用例系统讲解条件类型递归、元组长度读取与成对弹出比较法的完整思路并给出可复现的解法与源码级验证帮助你掌握数字比较类类型体操的通用套路。题目要求与输入输出契约题目原文ImplementCompareArrayLengthto compare two array length(T U). If length of T array is greater than U, return 1; If length of U array is greater than T, return -1; If length of T array is equal to U, return 0.翻译为契约化描述实现一个类型CompareArrayLengthT, U其中T、U均为数组含元组类型其返回值是一个数字字面量类型条件返回T数组的长度大于U的长度1U数组的长度大于T的长度-1T与U长度相等0与仓库内同类的两数比较题目如 Greater Than 题目 要求GreaterThanT, U模拟T U且明确不需要考虑负数相比本题的输入被限定为数组类型因此长度天然是非负整数规避了负数与符号处理问题被收敛为纯粹的非负整数大小比较。模板与测试用例题目给出的待实现模板位于 template.tstype CompareArrayLengthT extends any[], U extends any[] any模板约束了两个泛型参数都必须是任意数组/元组类型T extends any[], U extends any[]这是第一道安全网——若传入非数组类型类型系统会直接报错。真正需要实现的是将any替换为具体的类型逻辑。在 test-cases.ts 中仓库提供了 4 条验证用例import type { Equal, Expect } from type-challenges/utils type cases [ ExpectEqualCompareArrayLength[1, 2, 3, 4], [5, 6], 1, ExpectEqualCompareArrayLength[1, 2], [3, 4, 5, 6], -1, ExpectEqualCompareArrayLength[], [], 0, ExpectEqualCompareArrayLength[1, 2, 3], [4, 5, 6], 0, ]可见测试覆盖了三类场景长度不等且方向不同前长后短得1、前短后长得-1、双空数组长度相等得0、非空但等长得0。Expect与Equal均来自本仓库 workspace 内的type-challenges/utils包其实现可在 utils/index.d.ts 中查看Equal通过函数签名逆变比较严格判断两个类型是否完全一致ExpectT extends true则强制断言结果为true任何一处实现偏差都会在类型检查阶段直接报编译错误。核心思路用元组长度做数字计数器类型层面读取长度T[length]TypeScript 类型系统中元组类型自带length属性且其值是一个数字字面量类型而非宽泛的number。例如type Len1 [1, 2, 3, 4][length] // 4 type Len2 [][length] // 0因此本题最直观的解法是分别读取两个长度字面量再比较type LengthA T[length] type LengthB U[length]为什么不能直接比较数字字面量类型系统不支持对两个任意数字字面量做加减乘除或大小比较没有T[length] U[length]这样的运算符。仓库中大量数字运算类题目如 MinusOne 题目、Number Range 题目、ConstructTuple 题目都使用同一套替代方案用元组的length作为计数器的刻度盘。即长度 n等价于长度为 n 的元组递增即[..., any]追加元素递减即移除尾部元素比较则依赖递归展开。在 Greater Than 题目的测试用例 中可以看到这类比较可以延伸到GreaterThan1234567891011, 1234567891010这样的超长数字说明以元组为计数器的方案在纯类型层面天然支持任意大小的非负整数。解法一成对弹出双递归计数器思路同时消费两个元组既然长度等于元组长度那么比较T、U的长短等价于从两端同时弹出元素若T先弹空而U还有剩余说明T更短返回-1若U先弹空而T还有剩余说明T更长返回1若同时弹空说明两者等长返回0。这与仓库内 Reverse 题目每次取出首元素放入新数组、Pop 题目弹出末尾元素等元组递归操作一脉相承区别在于本题要同时递归两个元组。实现如下type CompareArrayLength T extends any[], U extends any[], T[length] extends U[length] ? 0 : T extends [any, ...infer RestT] ? U extends [any, ...infer RestU] ? CompareArrayLengthRestT, RestU : 1 : -1逐条解释基线相等判断T[length] extends U[length]——长度相等直接返回0。这不仅覆盖了[]vs[]与等长非空元组还能在递归中途提前终止例如[1,2,3]vs[4,5,6]在第一轮就命中3 extends 3返回0无需继续递归。T非空分支T extends [any, ...infer RestT]用变体元组解构拆出首个元素与剩余元组RestT。当T为空元组时该分支不成立落入最后的-1。U非空分支同理拆出RestU若此时U已为空说明T仍有剩余而U已耗尽返回1。递归两者都非空时用RestT、RestU继续调用自身每轮各削减一个元素。对测试用例的推演CompareArrayLength[1, 2, 3, 4], [5, 6]长度4不等于2T 非空且 U 非空 → 递归[2,3,4]vs[6]→[3,4]vs[]此时 T 非空、U 为空 → 返回1✔CompareArrayLength[1, 2], [3, 4, 5, 6]2不等于4→ 递归[2]vs[4,5,6]→[]vs[5,6]T 为空 → 返回-1✔CompareArrayLength[], []0 extends 0→ 返回0✔CompareArrayLength[1, 2, 3], [4, 5, 6]3 extends 3→ 返回0✔该解法完全通过 test-cases.ts 的 4 条断言时间复杂度递归深度为O(min(lenT, lenU))。解法二先取长度再递归消耗增量计数器思路把长度转成可消费的计数元组另一种更贴近数字比较直觉的写法是先读取两个长度字面量然后以长度为刻度构建计数元组再递归消耗。其核心是MinusOne式的长度减一一个长度为 n 的元组弹出头部后剩余长度为 n-1。type CompareArrayLengthT extends any[], U extends any[] CompareLenT[length], U[length] type CompareLen TA extends number, UA extends number, TA extends UA ? 0 : BuildTupleTA extends [any, ...infer R1] ? BuildTupleUA extends [any, ...infer R2] ? CompareLenR1[length], R2[length] : 1 : -1 type BuildTupleN extends number, Acc extends any[] [] Acc[length] extends N ? Acc : BuildTupleN, [...Acc, any]BuildTupleN是仓库中 ConstructTuple 题目 的核心模式从空数组开始不断追加any直到Acc[length]等于目标长度。随后CompareLen对两个计数元组做与解法一相同的成对弹出弹空的一方即为较短者。与解法一相比该写法多了一次数字字面量 → 元组的构建过程每次递归都要重建两个计数元组空间与时间开销更大但思路更贴近比较两个数字的直觉也更容易迁移到 Greater Than 这类直接比较数字字面量的题目。解法三infer与长度推算的辅助套路一次 infer 同时获得剩余元组与其长度TypeScript 的条件类型中infer声明的变量可以同时被后续分支引用。利用这一点可以在同一次解构中既得到剩余元组又通过Rest[length]拿到其剩余长度从而写出更紧凑的版本type CompareArrayLengthT extends any[], U extends any[] T extends [...infer RestT, ...U[length] extends infer _ ? [any] : [any]] ...不过这种写法可读性较差。更常用的紧凑写法是配合等长短路把三个分支压缩在一层条件里。这里给出一个可读性较好、适合作为参考答案的实现type CompareArrayLengthT extends any[], U extends any[] T[length] extends U[length] ? 0 : T extends [any, ...infer RestT] ? ( U extends [any, ...infer RestU] ? CompareArrayLengthRestT, RestU : 1 ) : -1它与解法一逻辑完全等价仅将等长判断放在最外层提前短路。注意infer RestT得到的RestT会自动携带正确的length属性因此递归调用CompareArrayLengthRestT, RestU时无需显式传长度类型参数仍然满足extends any[]的约束。边界情况与易错点1. 空数组与等长短路T[length] extends U[length]必须放在递归之前。若把相等判断放在递归之后空数组对([], [])会陷入T 为空走-1的错误分支。测试用例 test-cases.ts 中的第 3 条正是针对该边界的回归保护。2. 参数约束extends any[]模板中的T extends any[], U extends any[]是不可省略的约束。仓库中 Reverse 题目的测试用例 展示了同类约束的写法——用ts-expect-error断言Reversestring、Reverse{ key: value }必须报错。本题虽然未显式提供负例但约束保证了对string、object等非数组入参的编译期拦截。3. 递归深度与性能条件类型递归受编译器递归深度限制。解法一的递归深度为O(min(lenT, lenU))对常见规模的元组数百以内没有问题解法二因为每次都要重建计数元组实际展开的实例数量更大超大元组下可能触发Type instantiation is excessively deep之类的编译器报错。在 Greater Than 测试用例 中可以看到仓库对这类数字比较题目会压测到1234567891011级别的输入因此优先选择递归深度更浅的解法一。4. 返回值必须是字面量类型测试断言ExpectEqualCompareArrayLength..., 1中的Equal是严格比较见 utils/index.d.ts返回宽泛的number无法通过断言。所有分支必须返回1/-1/0这样的字面量。延伸从数组长度比较到数字比较掌握了元组长度即计数器的思路后可以把它推广到仓库中一系列数字运算题目形成体系化认知Greater Than编号 4425把两个数字字面量转成计数元组后成对弹出T先空则falseU先空则true本质就是本题的比较环节。MinusOne编号 2257MinusOne1得0实现时把T转成计数元组再弹出头部剩余元组的length即减一结果其测试甚至包含9_007_199_254_740_992级别的输入。Number Range编号 8640从L构建计数元组并不断递增直到长度等于H产出L | L1 | ... | H的联合类型其测试用例覆盖0..140的范围见 测试用例。ConstructTuple编号 7544BuildTuple的模板来源将数字字面量转换为指定长度的元组。这些题目共享同一个底层设施——长度即数值、元组即计数器而CompareArrayLength正是其中比较这一环节最简洁的练习。如何在仓库中验证你的实现type-challenges 的每个题目目录都包含template.ts与test-cases.ts验证方式是用类型检查跑测试将解法写入 template.ts替换 any的部分保留T extends any[], U extends any[]的签名与题目一致测试断言由 test-cases.ts 引入其中的Expect、Equal依赖 workspace 内的type-challenges/utils包声明见 utils/index.d.ts在仓库根目录运行类型检查命令项目基于 pnpm 管理tsconfig.json与tsconfig.base.json位于根目录pnpm install npx tsc --noEmit若类型实现正确test-cases.ts中的所有ExpectEqual...均通过tsc无报错若实现错误如返回宽泛number、比较方向反了、遗漏空数组分支类型检查会直接失败并指向对应断言行。小结CompareArrayLength是一道小巧但典型的递归类类型体操它把两个数组长度的大小比较翻译为两个元组的成对弹出本质是用元组的length作为类型层面的计数器绕开类型系统不支持的数字比较运算。核心要点有三长度即元组T[length]是数字字面量可借助BuildTuple之类的模式转成可操作的计数元组递归即循环变体元组解构[any, ...infer Rest]提供弹出头部的能力配合等长短路实现三态返回1/-1/0约束与字面量泛型约束extends any[]拦截非数组入参所有分支必须返回字面量类型才能通过Equal严格断言。掌握这一思路后你可以轻松迁移到 Greater Than、MinusOne、Number Range 等数字运算系列题目在类型系统中完成从比较到四则运算的完整能力拼图。赞分享示例工程【免费下载链接】type-challengesCollection of TypeScript type challenges with online judge项目地址https://gitcode.com/GitHub_Trending/ty/type-challenges点击查看免费下载相关推荐type-challenges 题解298 Length of String——用模板字面量类型在类型层计算字符串长度type challenges 题解 298 Length of String——用模板字面量类型在类型层计算字符串长度 Length of String 是示例工程type-challenges 中等题 298用模板字面量类型与递归实现 Length of Stringtype challenges 中等题 298用模板字面量类型与递归实现 Length of String 本文围绕 type challenges 题库中编示例工程ppscore源代码解析决策树在预测力评分中的应用ppscore源代码解析决策树在预测力评分中的应用 Predictive Power Score PPS 是一种数据科学工具用于衡量一个特征对另一个特征的预上一篇Aurelia 1框架自定义依赖注入装饰器简化服务注册下一篇免费导出微信聊天记录WeChatMsg 完整教程创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表