给面试官准备的礼物
Published by powerfulyang on Oct 9, 2022
遇到的手写题
类似 'a.b.c' 转换成对应对象格式
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; };
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);
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; };
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; };
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() */
二叉树的迭代遍历
- 前序遍历
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; }
- 中序遍历
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; } } }
- 后序遍历
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; } } }
整数转罗马数字
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 来判断最后的数组。
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); }
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()); };