【面试题】算法

爬楼梯

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
// 缓存
const cache = new Map();
export default function fib(n: number): number {
  if (n === 1) return 1;
  if (n === 2) return 2;
  if (cache.has(n)) {
    return cache.get(n);
  }
  let ret = fib(n - 1) + fib(n - 2);
  cache.set(n, ret);
  return ret;
}

合并两个排序的链表

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
export default function mergeTwoLists(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }

  if (l1.val > l2.val) {
    l2.next = mergeTwoLists(l1.next, l2);
    return l2;
  } else {
    l1.next = mergeTwoLists(l2.next, l1);
    return l1;
  }
}

反转链表

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
export default function reverseList(head: ListNode): ListNode | null {
  let perv,
    cur: any = head,
    temp;
  while (cur) {
    temp = cur.next;
    cur.next = perv;
    perv = cur;
    cur = temp;
  }
  return perv;
}

判断链表是否有环

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function hasCycle(head: ListNode | null): boolean {
  if (head === null || head.next === null) {
    return false;
  }

  let slow: ListNode | null = head;
  let fast: ListNode | null = head.next;

  while (fast !== slow) {
    if (fast === null || fast.next === null) {
      return false;
    }

    fast = fast.next?.next;
    slow = (slow as ListNode).next;
  }
  return true

有效的括号字符串

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
export default function checkValidString(s: string): boolean {
  let l = 0,
    r = 0;
  for (let k of s) {
    if (k === "(") {
      l++;
      r++;
    } else if (k === ")") {
      l = Math.max(0, l - 1);
      r--;
      if (r < 0) return false;
    } else {
      l = Math.max(0, l - 1);
      r++;
    }
  }
  return l == 0;
}

数组中的第 K 个最大元素

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
export default function findKthLargest(nums: number[], k: number): number {
  const sortNums = qsSort(nums);
  return sortNums[k - 1];
}

function qsSort(nums: number[]): number[] {
  if (nums.length <= 1) {
    return nums;
  }
  let left = [];
  let right = [];

  let temp = nums.splice(0, 1)[0];

  for (let v of nums) {
    if (temp < v) {
      left.push(v);
    } else {
      right.push(v);
    }
  }
  return [...qsSort(left), temp, ...qsSort(right)];
}

具有给定数值的最小字符串

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
export default function getSmallestString(n: number, k: number): string {
  let arr = new Array(n).fill("a");
  let reduceK = k - n;
  let i = n - 1;
  while (reduceK) {
    if (reduceK > 25) {
      arr[i] = "z";
      reduceK -= 25;
      i--;
    } else {
      arr[i] = String.fromCharCode(97 + reduceK);
      reduceK = 0;
    }
  }
  return arr.join("");
}

二叉树的深度

题目地址

1
2
3
export default function maxDepth(root: TreeNode | null): number {
  return root ? Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 : 0;
}

二叉树的层序遍历

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
export default function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const queue = [root];
  const res: any[] = [];

  while (queue.length > 0) {
    const arr = [];
    let len = queue.length;
    while (len--) {
      const node = queue.shift();
      arr.push(node?.val);
      if (node?.left) {
        queue.push(node.left);
      }
      if (node?.right) {
        queue.push(node.right);
      }
    }
    res.push(arr);
  }
}

x 的平方根

题目地址

1
2
3
4
5
6
7
8
export default function mySqrt(x: number): number {
  if (x == 1 || x == 0) return x;
  let start = 1;
  while (start * start < x && !((start + 1) * (start + 1) > x)) {
    start++;
  }
  return start;
}

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function mySqrt(x: number): number {
  if (x == 0 || x == 1) {
    return x;
  }
  let left = 1;
  let res: number = 0;
  let right = Math.floor(x / 2);
  while (left <= right) {
    let mid = (left + right) >> 1;
    if (x / mid >= mid) {
      res = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return res;
}

字符的最短距离

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function shortestToChar(s: string, c: string): number[] {
  let start = s[0] == c ? 0 : s.length;
  let pos = s.indexOf(c, 1);
  let arr = [];

  for (let i = 0; i < s.length; i++) {
    arr[i] = Math.min(Math.abs(i - start), Math.abs(i - pos));

    if (i === pos) {
      start = pos;
      pos = s.indexOf(c, start + 1);
    }
  }
  return arr;
}

翻转二叉树

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;

  invertTree(root.left);
  invertTree(root.right);

  let temp = root?.left;
  root.left = root?.right;
  root.right = temp;

  return root;
}

判断是否是回文数

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function isPalindrome(x: number): boolean {
  if (x < 0 || (x % 10 == 0 && x != 0)) return false;

  let changeData = 0;
  let l = x;

  while (l) {
    let yu = l % 10;
    l = Math.floor(l / 10);
    changeData = changeData * 10 + yu;
  }

  return x === changeData;
}

反转字符串

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
export default function reverseString(s: string[]): void {
  let temp;
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (left == right) return;
    temp = s[left];
    s[left] = s[right];
    s[right] = temp;
    left++;
    right--;
  }
}

第 k 个数

题目地址

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
export default function getKthMagicNumber(k: number): number {
  let resultArr: number[] = [1];
  let point3 = 0;
  let point5 = 0;
  let point7 = 0;

  for (let i = 1; i < k; i++) {
    let res3 = resultArr[point3] * 3;
    let res5 = resultArr[point5] * 5;
    let res7 = resultArr[point7] * 7;

    let resultN = Math.min(Math.min(res3, res5), res7);
    if (resultN % 3 === 0) {
      point3++;
    }
    if (resultN % 5 === 0) {
      point5++;
    }
    if (resultN % 7 === 0) {
      point7++;
    }

    resultArr[i] = resultN;
  }

  return resultArr[k - 1];
}

最小 K 个数

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
export default function smallestK(arr: number[], k: number): number[] {
  const qrSrot = (arr: number[]): number[] => {
    if (arr.length <= 1) {
      return arr;
    }

    const node = arr.splice(0, 1)[0];
    let left = [];
    let right = [];
    for (let v of arr) {
      if (v > node) {
        right.push(v);
      } else {
        left.push(v);
      }
    }
    return [...qrSrot(left), node, ...qrSrot(right)];
  };

  return qrSrot(arr).slice(0, k);
}

二叉树的中序遍历

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
export default function inorderTraversal(root: TreeNode | null): number[] {
  const arr: number[] = [];
  const fn = (node: TreeNode | null): void => {
    if (node) {
      fn(node.left);
      arr.push(node.val);
      fn(node.right);
    }
  };
  fn(root);
  return arr;
}

最长不含重复字符的子字符串

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
export default function lengthOfLongestSubstring(s: string): number {
  const length = s.length;
  const map = new Map();
  let i = 0,
    j = 0;
  let ans = 0;
  while (i < length && j < length) {
    let jv = s[j];
    if (map.has(jv) && map.get(jv) > i) {
      i = map.get(jv) + 1;
    }
    ans = Math.max(j - i + 1, ans);
    map.set(jv, j);
    ++j;
  }
  return ans;
}

分发饼干

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
export default function findContentChildren(g: number[], s: number[]): number {
  const sortCookie = s.sort((a, b) => a - b);
  const sortChild = g.sort((a, b) => a - b);

  let cookieLen = sortCookie.length;
  let childLen = sortChild.length;

  let posCookie = 1;
  let posChild = 1;

  while (cookieLen - posCookie >= 0 && childLen - posChild >= 0) {
    if (sortCookie[cookieLen - posCookie] >= sortChild[childLen - posChild]) {
      posCookie++;
    }
    posChild++;
  }
  return posCookie - 1;
}

正则匹配

题目地址

最小栈

题目地址

二叉树的右视图

题目地址

✏️ 如有问题,欢迎指正
下一篇 : 【面试题】手写代码