leetcode: A JavaScript repository from 615349

1, for ListNode

function ListNode(value) {
  this.value = value;
  this.next = null;
}

or

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

//initialization
const left = new ListNode(0);

//for testing
const left = {
  value: 0,
  next: {
    value: 1,
    next: null
  }
}

2a, swap two numbers by bitwise operation

exchange two values by normal way

tmp = a;
a = b;
b = tmp;

exchange without extra variable 注意，这个方法有两个限制条件首先只适用于交换数字的情况其次，i和j不能相等

a = a ^ b;
b = a ^ b;
a = a ^ b;

第二句

b = a ^ b ^ b;
b ^ b is 0, a ^ 0 is a. (假如a是110110 ^ 0 = 110110， 因为1和0不同，不同所以为1，0和0相同，相同所以为0)

第三句

a = a ^ b, 这里a = a ^ b, b = a
so
a = a ^ b ^ a === b

注意，如果这个方法用来交换数组的两个index，要注意两个index必须不同

const swap = (nums, i, j) => {
	nums[i] = nums[i] ^ nums[j];
	nums[j] = nums[i] ^ nums[j];
	nums[i] = nums[i] ^ nums[j];
}

考虑nums=[2], i = 0, j = 0，经过这样的交换后nums变成了[0] 见075

2b, swap two numbers by destructing

const swap = (a, b) => [b, a];
let a = 100, b = 200;
[b, a] = swap(a, b);

3, complexity 二分法一般都是o(logn)

4, 取中点

let mid = Math.floor((left + right)/2);
这样可能导致溢出。
所以一般是
mid = left + Math.floor((right - left)/2);

5, 初始化二维数组，其每个元素都是一个数组

const dp = [];
const n = 3;
while(dp.push(new Array(n).fill(0)) < n);

得到的结果是
[
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0]
]
而不是下面这个，因为下面是一维数组
[
	0, 0, 0,
	0, 0, 0,
	0, 0, 0
]

6, dfs 在dfs函数里，当条件满足时，如果是对数组进行操作，要对该数组进行拷贝操作比如

const dfs = (nums, array, result) => {
  if (nums.length === array.length) {
    result.push([...array]);
  } else {
    for (let i = 0; i < nums.length; i++) {
      if (array.includes(nums[i])) {
        continue;
      }

      array.push(nums[i]);
      dfs(nums, array, result);
      array.pop();
    }
  }
};

具体结果可以在046里面查看

如果这个数组是二维数组，那么不能直接像上面一样进行拷贝，而需要对每个元素单独进行拷贝

const getClone = arr => {
  const clone = [];
  for (let i = 0; i < arr.length; i++) {
    clone[i] = [...arr[i]];
  }
  return clone;
};

7, concat concat can be applied to both array and string, and the original array/string would be intact

const str = str1.concat(str2);
const arr = arr1.concat(arr2);

8, Math.min it accepts more than 2 arguments, like

Math.min(1, 2, 3) === 1

const array = [1, 2, 3];
Math.min(...array) === 1

9, -0

0 === -0
1/0 === Infinity
1/-0 === -Infinity

check 073 for more details

10, get row number and column number of a matrix

if(!matrix) {
	return 0;
}
const m = matrix.length;
if(m === 0) return 0;

const n = matrix[0].length;
if(n === 0) return 0;

11, access ith of string

const s = 'welcome';
s[5]
or
s.charAt(5);

12, b-tree, binary tree, and binary search tree b-tree may have multiple nodes. binary tree is one kind of b-tree, but has only two nodes BST is one kind of binary tree, it has below features:

the left subtree of a node contains only nodes with less key
the right subtree of a node contains only nodes with larger key
the left and right subtree each must be a BST
no duplicated nodes

13, binary search tree 空树也是一种二叉树

14, MIN and MAX

1, bit operation
MIN = 1 << 31;
MAX = ~(1 << 31);

2, Number
Number.MIN_SAFE_INTEGER
Number.MAX_SAFE_INTEGER

15, BFS (breadth first search) https://www.programiz.com/dsa/graph-bfs

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbours of u

16, preorder, inorder, postorder 简单说，pre 或者in或者post都是对于root节点来说的。 pre就是先访问root，in是先左子树后root最后右zishu，post是先左子树后右zishu最后root

以上图为例，preorder是3, 9, 15, 7, 20 inorder是15, 9, 7, 3, 20 postorder 15, 7, 9, 20, 3

200, 中英文对照 product (which means 积) facebook interview question, leetcode 238 the interviewer stated that division is very expensive

even: 偶数 odd: 奇数

dividend: 被除数 divisor: 除数 quotient: 商被除数 / 除数 = 商

615349/leetcode