给面试官准备的礼物

遇到的手写题

类似 'a.b.c' 转换成对应对象格式

typescript
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
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
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
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
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
    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
    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
    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;
        }
      }
    }