简单

69.x的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

  1. 输入：x = 4
  2. 输出：2

示例 2：

  1. 输入：x = 8
  2. 输出：2
  3. 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

  • 0 <= x <= 231 - 1

题解

  1. /**
  2. * @param {number} x
  3. * @return {number}
  4. */
  5. var mySqrt = function(x) {
  7. };

中等

50.Pow(x, n)

46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

  1. 输入：nums = [1,2,3]
  2. 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

  1. 输入：nums = [0,1]
  2. 输出：[[0,1],[1,0]]

示例 3：

  1. 输入：nums = [1]
  2. 输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

题解

递归

  1. /**
  2. * @param {number[]} nums
  3. * @return {number[][]}
  4. */
  5. // [1, 2, 3]
  6. // temp [1]
  7. var permute = function(nums) {
  8.   let list = [];
  9.   backtrack(list, [], nums);
  10.   return list;
  11. };
  13. function backtrack(list, temp, nums) {
  14.   // 终止条件
  15.   if (temp.length === nums.length) {
  16.     return list.push([...temp]);
  17.   }
  18.   for (let i = 0; i < nums.length; i++) {
  19.     if (temp.includes(nums[i])) continue;
  20.     temp.push(nums[i]);
  21.     backtrack(list, temp, nums);
  22.     temp.pop();
  23.   }
  24. }

79.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
image.png

  1. 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  2. 输出：true

示例 2：
image.png

  1. 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
  2. 输出：true

示例 3：
image.png

  1. 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
  2. 输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

题解

递归 + 回朔

  1. /**
  2. * @param {character[][]} board
  3. * @param {string} word
  4. * @return {boolean}
  5. */
  6. var exist = function(board, word) {
  7.   // 1.怎么找
  8.   // 2.什么时候终止
  9.   // 3.find内部 怎么找下一步（缓存存储中间的过程）
  11.   if (board.length === 0) return false;
  12.   if (word.length === 0) return true;
  13.   const row = board.length;
  14.   const col = board[0].length;
  15.   // 怎么找
  16.   for (let i = 0; i < row; i++) {
  17.     for (let j = 0; j < col; j++) {
  18.       let ret = find(i, j, 0);
  19.       if (ret) return true;
  20.     }
  21.   }
  22.   return false;
  24.   function find(i, j, cur) {
  25.     // 越界要停止
  26.     if (i >= row || i < 0) return false;
  27.     if (j >= col || j < 0) return false;
  28.     const letter = board[i][j];
  29.     // 字母不匹配
  30.     if (letter !== word[cur]) return false;
  31.     // 找到最后一个了，而且相等
  32.     if (cur === word.length - 1) return true;
  33.     // --终止条件
  34.     board[i][j] = null; // 当前路径标记为null
  35.     // ['A','B','C','E'],
  36.     // ['S','F','C','S'],
  37.     // ['A','D','E','E'],
  38.     const ret = find(i+1,j,cur+1) ||
  39.           find(i-1,j,cur+1) ||
  40.           find(i,j+1,cur+1) ||
  41.           find(i,j-1,cur+1);
  42.     board[i][j] = letter;
  43.     return ret;
  44.   }
  45. };

困难

51.N皇后