476-Sum

题目描述

Implement a type Sum<A, B> that summing two non-negative integers and returns the sum as a string. Numbers can be specified as a string, number, or bigint.

For example,

type T0 = Sum<2, 3>; // '5'
type T1 = Sum<'13', '21'>; // '34'
type T2 = Sum<'328', 7>; // '335'
type T3 = Sum<1_000_000_000_000n, '123'>; // '1000000000123'

分析

在 8804-两数之和 中已经提到两个数字加法的结果，但是借助的是构造一定长度的元组实现，这中间就涉及到了递归深度的问题，递归深度 导致当数字超过 1000 之后就会出现问题。

故这个题目，需要思考新的方案。

在 274-整数比较器 中其实就处理了大数字的情况，是将其转换成字符进行按位比较。

这个题目同样可以如此，按位加法，不过加法需要考虑进位以及执行顺序的问题。

因为加法是从右往左进行，故需要将字符反转，计算出结果后再进行反转即可得到最终结果。

而进位则需要一个辅助泛型进行标记即可。相信对做到这里的同学其实不太难了，直接根据代码进行讲解。

题解

// 转为字符
type TypeToString<T extends number | string | bigint> = `${T}`;
// 字符转元组
type StringToUnion<T extends string> = T extends `${infer F}${infer R}`
  ? [F, ...StringToUnion<R>]
  : [];
// 反转元组为字符
type ReverseUnion<T extends any[]> = T extends [
  ...infer F extends string[],
  infer R extends string,
]
  ? `${R}${ReverseUnion<F>}`
  : '';
// 反转字符
type Reverse<T extends number | string | bigint> = ReverseUnion<
  StringToUnion<TypeToString<T>>
>;

type ArrWithLength<
  A extends number,
  Acc extends any[] = [],
> = Acc['length'] extends A ? Acc : ArrWithLength<A, [...Acc, 1]>;

// 按位相加，此时最大是 9 + 9 + 1 不会导致递归溢出
type SumSingle<A extends number, B extends number, Carry extends number = 0> = [
  ...ArrWithLength<A>,
  ...ArrWithLength<B>,
  ...ArrWithLength<Carry>,
]['length'];

// 反转后的字符进行相加
type SumReverse<A extends string, B extends string, Carry extends number = 0> =
  // 匹配第一个数字
  A extends `${infer FA extends number}${infer RA}`
    ? // 匹配 B 的第一个数字
      B extends `${infer FB extends number}${infer RB}`
      ? // 判断两者之和是否大于 10
        `${SumSingle<FA, FB, Carry> &
          number}` extends `1${infer F extends number}`
        ? // 是 1x，那么结合 x 和递归处理剩余元素构成最终输出。需要注意的是 Carry 置为1
          `${F}${SumReverse<RA, RB, 1>}`
        : // 否则，小于 10，那么直接返回按位计算结果，并递归剩余元素，此时 Carry 值为 0
          `${SumSingle<FA, FB, Carry> & number}${SumReverse<RA, RB, 0>}`
      : // 如果 B 已经匹配完了，那么根据进位，决定是否要再计算
      Carry extends 1
      ? SumReverse<A, '0', Carry>
      : A
    : // 如果 A 已经是空字符了，那么根据进位，决定是否计算 B
    Carry extends 1
    ? SumReverse<'0', B, Carry>
    : B;

// 最终的结果就是 将 SumReverse 结果反转即可
type Sum<
  A extends string | number | bigint,
  B extends string | number | bigint,
> = Reverse<SumReverse<Reverse<A>, Reverse<B>>>;

知识点

1. 递归深度问题
2. 按位加法，其实是小学的知识了