274-整数比较器

题目描述

Implement a type-level integers comparator. We've provided an enum for indicating the comparison result, like this:

• If a is greater than b, type should be Comparison.Greater.
• If a and b are equal, type should be Comparison.Equal.
• If a is lower than b, type should be Comparison.Lower.

Note that a and b can be positive integers or negative integers or zero, even one is positive while another one is negative.

分析

比较大小的题目之前在 4425-实现比较 已经做过了，但是这一题的要求更为苛刻，需要考虑负数以及超过 1000 的数据的比较。

此时，之前通过构造辅助元组的方式实现比较就不可行。

这道题有两个麻烦的地方：

1. 负数的处理
2. 超过 1000 的数据的处理

负数的问题相对简单，如果一正一负，那么必然是正的大，如果是两个负数，那么只需要比较他们绝对值的大小就行了。

那么对于超过 1000 的数字，不能使用构造元组，只能用最原始的方法：模拟位比较，这在大数的加减乘除中也比较常用。

首先，将数字转为字符，比较长度，长度长的必然更大。

如果长度相等，那么需要每一位进行比较，直到比出更大的一方为止。

每一位的比较，可以通过 4425-实现比较 进行比较，因为一个位的长度最大也就是 9，并不会超过 1000。

了解了模拟比较的思路，这题的解法就比较简单了：

1. 判断入参是否相等： A extends B，如果相等，直接返回 Equal
2. 不相等，根据符号有四种场景：A 负 B 负、A 负 B 正、A 正 B 负、A 正 B 正
3. 对于 A 负 B 正、A 正 B 负 的场景，正数必然大
4. 对于 均为负的场景，可以转换成整数后，将比较结果取反
5. 对于正数的场景，使用模拟位比较的方式进行每一位的比较即可得到最终的结果

题解

// 相等
// 两个正数
// 两个负数
// 一正一负
type Comparator<A extends number, B extends number> = A extends B
  ? Comparison.Equal // 相等
  : `${A}` extends `-${infer F extends number}`
  ? `${B}` extends `-${infer R extends number}`
    ? GreaterThanBit<`${F}`, `${R}`> extends true // 两个负数，比较绝对值
      ? Comparison.Lower
      : Comparison.Greater
    : Comparison.Lower // A 负 B 正
  : `${B}` extends `-${infer R extends number}`
  ? Comparison.Greater // A 正 B 负
  : GreaterThanBit<`${A}`, `${B}`> extends true // A 正 B 正
  ? Comparison.Greater
  : Comparison.Lower;

// 4425-实现比较
type GreaterThan<T extends number, U extends number, Arr extends any[] = []> =
  // 先达到 T，则 T 小
  T extends Arr['length']
    ? false
    : // 先达到 U
    U extends Arr['length']
    ? // 则 T 大
      true
    : // 都没到，膨胀元组
      GreaterThan<T, U, [...Arr, 1]>;

// 计算字符长度
type LengthOfString<
  T extends string,
  Arr extends 1[] = [],
> = T extends `${infer F}${infer R}`
  ? LengthOfString<R, [...Arr, 1]>
  : Arr['length'];

// 按位比较
type GreaterThanBit<
  A extends string,
  B extends string,
> = LengthOfString<A> extends LengthOfString<B>
  ? A extends `${infer FA extends number}${infer RA}`
    ? B extends `${infer FB extends number}${infer RB}`
      ? FA extends FB
        ? GreaterThanBit<RA, RB>
        : GreaterThan<FA, FB>
      : // 不会走到这一分支，因为提前判断了长度是否相等
        false
    : // 走到这一分支，A 和 B 是相等的，但是在 Comparator 中已经对相等进行了处理
      // 故此处不做处理
      false
  : GreaterThan<LengthOfString<A>, LengthOfString<B>>;

知识点

1. 按位比较
2. 4425-实现比较
3. 负数转换等等