Published by powerfulyang on Oct 9, 2022

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
/**
* 'a.b.c' to {a: {b: {c: null}}}
*/
export const strToObject = (str: string) => {
  const arr = str.split('.');
  let obj = null;
  arr.reverse().forEach((item) => {
    obj = { [item]: obj };
  });
  return obj;
};

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
type CurryingReturn<F> = F extends (...args: infer A) => infer Return
  ? A extends [infer G, ...infer Rest]
    ? (arg: G) => CurryingReturn<(...args: Rest) => Return>
    : Return
  : never;

declare function Currying<F>(fn: F): CurryingReturn<F>;

const curry = Currying((a: number, b: number, c: number) => a + b + c);

curry(1)(2)(3);

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
12
function totalHammingDistance(nums: number[]): number {
      let ans = 0;
      let n = nums.length;
      for (let i = 0; i < 30; i++) {
          let c = 0;
          for (const val of nums) {
              c += (val >> i) & 1;
          }
          ans += c * (n - c);
      }
      return ans;
};

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
function maxProfit(prices: number[]): number {
  let min = prices[0];
  let maxProfit = 0;

  for (const price of prices) {
      min = Math.min(min, price);
      maxProfit = Math.max(maxProfit, price - min);
  }

  return maxProfit;
};

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

class Solution {
  private head: ListNode = null;

  constructor(head: ListNode | null) {
      this.head = head;
  }

  getRandom(): number {
  // 从链表头开始，遍历整个链表，对遍历到的第 i 个节点，随机选择区间 [0,i) 内的一个整数，如果其等于 0，则将答案置为该节点值，否则答案不变。

      let i = 1, ans = 0;
      for (let node = this.head; node != null; node = node.next) {
          if (Math.floor(Math.random() * i) === 0) { // 1/i 的概率选中（替换为答案）
              ans = node.val;
          }
          ++i;
      }
      return ans;
  }
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(head)
 * var param_1 = obj.getRandom()
 */

• 前序遍历

  typescript
  Copy Code
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  export const preOrder = (root: TreeNode) => {
    const helperStack = [root];
    const ans = [];
    while (helperStack.length) {
      const current = helperStack.pop();
      ans.push(current.val);
      if (current.right) {
        helperStack.push(current.right);
      }
      if (current.left) {
        helperStack.push(current.left);  
      }
    }
    return ans;
  }

• 中序遍历

  typescript
  Copy Code
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  export const inOrder = (root: TreeNode) => {
    const helperStack = [];
    const ans = [];
    let current = root;
    while (helperStack.length || current) {
      if (current) {
        helperStack.push(current);
        current = current.left;
      } else {
        current = helperStack.pop();
        ans.push(current.val);
        current = current.right;
      }
    }
  }

• 后序遍历

  typescript
  Copy Code
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  export const postOrder = (root: TreeNode) => {
    const helperStack = [];
    const ans = [];
    let current = root;
    let previousHandled = null;
    while (helperStack.length || current) {
      while (current) {
        helperStack.push(current);
        current = current.left;
      }
      current = helperStack[helperStack.length - 1];
      if (!current.right || current.right === previousHandled) { // 右边没有节点或右边的节点被处理过
        current = helperStack.pop(); // 回退
        ans.push(current.val);
        previousHandled = current; // 记录处理过的节点
        current = null;
      } else { // 右边有节点且右边的节点没有被处理过
        current = current.right;
      }
    }
  }

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function intToRoman(num: number): string {
    const map = new Map([
        [1000, 'M'],
        [900, 'CM'],
        [500, 'D'],
        [400, 'CD'],
        [100, 'C'],
        [90, 'XC'],
        [50, 'L'],
        [40, 'XL'],
        [10, 'X'],
        [9, 'IX'],
        [5, 'V'],
        [4, 'IV'],
        [1, 'I']
    ]);
    let ans = '';
    while (num > 0) {
        for (const [key, value] of map) {
            if (num >= key) {
                num -= key;
                ans += value;
                break;
            }
        }
    }
    return ans;
};

其实这里感觉上是一个 counting sort, 我为什么会愚蠢的用 every 来判断最后的数组。

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
12
13
export function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) {
    return false;
  }
  const array = new Array<number>(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    array[s.charCodeAt(i) - a]++;
    array[t.charCodeAt(i) - a]--;
  }
  // fast fail
  return !array.some((x) => x !== 0);
}

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
export const groupAnagrams = (strs: string[]) => {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const charFreq = Array.from({ length: 26 }, () => 0);
    for (let i = 0; i < s.length; i++) charFreq[s.charCodeAt(i) - 97]++;
    const keyStr = charFreq.toString();
    if (!map.has(keyStr)) map.set(keyStr, []);
    map.get(keyStr).push(s);
  }
  return Array.from(map.values());
};