小宋爱睡觉
  • 数组
Crucials
2022-02-07

回溯

# 回溯

# lc46. 全排列中等hot

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

思路

由题可得如果用暴力法面试会被直接挂掉，或者算法超时，可以采用dfs + 回溯(撤销)进行解答

看了这个图就对这道全排列比较直观了，同时也有一定的解题模版

const result = []
function backtrack(路径, 选择列表) {
    if 满足结束条件:
        result.push(路径)
        return
    
    for 选择 of 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
}
1
2
3
4
5
6
7
8
9
10
11

下面就来干起

var permute = function(nums) {
  const res = []
  const backtrack = (number) => {
    if(number.length === nums.length) {
      res.push([...number])
      return 
    }
    for(let i = 0; i < nums.length; i++) {
      if(number.includes(nums[i])) {
        continue
      }
      number.push(nums[i])
      backtrack(number)
      number.pop()
    }
  }
  dfs([])
  return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度:O(n×n!)

对于 backtrack 调用的次数/每个叶结点(概率论里面的C(n, k) = n! / (n - k)! 共 n! 个)，我们需要将当前答案使用 O(n) 的时间复制到答案数组中，相乘得时间复杂度为 O(n×n!)。

空间复杂度：O(n)，其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)

# lc47. 全排列 II中等hot

题目描述

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

示例 2：

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

思路：和全排列一 一样但是多了去重

var permuteUnique = function(nums) {
  const res = [], visited = {}
  nums.sort((a, b) => a - b)
  const dfs = (track) => {
    if(track.length === nums.length) {
      res.push([...track])
      return
    }

    for(let i = 0; i < nums.length; i++) {
      if(visited[i]) continue
      if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue
      track.push(nums[i])
      visited[i] = true
      dfs(track)
      track.pop()
      visited[i] = false 
    }
  }
  dfs([])
  return [...res]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度:O(n×n!)

空间复杂度：O(n)

# 剑指 Offer 38. 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例一:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
1
2

示例二

输入：s = "aab"
输出：["aab","aba","baa"]
1
2

思路

和全排列II 不一样的地方在于本题可以用set来去重字符串

跟前面的有一点区别是他的字母是有可能重复的

var permutation = function(s) {
  const res = new Set(), visited = {}
  const dfs = (track) => {
    if(track.length === s.length) {
      // res.push(track)
      res.add(track)
      return
    }

    for(let i = 0; i < s.length; i++) {
      if(visited[i]) continue
      
      visited[i] = true
      dfs(track + s[i])
      visited[i] = false 
    }
  }
  dfs('')
  return [...res]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# lc77. 组合中等hot

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
1
2
3
4
5
6
7
8
9
10

示例 2：

输入：n = 1, k = 1
输出：[[1]]
1
2

思路

还是套模版,只不过原来的按模版的会超时，我们可以剪一下枝

var combine = function(n, k) {
  const res = []
  let start = 1
  const dfs = (start, nums) => {
    if(nums.length === k) {
      res.push([...nums])
      return
    }
    for(let i = start; i <= n; i++) {
      if(nums.includes(i)) {
        continue
      } else {
        nums.push(i)
        dfs(i + 1, nums)
        nums.pop()
      }
    }
  }
  dfs(start, [])
  return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度:O(C(n, k) * n),参照上面的全排列，C(n, k) = n! / (n - k)!

空间复杂度:O(n)递归的深度是n

# lc93. 复原 IP 地址中等hot

题目描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
1
2

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]
1
2

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
1
2
var restoreIpAddresses = function(s) {
  const len = s.length
  const res = []

  const findIP = (start, path) => {

    if(path.length === 4 && start >= len) {
      res.push(path.join('.'))
      return 
    }

    for(let i = start; i < len; i++) {
      const str = s.slice(start, i + 1)
      if(isValid(str)) {
        path.push(str)
        findIP(i + 1, path)
        path.pop()
      } else break
    }
  }

  const isValid = (str) => {
    if(str.length > 4) return false
    if(parseInt(str, 10) > 255) return false
    if(str.length > 1 && str[0] === '0') return false

    return true
  }

  findIP(0, [])

  return res
};
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

# lc78. 子集中等

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

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

思路

这一道题就可以套模板了，只不过这里的dfs的push要在if外面，因为输出的res不一定与nums的length相等

var subsets = function(nums) {
  const result = [];
  helper(nums, 0, [], result);
  return result;
};

function helper(nums, start, track, result) {

  result.push([...track]);

  if (track.length === nums.length) {
    return
  }

  for (let i = start; i < nums.length; i++) {
    track.push(nums[i]);
    helper(nums, i + 1, track, result);
    track.pop();
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# lc139. 单词拆分中等

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意： 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
1
2
3

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。
1
2
3
4

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
1
2

思路

const wordBreak = (s, wordDict) => {
	const len = s.length;
  	const wordSet = new Set(wordDict);

	const canBreak = (start) => { // 判断从start到末尾的子串能否break
		if (start == len) {//指针越界，s一步步成功划分为单词，才走到越界这步，现在没有剩余子串
			return true;   //返回真，结束递归
		}
		for (let i = start + 1; i <= len; i++) { //指针i去划分两部分，for枚举出当前所有的选项i
			const prefix = s.slice(start, i);    // 切出的前缀部分
			if (wordSet.has(prefix) && canBreak(i)) {// 前缀部分是单词，且剩余子串能break，返回真
				return true;                            
			} // 如果前缀部分不是单词，就不会执行canBreak(i)。进入下一轮迭代，再切出一个前缀串，再试
		}
		return false; // 指针i怎么划分，都没有返回true，则返回false
	}

	return canBreak(0); // 递归的入口，从0到末尾的子串能否break
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

超时了

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

空间复杂度:O(n)

记忆化回溯

const wordBreak = (s, wordDict) => {
	const len = s.length;
  const wordSet = new Set(wordDict);
  const memo = new Array(len)
	const canBreak = (start) => { // 判断从start到末尾的子串能否break
		if (start == len) {//指针越界，s一步步成功划分为单词，才走到越界这步，现在没有剩余子串
			return true;   //返回真，结束递归
		}
    if(memo[start] !== undefined) return memo[start] // memo中有，就用memo中的
		for (let i = start + 1; i <= len; i++) { //指针i去划分两部分，for枚举出当前所有的选项i
			const prefix = s.slice(start, i);    // 切出的前缀部分
			if (wordSet.has(prefix) && canBreak(i)) {// 前缀部分是单词，且剩余子串能break，返回真
      memo[start] = true
				return true;                            
			} // 如果前缀部分不是单词，就不会执行canBreak(i)。进入下一轮迭代，再切出一个前缀串，再试
		}
    memo[start] = false
		return false; // 指针i怎么划分，都没有返回true，则返回false
	}

	return canBreak(0); // 递归的入口，从0到末尾的子串能否break
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

另解：动态规划

var wordBreak = function(s, wordDict) {
  const len = s.length
  const wordDictSet = new Set(wordDict)
  const dp = new Array(len + 1).fill(false)
  dp[0] = true
  for(let i = 1; i <= len; i++) {
    for(let j = 0; j < i; j++) {
      if(dp[j] && wordDictSet.has(s.slice(j, i))) {
        dp[i] = true
        break
      }
    }
  }
  return dp[len]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

空间复杂度:O(n)

# lc140. 单词拆分 II困难

题目描述

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意： 词典中的同一个单词可能在分段中被重复使用多次。

示例 1：

输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]
1
2

示例 2：

输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
解释: 注意你可以重复使用字典中的单词。
1
2
3

示例 3：

输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出:[]
1
2

思路

var wordBreak = function (s, wordDict) {
  let arr = [];
  function backTree(n, path) {
    if (n === s.length) {
      arr.push(path);
    } else {
      for (let i = 1; i <= s.length - n; i++) {
        if (wordDict.indexOf(s.substr(n, i)) !== -1) {
          if (n !== 0) {
            backTree(n + i, path + " " + s.substr(n, i));
          } else {
            backTree(n + i, path + s.substr(n, i));
          }
        }
      }
    }
  }
  backTree(0, "");
  return arr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# lc22. 括号生成中等hot

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
1
2

示例 2：

输入：n = 1
输出：["()"]
1
2

思路

可以看成🌲的dfs

截屏2022-01-16 下午4.56.04

然后对🌲进行剪枝

剪枝标准

  • 右括号数量大于左括号(其中就包括了开头是右括号的情况)
  • 左括号数量大于n的值

终止条件，字符串长度等于2 * n

var generateParenthesis = function(n) {
  const dfs = (path, open, close) => {
    if(close > open || open > n) return false

    if(path.length === 2 * n) {
      res.push(path)
      return res
    }
    dfs(path + '(', open + 1, close)
    dfs(path + ')', open, close + 1)
  }
  const res = []
  dfs('', 0, 0)
  return res 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# lc79. 矩阵中的路径/单词搜索中等hot

题目描述

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

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

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

示例 1：

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

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
1
2

思路： DFS

递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。 终止条件： 返回 false ：

  1. 行或列索引越界
  2. 当前矩阵元素与目标字符不同
  3. 当前矩阵元素已访问过 (3) 可合并至 (2)

返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。 递推工作： 标记当前矩阵元素： 将 board[i][j] 修改为 空字符 '' ，代表此元素已访问过，防止之后搜索时重复访问。 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。 还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。 返回值： 返回布尔量 res ，代表是否搜索到目标字符串。

var exist = function(board, word) {
  for(let i = 0; i < board.length; i++) {
    for(let j = 0; j < board[0].length; j++) {
      if(dfs(board, word, i, j, 0)) return true
    }
  }
  return false
};

function dfs(board, word, i, j, k) {
  if(i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1 || board[i][j] !== word[k]) return false

  if(k === word.length - 1) return true
  
  board[i][j] = ''
  let res = dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i, j - 1, k + 1) || dfs(board, word, i, j + 1, k + 1)
  board[i][j] = word[k]
  return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

M,N 分别为矩阵行列大小， K 为字符串 word 长度。

时间复杂度O(3^K * MN) 最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案，时间复杂度为 O(3^K) 矩阵中共有 MN 个起点，时间复杂度为 O(MN) 方案数计算： 设字符串长度为 K ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 3 种选择，因此方案数的复杂度为 O(3^K)

空间复杂度 O(K) ： 搜索过程中的递归深度不超过 K ，因此系统因函数调用累计使用的栈空间占用 O(K) 最坏情况下 K = MN，递归深度为 MN ，此时系统栈使用 O(MN)的额外空间

# 39. 组合总和/两数之和回溯中等hot

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
1
2
3
4
5
6

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
1
2

示例 3：

输入: candidates = [2], target = 1
输出: []
1
2

思路

标准的回溯模版

var combinationSum = function(candidates, target) {
  candidates.sort((a, b) => a - b)
  const res = []

  const dfs = (start, temp, track) => {
    if(temp === target) {
      res.push([...track])
      return
    }

    for(let i = start; i < candidates.length; i++) {
      if(temp + candidates[i] <= target) {
        temp += candidates[i]
        track.push(candidates[i])
        dfs(i, temp, track)
        track.pop()
        temp -= candidates[i]
      }
    }
  }
  dfs(0, 0, [])
  return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度:O(n)

空间复杂度:O(n)，最坏O(target)

# 加起来和为目标值的组合(二)中等

题目描述

给出一组候选数 c 和一个目标数 t ，找出候选数中起来和等于 t 的所有组合。

c 中的每个数字在一个组合中只能使用一次。

注意：

  1. 题目中所有的数字（包括目标数 t ）都是正整数
  2. 组合中的数组递增
  3. 结果中不能包含重复的组合
  4. 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

要求：空间复杂度 O(n!) ， 时间复杂度 O(n!)

示例1

输入：[100,10,20,70,60,10,50],80

返回值：[[10,10,60],[10,20,50],[10,70],[20,60]]

说明：给定的候选数集是[100,10,20,70,60,10,50]，目标数是80
1
2
3
4
5

示例2

输入：[2],1

返回值：[]
1
2
3

思路

function combinationSum2( num ,  target ) {
    // write code here
  	// 对原数组排序
    num.sort((a, b) => a - b)
    const temp = [], res = []
    dfs(num, target, 0, temp, res, 0)
    return res
}

function dfs(num, target, temp,tempArr, res, start) {
  	// 遍历的元素的累加值
    if(temp === target) {
        res.push([...tempArr])
        return
    }
  	// 越界
    if(start >= num.length) return
    
    for(let i = start; i < num.length; i++) {
        // 去重
        if(i > start && num[i] === num[i - 1]) continue

        if(temp + num[i] <= target) {
            temp += num[i]
            tempArr.push(num[i])
            dfs(num, target, temp, tempArr, res, i + 1)
            // 回溯 撤销操作
            tempArr.pop()
            temp -= num[i]
        }
    }
}
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

时间复杂度:O(n)

空间复杂度:O(n)

# lc17. 电话号码的字母组合中等

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2

示例 2：

输入：digits = ""
输出：[]
1
2

示例 3：

输入：digits = "2"
输出：["a","b","c"]
1
2

思路：dfs + 回溯

这道题有暴力法可以解，但是要嵌套三次循环，采用dfs可以降时间复杂度

var letterCombinations = function (digits) {
  // 为空特殊处理
  if (digits.length === 0) return [];
  let numMap = new Map([
    ['0', ''],
    ['1', ''],
    ['2', 'abc'],
    ['3', 'def'],
    ['4', 'ghi'],
    ['5', 'jkl'],
    ['6', 'mno'],
    ['7', 'pqrs'],
    ['8', 'tuv'],
    ['9', 'wxyz']
  ])
  let res = [];
  dfs("", digits);
  return res;

  function dfs(str, digit) {
    // 如果字符串为空了，将拼接好的字符加入数组
    if (digit.length === 0) res.push(str);
    else {
      // 拿到字符串第一个字符，拿到其对应的数字
      let numstr = numMap.get(digit[0]);
      // 对可能性进行组合
      for (let i = 0; i < numstr.length; i++) {
        str += numstr[i];
        // 递归组好的 str和下一段字符串
        dfs(str, digit.slice(1))
        // 回溯
        str = str.slice(0, -1);
        // dfs(str+numstr[i], digit.slice(1))
      }
    }
  }
};
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

# lc38. 外观数列中等

题目描述

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

  • countAndSay(1) = "1"
  • countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
1
2
3
4
5
6
7
8
9
10

要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

img

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。
1
2
3

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
1
2
3
4
5
6
7

思路

很简单的一道递归题

var countAndSay = function(n) {
  if(n === 1) return '1'
  let pre = countAndSay(n - 1)

  let str = '', left = 0, right = 0
  while(right < pre.length) {
    while(pre[left] === pre[right] && right < pre.length) right++

    str += (String(right - left) + pre[left])
    left = right
  }

  return str
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度:O(n)

空间复杂度:O(n) 每层递归都创建pre存储f(n - 1)

思路二：滚动数组

用pre代替f(n - 1)降低空间复杂度

var countAndSay = function(n) {
  let pre = '1', str = '1'
  for(let i = 1; i < n; i++) {
    pre = str
    str = ''
    let left = 0, right = 0
    while(right < pre.length) {
      while(pre[left] === pre[right] && right < pre.length) right++

      str += (String(right - left) + pre[left])
      left = right
    }
  }
  return str
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度:O(n)

空间复杂度:O(1)

# lc131. 分割回文串中等

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
1
2

示例 2：

输入：s = "a"
输出：[["a"]]
1
2

思路

标准动态规划

var partition = function(s) {
  var res = [], path = []
  var backTrack = (start) => {
      if (start > s.length) return false
      if (start === s.length) {
          res.push(path.slice())
          return false
      }
      for (let i = start; i < s.length; i ++) {
          if(isValid(s, start, i)) {
              var str = s.substr(start, i - start + 1);
              path.push(str)
              backTrack(i + 1)
              path.pop()
          }
      }
  }
  backTrack(0)
  return res
};
// 双指针判断回文串
var isValid = (str, start, end) => {
  for(let i = start, j = end; i < j; i ++, j--) {
      if (str[i] !== str[j]) return false
  }
  return true
}
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

# 51. N 皇后困难hot

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

img

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
1
2
3

示例 2：

输入：n = 1
输出：[["Q"]]
1
2

思路

不能在同一行 同一列 或同一条斜线上

var solveNQueens = function(n) {
  function isValid(row, col, chessBoard, n) {
    //不用判断同一行的因为回溯就是在同一行不同列放置皇后
    for(let i = 0; i < row; i++) {
      // 同一列的判断
      if(chessBoard[i][col] === 'Q') {
        return false
      }
    }
    for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      // 135度斜角判断 左上斜线 不需要判断下面的
      if(chessBoard[i][j] === 'Q') {
        return false
      }
    }
      // 45度斜角判断 右上斜线 不需要判断下面的
    for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if(chessBoard[i][j] === 'Q') {
        return false
      }
    }
    return true
  }

  function transformChessBoard(chessBoard) {
    // 转换一下输出
    let chessBoardBack = []
    chessBoard.forEach(row => {
      let rowStr = ''
      row.forEach(value => {
        rowStr += value
      })
      chessBoardBack.push(rowStr)
    })

    return chessBoardBack
  }

    let result = []
    function backtracing(row,chessBoard) {
      if(row === n) {
        // 最后一行 能放下了就已经算成功了
        result.push(transformChessBoard(chessBoard))
        return
      }
      for(let col = 0; col < n; col++) {
        // 遍历列 回溯行
        if(isValid(row, col, chessBoard, n)) {
          chessBoard[row][col] = 'Q'
          backtracing(row + 1,chessBoard)
          chessBoard[row][col] = '.'
        }
      }
    }
    let chessBoard = Array.from(new Array(n), ()=> new Array(n).fill('.'))
    backtracing(0,chessBoard)
    return result
};
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
上次更新: 2022/03/21, 11:27:08
双指针或哈希表
二分

← 二分→

Copyright © 2021-2022 粤ICP备2021165371号