给面试官准备的礼物
Published by powerfulyang on Oct 9, 2022
遇到的手写题
类似 'a.b.c' 转换成对应对象格式
1/**
2* 'a.b.c' to {a: {b: {c: null}}}
3*/
4export const strToObject = (str: string) => {
5 const arr = str.split('.');
6 let obj = null;
7 arr.reverse().forEach((item) => {
8 obj = { [item]: obj };
9 });
10 return obj;
11};1type CurryingReturn<F> = F extends (...args: infer A) => infer Return
2 ? A extends [infer G, ...infer Rest]
3 ? (arg: G) => CurryingReturn<(...args: Rest) => Return>
4 : Return
5 : never;
6
7declare function Currying<F>(fn: F): CurryingReturn<F>;
8
9const curry = Currying((a: number, b: number, c: number) => a + b + c);
10
11curry(1)(2)(3);1function totalHammingDistance(nums: number[]): number {
2 let ans = 0;
3 let n = nums.length;
4 for (let i = 0; i < 30; i++) {
5 let c = 0;
6 for (const val of nums) {
7 c += (val >> i) & 1;
8 }
9 ans += c * (n - c);
10 }
11 return ans;
12};1function maxProfit(prices: number[]): number {
2 let min = prices[0];
3 let maxProfit = 0;
4
5 for (const price of prices) {
6 min = Math.min(min, price);
7 maxProfit = Math.max(maxProfit, price - min);
8 }
9
10 return maxProfit;
11};1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13class Solution {
14 private head: ListNode = null;
15
16 constructor(head: ListNode | null) {
17 this.head = head;
18 }
19
20 getRandom(): number {
21 // 从链表头开始，遍历整个链表，对遍历到的第 i 个节点，随机选择区间 [0,i) 内的一个整数，如果其等于 0，则将答案置为该节点值，否则答案不变。
22
23 let i = 1, ans = 0;
24 for (let node = this.head; node != null; node = node.next) {
25 if (Math.floor(Math.random() * i) === 0) { // 1/i 的概率选中（替换为答案）
26 ans = node.val;
27 }
28 ++i;
29 }
30 return ans;
31 }
32}
33
34/**
35 * Your Solution object will be instantiated and called as such:
36 * var obj = new Solution(head)
37 * var param_1 = obj.getRandom()
38 */二叉树的迭代遍历
- 前序遍历
1export const preOrder = (root: TreeNode) => { 2 const helperStack = [root]; 3 const ans = []; 4 while (helperStack.length) { 5 const current = helperStack.pop(); 6 ans.push(current.val); 7 if (current.right) { 8 helperStack.push(current.right); 9 } 10 if (current.left) { 11 helperStack.push(current.left); 12 } 13 } 14 return ans; 15} - 中序遍历
1export const inOrder = (root: TreeNode) => { 2 const helperStack = []; 3 const ans = []; 4 let current = root; 5 while (helperStack.length || current) { 6 if (current) { 7 helperStack.push(current); 8 current = current.left; 9 } else { 10 current = helperStack.pop(); 11 ans.push(current.val); 12 current = current.right; 13 } 14 } 15} - 后序遍历
1export const postOrder = (root: TreeNode) => { 2 const helperStack = []; 3 const ans = []; 4 let current = root; 5 let previousHandled = null; 6 while (helperStack.length || current) { 7 while (current) { 8 helperStack.push(current); 9 current = current.left; 10 } 11 current = helperStack[helperStack.length - 1]; 12 if (!current.right || current.right === previousHandled) { // 右边没有节点或右边的节点被处理过 13 current = helperStack.pop(); // 回退 14 ans.push(current.val); 15 previousHandled = current; // 记录处理过的节点 16 current = null; 17 } else { // 右边有节点且右边的节点没有被处理过 18 current = current.right; 19 } 20 } 21}
整数转罗马数字
1function intToRoman(num: number): string {
2 const map = new Map([
3 [1000, 'M'],
4 [900, 'CM'],
5 [500, 'D'],
6 [400, 'CD'],
7 [100, 'C'],
8 [90, 'XC'],
9 [50, 'L'],
10 [40, 'XL'],
11 [10, 'X'],
12 [9, 'IX'],
13 [5, 'V'],
14 [4, 'IV'],
15 [1, 'I']
16 ]);
17 let ans = '';
18 while (num > 0) {
19 for (const [key, value] of map) {
20 if (num >= key) {
21 num -= key;
22 ans += value;
23 break;
24 }
25 }
26 }
27 return ans;
28};其实这里感觉上是一个 counting sort, 我为什么会愚蠢的用 every 来判断最后的数组。
1export function isAnagram(s: string, t: string): boolean {
2 if (s.length !== t.length) {
3 return false;
4 }
5 const array = new Array<number>(26).fill(0);
6 const a = 'a'.charCodeAt(0);
7 for (let i = 0; i < s.length; i++) {
8 array[s.charCodeAt(i) - a]++;
9 array[t.charCodeAt(i) - a]--;
10 }
11 // fast fail
12 return !array.some((x) => x !== 0);
13}1export const groupAnagrams = (strs: string[]) => {
2 const map = new Map<string, string[]>();
3 for (const s of strs) {
4 const charFreq = Array.from({ length: 26 }, () => 0);
5 for (let i = 0; i < s.length; i++) charFreq[s.charCodeAt(i) - 97]++;
6 const keyStr = charFreq.toString();
7 if (!map.has(keyStr)) map.set(keyStr, []);
8 map.get(keyStr).push(s);
9 }
10 return Array.from(map.values());
11};八股
'a' 和 String('a') 和 new String('a')?
- new String('a') => 本质是对象object了，引用类型，值保存在堆内存 heap 中。
- 'a' string 类型，基本类型的值保存在 stack 栈 内存中。
- String('a') 同 2
js 浮点数运算不精确 如何解决?
JavaScript 中所有数字包括整数和小数都只有一种类型 - Number，它的实现遵循 IEEE 754 标准，使用 64 位固定长度来表示，也就是标准的 double 双精度浮点数。
这样的存储结构优点是可以归一化处理整数和小数，节省存储空间。
64位比特又可分为三个部分：
- Sign bit: 1 bit
- Exponent: 11 bits
- Significand precision: 53 bits (52 explicitly stored)
The sign bit determines the sign of the number (including when this number is zero, which is signed).
The exponent field is an 11-bit unsigned integer from 0 to 2047, in biased form: an exponent value of 1023 represents the actual zero. Exponents range from −1022 to +1023 because exponents of −1023 (all 0s) and +1024 (all 1s) are reserved for special numbers.
The 53-bit significand precision gives from 15 to 17 significant decimal digits precision (2^−53 ≈ 1.11 × 10^−16). If a decimal string with at most 15 significant digits is converted to the IEEE 754 double-precision format, giving a normal number, and then converted back to a decimal string with the same number of digits, the final result should match the original string. If an IEEE 754 double-precision number is converted to a decimal string with at least 17 significant digits, and then converted back to double-precision representation, the final result must match the original number.
有效位数在15位以下的十进制数转成双精度浮点数再转回去不会丢失精度。
可以将双精度数转成有效位数17位以上的十进制数再转回来是可以的，但是要注意可能有多个有效位数17位以上的十进制数同时对应同一个双精度浮点数。
1console.log((0.30000000000000004).toString(2)); // 0.0100110011001100110011001100110011001100110011001101
2console.log((0.30000000000000003).toString(2)); // 0.0100110011001100110011001100110011001100110011001101
3console.log(0.30000000000000004 === 0.30000000000000003); // true1// 二进制小数转成十进制
2const doubleToDecimal = (binary) => {
3 const float = binary.split('.')[1];
4 // 小数部分
5 const arr = float.split('');
6 const bArr = arr.map((currentValue, index) => {
7 return Number(currentValue) * Math.pow(2, -(index + 1));
8 });
9 return bArr.reduce((accumulator, currentValue) => {
10 return accumulator + currentValue;
11 });
12};双精度IEEE 754 64位浮点类型的确切精度
双精度IEEE 754 64位浮点类型的精度最高到16位(由于 ( ) 15.95 所以能够保证15位)。
尾数部分一共占52位，加上固定的1，一共53位，可以有53个1。可以表示小数，也可以表示整数。因为尾数部分表示的是有效数字，指数部分只是小数点左移右移。
当53位的1做二进制的小数时（零点1，一共53个1），转化为10进制是1 - 1 / 2^53，求值后，有效数字是16位。（ 1 / 2^53 = 1.1102230246251565e-16）。
当53位的1做二进制的整数时（一共53个1），转化为10进制大概是2^53 - 1，也就是最大安全数，有效数字是16位。
注意，上面的小数或整数是16位，但是不代表十进制的所有16位整数或小数点后的16位小数都能表示，超过上面两个值的十进制整数或小数，是无法精确表示的，所以才会存在安全数的概念。所以是最高到16位，因为无法覆盖16位的每一种情况。
公式如下
x= (1.M)
e=E-1023
十进制的数的双精度IEEE 754 64位浮点类型存储：0.1的二进制表示
整数部分十进制转其它进制的套路都很熟了，也就是辗转相除法；但是小数部分的转换好像有点陌生，不过大概的套路和辗转相除法有点相似，只不过变成了乘法。
-
1.将小数部分乘2，得到的数值其整数部分作为当前位进行存储；
-
2.将上述得到的数值小数部分重复1步骤，直到小数部分为0；
计算过程如下：
0.1 * 2 = 0.2 取整数部分0，得到小数部分0.2，不为0，继续；整数部分0为二进制新一位。
0.2 * 2 = 0.4 取整数部分0，得到小数部分0.4，不为0，继续；整数部分0为二进制新一位。
0.4 * 2 = 0.8 取整数部分0，得到小数部分0.8，不为0，继续；整数部分0为二进制新一位。
0.8 * 2 = 1.6 取整数部分1，得到小数部分0.6，不为0，继续；整数部分1为二进制新一位。
0.6 * 2 = 1.2 取整数部分1，得到小数部分0.2，不为0，继续；整数部分1为二进制新一位。
0.2 * 2 = 0.4 取整数部分0，得到小数部分0.4，不为0，继续；整数部分0为二进制新一位。
0.4 * 2 = 0.8 取整数部分0，得到小数部分0.8，不为0，继续；整数部分0为二进制新一位。
0.8 * 2 = 1.6 取整数部分1，得到小数部分0.6，不为0，继续；整数部分1为二进制新一位。
0.6 * 2 = 1.2 取整数部分1，得到小数部分0.2，不为0，继续；整数部分1为二进制新一位。
0.2 * 2 = 0.4 取整数部分0，得到小数部分0.4，不为0，继续；整数部分0为二进制新一位。
0.4 * 2 = 0.8 取整数部分0，得到小数部分0.8，不为0，继续；整数部分0为二进制新一位。
0.8 * 2 = 1.6 取整数部分1，得到小数部分0.6，不为0，继续；整数部分1为二进制新一位。
……然后你发现，开始循环了。😂
所以十进制的0.1转换成二进制是0.0001 1001 1001的循环。这尾数部分的长度远远超过了我们规定的52位！！那这个时候就需要一个类似10进制的四舍五入也就是我最一开始提到的近似存储。IEEE 754规定了几种舍入规则。默认的是四舍六入五留双(又称银行家算法)具体的怎舍入这里就不提了。舍入的目的是为了尽可能的使64位双精度浮点数转换成的十进制数接近原始的十进制10。比如上面1/10这个值采用双精度IEEE 754 64位浮点类型存储后在转换成十进制之后是0.1000000000000000055511151231257827021181583404541015625。和最初的0.1还是有偏差的，这就是舍入的缺点，所以造成了精度丢失。这里我们说完了JS中0.1+0.2 !== 0.3的第一个原因，那就是某些小数，存储的时候就已经精度丢失了（产生了偏差）。
为什么 0.1+0.2=0.30000000000000004？
浮点数参与计算时，浮点数参与计算时，有一个步骤叫对阶，以加法为例，要把小的指数域转化为大的指数域，也就是左移小指数浮点数的小数点，一旦小数点左移，必然会把52位有效域的最右边的位给挤出去，这个时候挤出去的部分也会发生舍入。这就又会发生一次精度丢失。
10.1 初始值
20.1 转化为二进制：0.0 0011 0011 0011 0011 0011 0011 ... （0011循环）
3e（阶码） = E - 1023 = -4;
4M（尾数）= 1.1001100110011001100110011001100110011001100110011010 (52位)10.2 初始值
20.2 转化为二进制：0.0011 0011 0011 0011 0011 0011 0011 ... （0011循环）
3e（阶码） = E - 1023 = -3;
4M（尾数）= 1.1001100110011001100110011001100110011001100110011010 (52位)我们发现，e的值不一样，这时候需要对阶要把0.1的M小数点左移一位，阶码e加1，变成了-3，所以就和0.2的阶码一致了。对阶之后，0.1的值为：
10.1 对阶后的值
2e（阶码）= E - 1023 = -3;
3M（尾数）= 0.1100110011001100110011001100110011001100110011001101 (52位)然后进行相加，结果如下：
10.1 + 0.2 的结果
2e（阶码） = E - 1023 = -3;
3M（尾数）= 10.0110011001100110011001100110011001100110011001100111 (52位)然后这个结果小数点需要左移一位，然后e（阶码）加1然后在转换成10进制，左移一位的话又要舍去，所以又发生了精度丢失。最终的加法运算的结果自然就会不准。
特殊值
1const x = Number.MAX_SAFE_INTEGER + 1;
2const y = Number.MAX_SAFE_INTEGER + 2;
3
4console.log(Number.MAX_SAFE_INTEGER);
5// Expected output: 9007199254740991
6
7console.log(x);
8// Expected output: 9007199254740992
9
10console.log(x === y);
11// Expected output: trueDouble precision floating point format only has 52 bits to represent the mantissa, so it can only safely represent integers between -(2**53 – 1) and 2**53 – 1. "Safe" in this context refers to the ability to represent integers exactly and to compare them correctly. For example, Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2 will evaluate to true, which is mathematically incorrect.
-
JS中最大值
Number.MAX_VALUE：当符号位为0、指数取到1023、小数位全为1时，为可表示的最大值。1.79E+308或21024。比其大的数视为无穷大 -
JS中最小值
Number.MIN_VALUE：当符号位为0、指数位全为0（表示非规格浮点数）、小数位仅最后一位为1时，为可表示的最小正值。大约是5e-324 -
JS中最大安全数
Number.MAX_SAFE_INTEGER：9007199254740991或2^53 - 1，安全存储的意思是指能够准确区分两个不相同的值。1Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2但是 。因Number.MAX_SAFE_INTEGER * 2 !== Number.MAX_SAFE_INTEGER + 2为乘了2之后，e会+1。比较时64位中的尾数域虽然相同，但是指数域不相同。
-
JS中最小安全数
Number.MIN_SAFE_INTEGER：-9007199254740991或-(2^53 - 1)。 -
JS中的非数字
Number.NaN：表示“非数字”（Not-A-Number）。和 NaN相同。 -
JS中Number.EPSILON
Number.EPSILON：表示 1 与 Number 可表示的大于 1 的最小的浮点数之间的差值。其值接近于2.2204460492503130808472633361816E-16，或者 2^-52。
可以用来测试是否浮点数预算结果和预期是否相等: Math.abs(0.3 - (0.1 + 0.2)) < Number.EPSILON。为true时表示0.3 - (0.1+0.2) ≈ 0（误差小于Number.EPSILON）。
Precision limitations on integer values
二进制能精确地表示位数有限且分母是2的倍数的小数
- Integers from −2^53 to 2^53 (−9,007,199,254,740,992 to 9,007,199,254,740,992) can be exactly represented
- Integers between 2^53 and 2^54 = 18,014,398,509,481,984 round to a multiple of 2 (even number)
- Integers between 2^54 and 2^55 = 36,028,797,018,963,968 round to a multiple of 4