https://leetcode-cn.com/tag/backtracking/
52. N皇后 II难度困难
60. 第k个排列难度中等 [✔]
77. 组合难度中等 [✔]
78. 子集难度中等
79. 单词搜索难度中等 [✔]
89. 格雷编码难度中等
90. 子集 II难度中等
93. 复原IP地址难度中等
126. 单词接龙 II难度困难(只求看懂题解)
131. 分割回文串难度中等 [✔]
52. N皇后 II难度困难
n皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
提示：
皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。（引用自 百度百科 - 皇后 ）
思路：
class Solution {
private boolean[] col;
private boolean[] dia1;
private boolean[] dia2;
public int totalNQueens(int n) {
col = new boolean[n];
dia1 = new boolean[2 * n - 1]; // 对角线个数为 2 * n - 1
dia2 = new boolean[2 * n - 1];
return putQueen(n, 0);
}
/**
* 递归回溯方式摆放皇后
*
* @param n 待摆放皇后个数
* @param row 已摆放皇后个数
*/
public int putQueen(int n, int row){
int res = 0;
if(row == n) return 1;
// 表示在 row 行的第 i 列尝试摆放皇后
for(int i = 0; i < n; i++){
if(!col[i] && !dia1[row + i] && ! dia2[row - i + n - 1]){
col[i] = true;
dia1[row + i] = true;
dia2[row - i + n - 1] = true;
res += putQueen(n, row + 1);//递归
col[i] = false;
dia1[row + i] = false;
dia2[row - i + n - 1] = false;
}
}
return res;
}
}
60. 第k个排列难度中等
给出集合
[1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。
示例 :
输入: n = 3, k = 3
输出: "213"
思路：回溯
class Solution {//执行用时：8 ms, 在所有 Java 提交中击败了33.77%的用户
public String getPermutation(int n, int k) {
int[] nums = new int[n];
for(int i=0;i<n;i++){
nums[i] = i + 1;//生成nums数组
}
boolean[] used = new boolean[n];//记录当前的索引的数是否被使用过
return dfs(nums, new ArrayList<String>(), used, 0, n, k);
}
/**
* @param nums 源数组
* @param levelList 每一层的选择
* @param used 数组的元素是否被使用过
* @param depth 深度，也就是当前使用的元素的索引
* @param n 上限值
* @param k 第k个
* @return 第k个排列
*/
private String dfs(int[] nums, List<String> levelList, boolean[] used, int depth, int n, int k){
if(depth == n){//触发出口条件，开始收集结果集
StringBuilder res = new StringBuilder();
for (String s : levelList) res.append(s);
return res.toString();
}
int cur = factorial(n - depth - 1);//当前的depth也就是索引，有多少排列数
for(int i=0;i<n;i++){
if (used[i]) continue;//当前元素被使用过，做剪枝
if (cur < k) {//当前的排列组合数小于k，说明就算这一层排完了，也到不了第k个，剪枝
k -= cur;
continue;//不执行循环体剩余部分，直接进行下次循环
}
levelList.add(nums[i] + "");//list收的是string类型
used[i] = true;//当前元素被使用过标记
return dfs(nums, levelList, used, depth + 1, n, k);
}
return null;
}
//返回n的阶乘，如3!=3*2*1=6
private int factorial(int n) {
int res = 1;
while (n > 0) {
res *= n--;
}
return res;
}
}
77. 组合难度中等
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[ [2,4],[3,4],[2,3], [1,2],[1,3],[1,4],]
思路：回溯
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
if(n <= 0 || k <= 0 || n < k) return res;
backtrack(n, k, 1, new ArrayList<>());
return res;
}
public void backtrack(int n, int k, int start, List<Integer> list){
if(list.size() == k){
res.add(new ArrayList<>(list));
}
for(int i = start; i <= n; i++){
//for(int i = start; i <= n - (k - list.size()) + 1; i++){
list.add(i);
backtrack(n, k, i + 1, list);
list.remove(list.size() - 1);
}
}
}
78. 子集难度中等
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
思路：回溯
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
public void backtrack(int start, int[] nums, List<List<Integer>> res, List<Integer> list){
res.add(new ArrayList<>(list));
for(int i = start; i < nums.length; i++){
list.add(nums[i]);
backtrack(i + 1, nums, res, list);
list.remove(list.size() - 1);
}
}
}
79. 单词搜索难度中等
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
思路：回溯
class Solution {
int rows;
int cols;
char[][] board;
char[] word_ch;// 需要寻找的字符数组
public boolean exist(char[][] board, String word) {
this.rows = board.length;
this.cols = board[0].length;
this.board = board;
this.word_ch = word.toCharArray();
boolean[][] used = new boolean[rows][cols];
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(backtrack(i ,j, 0, used)){
return true;
}
}
}
return false;
}
public boolean backtrack(int row, int col, int index, boolean[][] used){
// 当前位置不存在或者使用过，则返回失败
if(row < 0 || row >= rows || col < 0 || col >= cols || used[row][col]){
return false;
}
if(board[row][col] != word_ch[index]){
return false;
}
if(index == word_ch.length - 1){
return true; // 全部找完了
}
used[row][col] = true; // 设置当前格使用过了
// 寻找上下左右是否有符合下一个的情况
boolean flag = backtrack(row + 1, col, index + 1, used) || backtrack(row - 1, col, index + 1, used)
|| backtrack(row, col + 1, index + 1, used) || backtrack(row, col - 1, index + 1, used) ;
used[row][col] = false;// 上下左右的情况都走完了，因此回退，设置当前格没有使用过
return flag;
}
}
89. 格雷编码难度中等
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数* n*，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。
90. 子集 II难度中等
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
93. 复原IP地址难度中等
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 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 地址。
提示：
0 <= s.length <= 3000
s 仅由数字组成
思路：回溯
class Solution {
public List<String> restoreIpAddresses(String s) {
int len = s.length();
List<String> res = new ArrayList<>();
if(len < 4 || len > 12){
return res;
}
Deque<String> path = new ArrayDeque<>(4);
int splitTimes = 0;
dfs(s, len, splitTimes, 0, path, res);
return res;
}
/**
* @param s :字符串
* @param len :字符串长度
* @param split :已经分割出多少个 ip 段
* @param begin :截取 ip 段的起始位置
* @param path :记录从根结点到叶子结点的一个路径
* @param res :记录结果集的变量
* @return
*/
private void dfs(String s, int len, int split, int begin, Deque<String> path, List<String> res) {
if (begin == len) {
if (split == 4) {//由于 ip 段最多就 4 个段
res.add(String.join(".", path));
}
return;
}
// 看到剩下的不够了，就退出（剪枝），len - begin 表示剩余的还未分割的字符串的位数
if (len - begin < (4 - split) || len - begin > 3 * (4 - split)) {
return;
}
for (int i = 0; i < 3; i++) {
if (begin + i >= len) {
break;
}
int ipSegment = judgeIfIpSegment(s, begin, begin + i);
if (ipSegment != -1) {
// 在判断是 ip 段的情况下，才去做截取
path.addLast(ipSegment + "");
dfs(s, len, split + 1, begin + i + 1, path, res);
path.removeLast();
}
}
}
//判断 s 的子区间 [left, right] 是否能够成为一个 ip 段
private int judgeIfIpSegment(String s, int left, int right) {
int len = right - left + 1;
if(len > 1 && s.charAt(left) == '0'){
return -1;
}
int res = 0;
for(int i = left; i <= right; i++){
res = res * 10 + s.charAt(i) - '0';
}
if(res > 255){
return -1;
}
return res;
}
}
126. 单词接龙 II难度困难
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 *beginWord *到 *endWord *的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。
转换后得到的单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 *endWord *是非空的，且二者不相同。
要先学会127. 单词接龙
思路：回溯
使用BFS建立邻接表的过程不熟悉，通过邻接表，使用回溯算法得到所有从起点单词到终点单词的路径这步可以独立完成。代码是摘抄自大佬的题解https://leetcode-cn.com/problems/word-ladder-ii/solution/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you--2/
自己是真的写不出来，只求看懂！
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
List<List<String>> res = new ArrayList<>();
if(wordSet.size() == 0 || !wordSet.contains(endWord)){
return res;
}
// 第 1 步：使用广度优先遍历得到后继结点列表 successors
// key：字符串，value：广度优先遍历过程中 key 的后继结点列表
Map<String,Set<String>> successors = new HashMap<>();
boolean found = bfs(beginWord, endWord, wordSet, successors);
if(!found){
return res;
}
// 第 2 步：基于后继结点列表 successors ，使用回溯算法得到所有最短路径列表
Deque<String> path = new ArrayDeque<>();
path.addLast(beginWord);
dfs(beginWord, endWord, successors, path, res);
return res;
}
public boolean bfs(String beginWord, String endWord, Set<String> wordSet, Map<String,Set<String>> successors){
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
boolean found = false;
int len = beginWord.length();
// 当前层访问过的结点，当前层全部遍历完成以后，再添加到总的 visited 集合里
Set<String> nextLevelVisited = new HashSet<>();
while(!queue.isEmpty()){
int currentSize = queue.size();
for(int i = 0; i < currentSize; i++){
String currentWord = queue.poll();
char[] charArray = currentWord.toCharArray();
for(int j = 0; j < len; j++){
char originChar = charArray[j];//从这里开始不理解了
for (char k = 'a'; k <= 'z'; k++) {
if (charArray[j] == k) {
continue;
}
charArray[j] = k;
String nextWord = new String(charArray);
if (wordSet.contains(nextWord)) {
if (!visited.contains(nextWord)) {
if (nextWord.equals(endWord)) {
found = true;
}
// 避免下层元素重复加入队列，这里感谢 https://leetcode-cn.com/u/zhao-da-ming/ 优化了这个逻辑
if (!nextLevelVisited.contains(nextWord)) {
queue.offer(nextWord);
nextLevelVisited.add(nextWord);
}
// 维护 successors 的定义
successors.computeIfAbsent(currentWord, a -> new HashSet<>());
successors.get(currentWord).add(nextWord);
}
}
}
charArray[j] = originChar;
}
}
if (found) {
break;
}
visited.addAll(nextLevelVisited);
nextLevelVisited.clear();
}
return found;
}
private void dfs(String beginWord, String endWord,
Map<String, Set<String>> successors,
Deque<String> path, List<List<String>> res) {
if (beginWord.equals(endWord)) {
res.add(new ArrayList<>(path));
return;
}
if (!successors.containsKey(beginWord)) {
return;
}
Set<String> successorWords = successors.get(beginWord);
for (String nextWord : successorWords) {
path.addLast(nextWord);
dfs(nextWord, endWord, successors, path, res);
path.removeLast();
}
}
}
131. 分割回文串难度中等
给定一个字符串 s，将* s *分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
思路：回溯
class Solution {
public List<List<String>> partition(String s) {
int len = s.length();
List<List<String>> res = new ArrayList<>();
if(len == 0) return res;
List<String> path = new ArrayList<>();
backtrack(s, 0, len, path, res);
return res;
}
/**
* @param s
* @param start 起始字符的索引
* @param len 字符串 s 的长度，可以设置为全局变量
* @param path 记录从根结点到叶子结点的路径
* @param res 记录所有的结果
*/
private void backtrack(String s, int start, int len, List<String> path,List<List<String>> res){
if(start == len){
res.add(new ArrayList<>(path));
return;
}
for(int i = start; i < len; i++){
if(!checkPalindrome(s, start, i)){
continue;
}
path.add(s.substring(start, i + 1));
backtrack(s, i + 1, len, path, res);
path.remove(path.size() - 1);
}
}
private boolean checkPalindrome(String str, int left, int right){
while(left < right){
if(str.charAt(left) != str.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
网友评论