338. Counting Bits

原题：338. Counting Bits

思路

DP + Bit Manupulation。主用运用 x & (x-1) 移除x最低位1的思想。。

source code

1
2
3
4
5
6
7
8
9
10
// Runtime: 96 ms, faster than 72.42% of JavaScript online submissions for Counting Bits.
// Memory Usage: 42.1 MB, less than 100.00% of JavaScript online submissions for Counting Bits.
var countBits = function (num) {
  const result = [0];
  for (let i = 1; i <= num; i++) {
    result[i] = result[i & (i - 1)] + 1;
  }

  return result;
};

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
test("test1", () => {
  expect(countBits(0)).toEqual([0]);
});

test("test2", () => {
  expect(countBits(1)).toEqual([0, 1]);
});

test("test3", () => {
  expect(countBits(2)).toEqual([0, 1, 1]);
});

test("test4", () => {
  expect(countBits(5)).toEqual([0, 1, 1, 2, 1, 2]);
});

展开全文 >>

231. Power of Two

原题：231. Power of Two

方法一

思路：求底，判断结果是否是整数

1
2
3
4
5
6
// Runtime: 88 ms, faster than 18.54% of JavaScript online submissions for Power of Two.
// Memory Usage: 36.6 MB, less than 15.38% of JavaScript online submissions for Power of Two.
var isPowerOfTwo = function(n) {
    let result = Math.log2(n);
    return ~~result == result;
};

方法二

思路：位运算，因为2的指数结果二进制一定是以1开头，剩下位数都是0的串。

1
2
3
4
5
// Runtime: 96 ms, faster than 15.25% of JavaScript online submissions for Power of Two.
// Memory Usage: 36.4 MB, less than 15.38% of JavaScript online submissions for Power of Two.
var isPowerOfTwo = function (n) {
  return n > 0 && !(n & (n - 1));//2为底的任意次方都一定>0
};

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
test("test1", () => {
  expect(isPowerOfTwo(1)).toEqual(true);
});

test("test2", () => {
  expect(isPowerOfTwo(16)).toEqual(true);
});

test("test3", () => {
  expect(isPowerOfTwo(218)).toEqual(false);
});

test("test4", () => {
  expect(isPowerOfTwo(-2147483648)).toEqual(false);
});

展开全文 >>

191. Number of 1 Bits

原题：191. Number of 1 Bits

思路

位运算。

source code

1
2
3
4
5
6
7
8
9
10
// Runtime: 72 ms, faster than 26.58% of JavaScript online submissions for Number of 1 Bits.
// Memory Usage: 36.1 MB, less than 10.00% of JavaScript online submissions for Number of 1 Bits.
var hammingWeight = function (n) {
  let count = 0;
  while (n != 0) {
    count++;
    n = n & (n - 1);
  }
  return count;
};

test case

1
2
3
test("test1", () => {
  expect(hammingWeight(11)).toEqual(3);
});

展开全文 >>

212. Word Search II

原题：212. Word Search II

方法一

思路

DFS。这道题借用了 79. Word Search 中的exist方法。

source code

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
39
40
41
42
43
44
45
46
47
48
49
50
// RuRuntime: 1352 ms, faster than 20.07% of JavaScript online submissions for Word Search II.
// Memory Usage: 45 MB, less than 100.00% of JavaScript online submissions for Word Search II.
var exist = function (board, word) {
  const helper = function (i, j, w) {
    if (w >= word.length) {
      return true;
    }
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
      //越界
      return false;
    }
    if (board[i][j] != word[w]) {
      return false;
    }
    //backtrace
    const tmp = board[i][j];
    board[i][j] = "*";
    if (
      helper(i - 1, j, w + 1) ||
      helper(i, j + 1, w + 1) ||
      helper(i + 1, j, w + 1) ||
      helper(i, j - 1, w + 1)
    ) {
      //上右下左
      return true;
    } else {
      board[i][j] = tmp;
      return false;
    }
  };

  if (!board || !board.length || !word) {
    //sanity check
    return false;
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (helper(i, j, 0)) {
        return true;
      }
    }
  }

  return false;
};

var findWords = function (board, words) {
  return words.filter((word) => exist(JSON.parse(JSON.stringify(board)), word));
};

方法二

思路

Trie。

//todo

test case

1
2
3
4
5
6
7
8
9
10
11
12
const board = [
  ["o", "a", "a", "n"],
  ["e", "t", "a", "e"],
  ["i", "h", "k", "r"],
  ["i", "f", "l", "v"],
];

test("test1", () => {
  expect(findWords(board, ["oath", "pea", "eat", "rain"]).sort()).toEqual(
    ["eat", "oath"].sort()
  );
});

展开全文 >>

79. Word Search

原题：79. Word Search

使用回溯法解决。

source code

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
39
40
41
42
43
44
45
46
// Runtime: 76 ms, faster than 89.67% of JavaScript online submissions for Word Search.
// Memory Usage: 38.2 MB, less than 76.92% of JavaScript online submissions for Word Search.
var exist = function (board, word) {
  const helper = function (i, j, w) {
    if (w >= word.length) {
      return true;
    }
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
      //越界
      return false;
    }
    if (board[i][j] != word[w]) {
      return false;
    }
    //backtrace
    const tmp = board[i][j];
    board[i][j] = "*";
    if (
      helper(i - 1, j, w + 1) ||
      helper(i, j + 1, w + 1) ||
      helper(i + 1, j, w + 1) ||
      helper(i, j - 1, w + 1)
    ) {
      //上右下左
      return true;
    } else {
      board[i][j] = tmp;
      return false;
    }
  };

  if (!board || !board.length || !word) {
    //sanity check
    return false;
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (helper(i, j, 0)) {
        return true;
      }
    }
  }

  return false;
};

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const board = [
  ["A", "B", "C", "E"],
  ["S", "F", "C", "S"],
  ["A", "D", "E", "E"],
];

test("test1", () => {
  expect(exist(JSON.parse(JSON.stringify(board)), "ABCCED")).toEqual(true);
});

test("test2", () => {
  expect(exist(JSON.parse(JSON.stringify(board)), "SEE")).toEqual(true);
});

test("test3", () => {
  expect(exist(JSON.parse(JSON.stringify(board)), "ABCB")).toEqual(false);
});

展开全文 >>

208. Implement Trie (Prefix Tree)

原题：208. Implement Trie (Prefix Tree)

source code

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
39
40
41
42
43
44
45
46
47
48
49
// Runtime: 212 ms, faster than 34.03% of JavaScript online submissions for Implement Trie (Prefix Tree).
// Memory Usage: 55.7 MB, less than 100.00% of JavaScript online submissions for Implement Trie (Prefix Tree).
class Trie {
  constructor() {
    this.arr = [];
    this.isWord = false;
  }

  insert(word) {
    if (!word) {
      return;
    }
    const queue = word.split("");
    let current = this;
    for (let i = 0; i < word.length; i++) {
      const ch = word[i];
      const index = ch.charCodeAt(0) - 97;
      let next = current.arr[index];
      if (!next) {
        next = current.arr[index] = new Trie();
      }
      current = next;
      if (i == word.length - 1) {
        next.isWord = true;
      }
    }
  }

  search(word) {
    const node = this._getPathNode(word);
    return !!(node && node.isWord);
  }

  startsWith(prefix) {
    return !!this._getPathNode(prefix);
  }

  _getPathNode(word) {
    let current = this;
    for (let i = 0; i < word.length; i++) {
      const next = current.arr[word[i].charCodeAt(0) - 97];
      if (!next) {
        return null;
      }
      current = next;
    }
    return current;
  }
}

展开全文 >>

69. Sqrt(x)

原题：69. Sqrt(x)

方法一

思路

二分法

要牢记二分法的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
let left = 0;
let right = arr.length-1;
while(left <= right) {
  let mid = (left + right) / 2;
  if(arr[mid] === target) {
    // find the target
    break or return result;
  }else if(arr[mid] < target) {
    left = mid + 1;
  }else {
    right = mid - 1;
  }
}

source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Runtime: 88 ms, faster than 35.63% of JavaScript online submissions for Sqrt(x).
// Memory Usage: 36.1 MB, less than 11.11% of JavaScript online submissions for Sqrt(x).
var mySqrt = function (x) {
  let left = 0;
  let right = x;
  while (left <= right) {
    let mid = ~~((left + right) / 2);
    let tmp = mid * mid;
    if (tmp == x) {
      return mid;
    } else if (tmp < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return right;
};

拓展

求sqart(x)，要求精度为n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// init variable
while(Math.abs(right-left)< 1/Math.pow(10, n)) {// 退出条件为小于具体的精度
  let mid = (left + right) / 2;
  let tmp = mid * mid;
  if (tmp == x) {
    return mid;
  } else if (tmp < x) {
    left = mid;// 这里不能+1
  } else {
    right = mid;// 这里不能-1
  }
}

return left;

方法二

思路

牛顿迭代法：

牛顿迭代法

这道题中，f(xn) = xn ^ 2 - y，f(xn)的导数 f'(xn) = 2 * xn。

最终可得：x(n+1) = (xn + y/xn)/2。

source code

1
2
3
4
5
6
7
8
9
10
// Runtime: 64 ms, faster than 95.63% of JavaScript online submissions for Sqrt(x).
// Memory Usage: 37.2 MB, less than 8.33% of JavaScript online submissions for Sqrt(x).
var mySqrt = function (x) {
  let r = x;
  while (r * r > x) {
    r = ~~((r + x / r) / 2);
  }

  return r;
};

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
test("test1", () => {
  expect(mySqrt(4)).toEqual(2);
});

test("test2", () => {
  expect(mySqrt(8)).toEqual(2);
});

test("test3", () => {
  expect(mySqrt(1)).toEqual(1);
});

test("test4", () => {
  expect(mySqrt(5)).toEqual(2);
});

展开全文 >>

37. Sudoku Solver

原题：37. Sudoku Solver

思路：backtrace + 适当剪枝，判断是否合法应用了36. Valid Sudoku的解法

时间复杂度：O(n^3)

source code

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Runtime: 192 ms, faster than 16.58% of JavaScript online submissions for Sudoku Solver.
// Memory Usage: 43.7 MB, less than 14.29% of JavaScript online submissions for Sudoku Solver.
var solveSudoku = function (board) {
  //判断是否合法，可以把这个单独抽离，使得整个程序逻辑更加清晰
  const set = new Set();
  const getKey = function (row, col, num) {
    const rowKey = `row_${row}_${num}`;
    const colKey = `col_${col}_${num}`;
    const boxKey = `box_${~~(row / 3)}_${~~(col / 3)}_${num}`;
    return [rowKey, colKey, boxKey];
  };

  const add = function (row, col, num) {
    const [rowKey, colKey, boxKey] = getKey(row, col, num);
    if (set.has(rowKey) || set.has(colKey) || set.has(boxKey)) {
      return false;
    }

    set.add(rowKey);
    set.add(colKey);
    set.add(boxKey);
    board[row][col] = "" + num;

    return true;
  };

  const remove = function (row, col, num) {
    const [rowKey, colKey, boxKey] = getKey(row, col, num);
    set.delete(rowKey);
    set.delete(colKey);
    set.delete(boxKey);
    board[row][col] = ".";
  };

  //初始化
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] === ".") {
        continue;
      }
      add(i, j, board[i][j]); //假设初始面板是合法的
    }
  }

  const helper = function () {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] !== ".") {
          continue;
        }
        for (var num = 1; num <= 9; num++) {
          if (add(i, j, num)) {
            if (helper()) {
              return true;
            } else {
              remove(i, j, num);
            }
          }
        }
        if (num > 9) {
          //如果某一个单元格所有数字都不可行，说明前面走错了
          return false;
        }
      }
    }

    return true;
  };

  helper();
};

test cases

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
const board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"],
];

solveSudoku(board);
console.log(board);

//output:
[ 
  [ '5', '3', '4', '6', '7', '8', '9', '1', '2' ],
  [ '6', '7', '2', '1', '9', '5', '3', '4', '8' ],
  [ '1', '9', '8', '3', '4', '2', '5', '6', '7' ],
  [ '8', '5', '9', '7', '6', '1', '4', '2', '3' ],
  [ '4', '2', '6', '8', '5', '3', '7', '9', '1' ],
  [ '7', '1', '3', '9', '2', '4', '8', '5', '6' ],
  [ '9', '6', '1', '5', '3', '7', '2', '8', '4' ],
  [ '2', '8', '7', '4', '1', '9', '6', '3', '5' ],
  [ '3', '4', '5', '2', '8', '6', '1', '7', '9' ] 
]

展开全文 >>

36. Valid Sudoku

原题：36. Valid Sudoku

方法一

思路：brute force

时间复杂度：O(n^2)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// Runtime: 96 ms, faster than 28.80% of JavaScript online submissions for Valid Sudoku.
// Memory Usage: 39.2 MB, less than 26.67% of JavaScript online submissions for Valid Sudoku.
var isValidSudoku = function (board) {
  const checkRow = function (row) {
    const set = new Set();
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === ".") {
        continue;
      }
      if (set.has(board[row][i])) {
        return false;
      }
      set.add(board[row][i]);
    }

    return true;
  };

  const checkCol = function (col) {
    const set = new Set();
    for (let i = 0; i < 9; i++) {
      if (board[i][col] === ".") {
        continue;
      }
      if (set.has(board[i][col])) {
        return false;
      }
      set.add(board[i][col]);
    }

    return true;
  };

  const checkSquare = function (x, y) {
    //左上角原点
    const set = new Set();
    for (let i = x; i < x + 3; i++) {
      for (let j = y; j < y + 3; j++) {
        if (board[i][j] === ".") {
          continue;
        }
        if (set.has(board[i][j])) {
          return false;
        }
        set.add(board[i][j]);
      }
    }

    return true;
  };

  for (let i = 0; i < 9; i++) {
    if (!checkRow(i) || !checkCol(i)) {
      return false;
    }
  }

  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (!checkSquare(i * 3, j * 3)) {
        return false;
      }
    }
  }

  return true;
};

方法二（Recommend）

思路：利用set缓存每一步的结果

时间复杂度：O(n^2)，实际上比方法一通用、高效很多

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
// Runtime: 100 ms, faster than 25.57% of JavaScript online submissions for Valid Sudoku.
// Memory Usage: 39.4 MB, less than 26.67% of JavaScript online submissions for Valid Sudoku.
var isValidSudoku = function (board) {
  const set = new Set();
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const grid = board[i][j];
      if (grid === ".") {
        continue;
      }
      const rowKey = `row_${i}_${grid}`;
      const colKey = `col_${j}_${grid}`;
      const boxKey = `box_${~~(i / 3)}_${~~(j / 3)}_${grid}`;
      if (set.has(rowKey) || set.has(colKey) || set.has(boxKey)) {
        return false;
      }

      set.add(rowKey);
      set.add(colKey);
      set.add(boxKey);
    }
  }

  return true;
};

test cases:

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
39
40
41
42
43
44
45
46
47
test("test1", () => {
  expect(
    isValidSudoku([
      ["5", "3", ".", ".", "7", ".", ".", ".", "."],
      ["6", ".", ".", "1", "9", "5", ".", ".", "."],
      [".", "9", "8", ".", ".", ".", ".", "6", "."],
      ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
      ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
      ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
      [".", "6", ".", ".", ".", ".", "2", "8", "."],
      [".", ".", ".", "4", "1", "9", ".", ".", "5"],
      [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ])
  ).toEqual(true);
});

test("test2", () => {
  expect(
    isValidSudoku([
      ["8", "3", ".", ".", "7", ".", ".", ".", "."],
      ["6", ".", ".", "1", "9", "5", ".", ".", "."],
      [".", "9", "8", ".", ".", ".", ".", "6", "."],
      ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
      ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
      ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
      [".", "6", ".", ".", ".", ".", "2", "8", "."],
      [".", ".", ".", "4", "1", "9", ".", ".", "5"],
      [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ])
  ).toEqual(false);
});

test("test3", () => {
  expect(
    isValidSudoku([
      [".", ".", ".", ".", "5", ".", ".", "1", "."],
      [".", "4", ".", "3", ".", ".", ".", ".", "."],
      [".", ".", ".", ".", ".", "3", ".", ".", "1"],
      ["8", ".", ".", ".", ".", ".", ".", "2", "."],
      [".", ".", "2", ".", "7", ".", ".", ".", "."],
      [".", "1", "5", ".", ".", ".", ".", ".", "."],
      [".", ".", ".", ".", ".", "2", ".", ".", "."],
      [".", "2", ".", "9", ".", ".", ".", ".", "."],
      [".", ".", "4", ".", ".", ".", ".", ".", "."],
    ])
  ).toEqual(false);
});

展开全文 >>

51. N-Queens

原题：51. N-Queens

思考

这道题主要用到 回溯 的思想解题。
n-queen
假设第i行Q占据图中的位置，则她的四条攻击路径如图所示。

容易得出：路径3（撇）经过的单元格都有y+x=c1，路径4（捺）经过的单元格都有y-x=c2，其中c1/c2是一个常数。

  • 由于我们逐行扫描，所以路径1必然不会冲突。
  • 对于路径2，使用col标记已经占用的列
  • 对于路径3，使用xySum标记已经被占用的撇
  • 对于路径4，使用xyDiff标记已经占用的捺

最后回溯即可。

source code

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
39
40
41
42
43
44
// Runtime: 88 ms, faster than 33.33% of JavaScript online submissions for N-Queens.
// Memory Usage: 39.3 MB, less than 100.00% of JavaScript online submissions for N-Queens.
var solveNQueens = function (n) {
  //左上角为原点，横向为x，纵向为y
  const col = {}; //列
  const xySum = {}; //撇，y+x=c
  const xyDiff = {}; //捺，y-x=c
  const result = [];

  const helper = function (y, tmp) {
    //x为第几行
    //tmp为中间结果，值为第y行皇后的位置
    if (y >= n) {
      //到底
      result.push(tmp);
      return;
    }
    for (let x = 0; x < n; x++) {
      //对每一列假设求解
      if (!col[x] && !xySum[x + y] && !xyDiff[y - x]) {
        col[x] = 1;
        xySum[x + y] = 1;
        xyDiff[y - x] = 1;

        helper(y + 1, [...tmp, x]);

        //恢复现场
        col[x] = 0;
        xySum[x + y] = 0;
        xyDiff[y - x] = 0;
      }
    }
  };

  helper(0, []);

  return result.map((v) =>
    v.map((qi) => {
      const arr = new Array(n).fill(".");
      arr[qi] = "Q";
      return arr.join("");
    })
  );
};

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
test("test1", () => {
  expect(solveNQueens(4).sort()).toEqual(
    [
      [
        ".Q..", // Solution 1
        "...Q",
        "Q...",
        "..Q.",
      ],

      [
        "..Q.", // Solution 2
        "Q...",
        "...Q",
        ".Q..",
      ],
    ].sort()
  );
});

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

不思进取的前端开发攻城狮。<br>梦想是躺着也能拯救世界。