给面试官准备的礼物
遇到的手写题
类似 '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); // true
1// 二进制小数转成十进制
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: true
Double 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