欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

使用typescript類型實現(xiàn)ThreeSum

 更新時間：2022年08月14日 10:14:30   作者：東東么么噠  
這篇文章主要介紹了使用typescript類型實現(xiàn)ThreeSum，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以一下，希望對你學(xué)習(xí)又是幫助

前言

本文執(zhí)行環(huán)境typescript，版本4.7.4

不使用typescript的計算能力，通過類型來實現(xiàn)ThreeSum

思路整理

實現(xiàn)ThreeSum之前我們先降低下難度，實現(xiàn)TwoSum，因為TwoSum可以作為ThreeSum的基礎(chǔ)泛型

TwoSum需要準備什么呢？

  • 遞歸元組，模擬for循環(huán)
  • 減法，遞歸過程中求出差值
  • 對每一項差值判斷是否存在

完成TwoSum后如何實現(xiàn)ThreeSum？

  • 每一項和剩余元組走一遍 TwoSum泛型，篩選滿足條件的
  • 為了保證每一項能夠走TwoSum泛型，對于元組大到小排序

實現(xiàn)TwoSum

實現(xiàn)減法

因為元組下標(biāo)是遞增有序數(shù)列，我們在每次遞歸的時候返回一個長度+1的新元組并獲取長度，就可以對非負整數(shù)依次點名了

如求A - B，我們假設(shè)A - B永遠是非負整數(shù)數(shù)，無限遞歸產(chǎn)生新元祖的過程中，排查掉A和B相等后，必定是先點名到B，然后點名到A，而B 到 A的遞歸次數(shù)就是差值，也就是求得的結(jié)果

實現(xiàn)這個差值的計算

  • A作為被減數(shù)，R作為長度與減數(shù)相等的數(shù)組，Z則用于遞歸累增
  • 當(dāng)被減數(shù)R長度等于A的過程中，Z則是被減數(shù)和減數(shù)的差值
type GetLen<A extends number, R extends number[], Z extends number[] = []> =
  A extends R['length'] ? Z['length'] : GetLen<A, [...R, 0], [...Z, 0]>;

減法如下：

  • 排除掉A和B相等的情況
  • 前提條件：A大于或者等于B
  • 用差值泛型求A 和 B的差
type Subtract<A extends number, B extends number, R extends number[] = []> =
  A extends B ? 0 :
  A extends R['length'] ? never :
  B extends R['length'] ? GetLen<A, R> :
  Subtract<A, B, [...R, 0]>;

元祖中是否包含差值

求出每一項的差值后，需要判斷元組中是否存在，存在則滿足 被減數(shù)和減數(shù) 都存在元祖，作為復(fù)合條件的一組返回

  • 從元祖第一項開始遞歸至末尾，則返回false
  • 若某一項的值滿足尋找的值，返回ture，否則遞歸
type Includes<A extends number[], T extends number, L extends number[] = []> =
  A['length'] extends L['length'] ? false :
  A[L['length']] extends T ? true : Includes<A, T, [...L, 0]>;

遞歸元組

根據(jù)最開始的思路可以實現(xiàn)：

  • 依次遞歸元祖
  • 對每一項求差值
  • 判斷差值是否存在于數(shù)組中
  • R是返回的結(jié)果，N是遞歸計數(shù)，Item是被減數(shù)，SubItem是減數(shù)
type TwoSum<
  T extends number,
  L extends number[],
  R extends number[][] = [],
  N extends number[] = [],
  Item extends number = L[N['length']],
  SubItem extends number = Subtract<T, Item>,
> = L['length'] extends N['length'] ?
  R : TwoSum<
    T,
    L,
    Includes<L, SubItem> extends true ? [
      ...R,
      [Item, SubItem]
    ] : R,
    [...N, 0]
  >;
  
type t1 = TwoSum<4, [1, 2, 3]>;
// [[1, 3], [2, 2], [3, 1]]

存在缺陷：

  • 如果被減數(shù)和減數(shù)值相同，且只存在一個，那結(jié)果也是滿足的。如：4 和 [1, 2, 3]，我們要的是 [1, 3]，需要排除掉 [2, 2]
  • 遞歸到被減數(shù)和減數(shù)都會滿足條件，會存在重復(fù)的兩個結(jié)果。如：4 和 [1, 2, 3]，我們要的是 [1, 3]，需要排除掉 [3, 1]

出現(xiàn)這兩個問題，是因為遞歸過的被減數(shù)仍然保留在元祖中，所以我們需要把遞歸過的被減數(shù)移除掉

優(yōu)化一下：

  • 每次遞歸后移除當(dāng)前項
type GetNext<T extends number[]> = T extends [number, ...infer U] ? U : [];

type TwoSum<
  T extends number,
  L extends number[],
  R extends number[][] = [],
  Item extends number = L[0],
  SubItem extends number = Subtract<T, Item>,
  NextL extends number[] = GetNext<L>,
> = L['length'] extends 0 ?
  R : TwoSum<
    T,
    NextL,
    Includes<NextL, SubItem> extends true ? [
      ...R,
      [Item, SubItem]
    ] : R
  >;

測試

type t1 = TwoSum<7, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// [[0, 7], [1, 6], [2, 5], [3, 4]]

type t2 = TwoSum<12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// [[3, 9], [4, 8], [5, 7]]

type t3 = TwoSum<20, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// []

type t4 = TwoSum<10, [0, 8, 2, 1, 4, 7, 6, 3, 4, 9]>;
// [[8, 2], [1, 9], [4, 6], [7, 3], [6, 4]]

實現(xiàn)ThreeSum

實現(xiàn)排序

之前已經(jīng)實現(xiàn)typescript的快排，移步：用typescript類型來實現(xiàn)快排

為什么需要實現(xiàn)排序，因為上文中 TwoSum泛型的實現(xiàn)，需要滿足

  • 輸入?yún)?shù) - 被減數(shù) = 減數(shù)。所以 輸入?yún)?shù) > 被減數(shù) 、 輸入?yún)?shù) > 減數(shù)
  • 從頭選取參數(shù)、被減數(shù)、減數(shù)

所以排序后可以直接使用TwoSum泛型

實現(xiàn)ThreeSum

  • 遞歸元祖
  • 依次選擇 TwoSum的參數(shù)，剩余元組
  • 剩余元組中挑選符合條件的被減數(shù)、減數(shù)并返回
  • R為返回結(jié)果，NextL為剩余元組，NewList為合并TwoSum的結(jié)果
// 合并參數(shù)到TwoSum的結(jié)果，因為TwoSum返回的二元數(shù)組
type GetNewList<
  A extends number,
  T extends number[][],
  N extends number[] = [],
  R extends number[][] = []
> = T['length'] extends N['length'] ? R :
  GetNewList<A, T, [...N, 0], [...R, [A, ...T[N['length']]]]>;

type IsArray<T> = T extends number[] ? T : [];

type IsArray2<T> = T extends number[][] ? T : [];

type ThreeSumLoop<
  L extends number[],
  R extends number[][] = [],
  NextL extends number[] = GetNext<L>,
  NewList extends number[][] = IsArray2<TwoSum<L[0], NextL>>
> = L['length'] extends 0 | 1 ? R :
  ThreeSumLoop<NextL, NewList['length'] extends 0 ? R :
  IsArray2<[...R, ...GetNewList<L[0], NewList>]>>;

type ThreeSum<L extends number[]> = ThreeSumLoop<IsArray<QuickSort<L>>>;

測試

type l1 = ThreeSum<[1, 3, 2, 4]>;
// [[4, 3, 1], [3, 2, 1]]

type l2 = ThreeSum<[1, 6, 3, 7, 5, 4, 2]>;
// [[7, 6, 1], [7, 5, 2], [7, 4, 3], [6, 5, 1], [6, 4, 2], [5, 4, 1], [5, 3, 2], [4, 3, 1], [3, 2, 1]]

type l3 = ThreeSum<[0, 5, 15, 10, 5, 25, 20]>;
// [[25, 20, 5], [25, 15, 10], [20, 15, 5], [15, 10, 5], [10, 5, 5], [5, 5, 0]]

type l4 = ThreeSum<[1, 16, 3, 17, 5, 4, 21]>;
// [[21, 17, 4], [21, 16, 5], [17, 16, 1], [5, 4, 1], [4, 3, 1]]

到此這篇關(guān)于使用typescript類型實現(xiàn)ThreeSum的文章就介紹到這了,更多相關(guān)typescript ThreeSum內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評論