给面试官准备的礼物

遇到的手写题

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

typescript
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};
typescript
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);
typescript
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};
typescript
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};
typescript
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 */

二叉树的迭代遍历

  • 前序遍历
    typescript
    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}
  • 中序遍历
    typescript
    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}
  • 后序遍历
    typescript
    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}

整数转罗马数字

typescript
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 来判断最后的数组。

typescript
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}
typescript
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位比特又可分为三个部分:

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位以上的十进制数同时对应同一个双精度浮点数。

js
1console.log((0.30000000000000004).toString(2)); // 0.0100110011001100110011001100110011001100110011001101
2console.log((0.30000000000000003).toString(2)); // 0.0100110011001100110011001100110011001100110011001101
3console.log(0.30000000000000004 === 0.30000000000000003); // true
js
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位(由于 log10\log _ {10} ( 2532^ {53} ) \approx 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)S(-1)^ {S} ×\times (1.M) ×\times 2e2^ {e}
e=E-1023

十进制的数的双精度IEEE 754 64位浮点类型存储:0.1的二进制表示

整数部分十进制转其它进制的套路都很熟了,也就是辗转相除法;但是小数部分的转换好像有点陌生,不过大概的套路和辗转相除法有点相似,只不过变成了乘法。

  1. 1.将小数部分乘2,得到的数值其整数部分作为当前位进行存储;

  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位有效域的最右边的位给挤出去,这个时候挤出去的部分也会发生舍入。这就又会发生一次精度丢失。

js
10.1 初始值
20.1 转化为二进制:0.0 0011 0011 0011 0011 0011 0011 ...0011循环)
3e(阶码) = E - 1023 = -4;
4M(尾数)= 1.1001100110011001100110011001100110011001100110011010 (52)
js
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的值为:

js
10.1 对阶后的值
2e(阶码)= E - 1023 = -3;
3M(尾数)= 0.1100110011001100110011001100110011001100110011001101 (52)

然后进行相加,结果如下:

js
10.1 + 0.2 的结果
2e(阶码) = E - 1023 = -3;
3M(尾数)= 10.0110011001100110011001100110011001100110011001100111 (52)

然后这个结果小数点需要左移一位,然后e(阶码)加1然后在转换成10进制,左移一位的话又要舍去,所以又发生了精度丢失。最终的加法运算的结果自然就会不准。

特殊值

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER

js
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,安全存储的意思是指能够准确区分两个不相同的值。

    js
    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