递归与回溯问题
2020/7/24大约 5 分钟
汉诺塔问题
解题思路
1、假设有n个盘子需要移动
2、首先将最上面的n-1个盘子从A借助C移到B柱子
3、然后将最下面的一个盘子从A移到C柱子
4、最后将B当作A，A当作B，将n-1个盘子从B借助C移动到A柱子，再将B柱子最后一个移动到C上（实际重复了2-3步骤，只是把A、B参考对象对换）
5、当只剩下最后一个时，从A移动到C就可以了
Java代码
public class Hanota {
public static void main(String[] args) {
List<Integer> a = new ArrayList<>();
List<Integer> b = new ArrayList<>();
List<Integer> c = new ArrayList<>();
a.add(2);
a.add(1);
a.add(0);
new Hanota().hanota(a,b,c);
System.out.println(c);
}
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
move(A.size(), A, B, C);
}
public void move(int n, List<Integer> A, List<Integer> B, List<Integer> C){
if(n == 1){
C.add(A.get(A.size() - 1));
A.remove(A.size() - 1);
}else{
// 把A经过辅助C放到B上
move(n - 1, A, C, B);
// 把A放到C上
C.add(A.get(A.size() - 1));
A.remove(A.size() - 1);
// 把B经过辅助A放到C上
move(n - 1, B, A, C);
}
}
}/**
* 实现二
* @param n 多少个盘子
* @param a 柱子A
* @param b 柱子B
* @param c 柱子C
*/
void move1(int n, char a, char b, char c) {
if (n == 1) {
System.out.println(String.format("%s->%s",a,c));
} else {
move1(n-1, a, c, b);
System.out.println(String.format("%s->%s",a,c));
move1(n-1, b, a, c);
}
}LeetCode 第 91 题
题目
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。思路
1、dp[i]的结果与dp[i-1]和dp[i-2]有关，即在满足条件下dp[i]=dp[i-1]+dp[i-2]。
2、根据题意，有如下情况：
- s[0]='0'时，直接return 0;
- s[i]='0'时，若s[i-1]=1或者s[i-1]=2，则dp[i]=dp[i-2]，否则return 0;
- s[i-1]='1'时，则dp[i]=dp[i-1]+dp[i-2]
- s[i-1]='2'时，若'0'<s[i]<'6'，则dp[i]=dp[i-1]+dp[i-2]
Java代码
public class LeetCode91 {
public static void main(String[] args) {
String str = "11129382827";
int i = new LeetCode91().numDecodings(str);
System.out.println(i);
}
public int numDecodings(String str) {
char[] chars = str.toCharArray();
if (chars[0] == '0')
return 0;
int pre1 = 1,pre2 = 1, curr = 1;
for (int i = 1; i < chars.length; i++) {
// s[i]='0'时，若s[i-1]=1或者s[i-1]=2，则dp[i]=dp[i-2]，否则return 0;
if (chars[i] == '0') {
if (chars[i-1] == '1' || chars[i-1] == '2') {
curr = pre1;
}
else return 0;
}
// s[i-1]='1'时，则dp[i]=dp[i-1]+dp[i-2]
else if (chars[i-1] == '1') {
curr = pre1 + pre2;
}
// s[i-1]='2'时，若'0'<s[i]<'6'，则dp[i]=dp[i-1]+dp[i-2]
else if (chars[i-1] == '2' && chars[i] <= '6') {
curr = pre1 + pre2;
}
pre1 = pre2;
pre2 = curr;
}
return curr;
}
}LeetCode 第 247 题
题目
中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。
找到所有长度为 n 的中心对称数。
示例 :
输入: n = 2
输出: ["11","69","88","96"]思路
1、对称：0|0，1|1，6|9，8|8
2、不以0开头，设置一个m变量以控制0不加在最外层
Java代码
public class LeetCode247 {
public static void main(String[] args) {
List<String> strings = new LeetCode247().searchSymmetry(3,3);
System.out.println(strings);
}
public List<String> searchSymmetry(int n, int m) {
if (n == 0) {
return new ArrayList<>(Arrays.asList(""));
}
if (n == 1) {
return new ArrayList<>(Arrays.asList("0","1","8"));
}
List<String> str = searchSymmetry(n-2, m);
List<String> res = new ArrayList<>();
for(int i = 0; i < str.size(); i++){
String s = str.get(i);
// 不把0加在最外层
if (n != m) {
res.add("0" + s + "0");
}
res.add("1" + s + "1");
res.add("6" + s + "9");
res.add("8" + s + "8");
res.add("9" + s + "6");
}
return res;
}
}LeetCode 第 39 题
题目
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 ：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]思路
Java代码
public class LeetCode39 {
public static void main(String[] args) {
int[] candidates = {2,3,6,7};
int target = 7;
List<List<Integer>> lists = new LeetCode39().combinationSum(candidates, target);
for (int i = 0; i < lists.size(); i++) {
System.out.println(lists.get(i));
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
helper(candidates, target,0, new ArrayList<>(), res);
return res;
}
/**
* @param candidates 原数组
* @param target 目标大小
* @param start 开始迭代
* @param tmp 正在进行查找的集合
* @param res 接收找到的数集合
*/
private void helper(int[] candidates, int target, int start, List<Integer> tmp, List<List<Integer>> res) {
int count = 0;
for (int i = 0; i < tmp.size(); i++) {
Integer integer = tmp.get(i);
count += integer;
}
for (int i = start; i < candidates.length; i++) {
ArrayList<Integer> objects = new ArrayList<>();
objects.addAll(tmp);
objects.add(candidates[i]);
if (count + candidates[i] == target) {
res.add(objects);
} else if (count + candidates[i] < target) {
helper(candidates, target, i, objects, res);
}
}
}
}LeetCode 第 51 题（皇后问题）
题目
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。思路
Java代码
待做.....