1、求3位数，每位数字可以取1-3的所有可能
百位上的数字可以分别求1，2，3，然后问题就变成：求2位数，每位数字可以取1-3的所有可能，所以可以用递归。
从百位上的数字开始遍历（1-3），然后递归求解下一位 fun(n-1,x)
x 为高位数字的和，在每层运算时，加上本位数字产生的和，第三位为∗102，第二位为 ∗101，依次类推
递归退出条件为 n==0
public class Main {
public static void main(String[] args) {
fun(3, 0);
}
private static void fun(int n, int x) {
if (n == 0) {
System.out.println(x);
return;
}
for (int i = 1; i <= 3; i++) {
fun(n - 1, (int)(Math.pow(10, n - 1) * i) + x);
}
}
}
111
112
...
331
332
333
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
题解：
组合问题一般用递归。
每一位数组循环选 1 … n，传递本次递归的 list ，和下一位的数。注意递归出口后，要移除最后一个元素（即本循环位上的元素），以便下次循环，替换成下一个。
刚开始用了一个List 保存之前添加过的元素，防止后面重复，结果提交超时。
注意到 下一个数字只能从比他大的数字开始增加，即可避免后面出现重复，
将 fun(start + 1, list); 改为 fun(i + 1, list); 即通过。
注意本题不用使用 Set<Set<Integer>> ,注意观察理解本质，即可避免后面重复。
class Solution {
List<List<Integer>> resultList = new ArrayList<List<Integer>>();
int kk;
int nn;
public List<List<Integer>> combine(int n, int k) {
if(k <= 0 || n <= 0) return new ArrayList<>();//一定要先判断特殊输入，大大减轻耗时
kk = k;
nn = n;
fun(1, new ArrayList<Integer>());
return resultList;
}
public void fun(int start, List<Integer> list) {
if (list.size() == kk) {
resultList.add(new ArrayList(list));//这里一定要在new 一个放进去，不然后面list改变，resultList 里的结果也会变
return;
}
for (int i = start; i <= nn; i++) {
list.add(i);
fun(i + 1, list);// 下一个数字只能从比他大的数字开始增加
list.remove(list.size() - 1);// 递归出来后，要移除最后一个元素，以便下次循环，添加下一个
}
}
}
给出一个候选数字的 set(C) 和 目标数字(T), 找到 C 中所有的组合，使找出的数字和为T。C中的数字可以无限制重复被选取。
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题解：
组合问题一般用递归。
递归遍历选择候选数组的每位数字，为了防止候选数组重复，导致结果有重复，先将候选数字排序，后面递归时判断是否等于前一位数字；
由于每位数字可以重复使用，所以递归传递的下次位置还是 当前位置 i 。
class Solution {
List<List<Integer>> resultList = new ArrayList<List<Integer>>();
int[] candidates;
public List<List<Integer>> combinationSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return resultList;
}
candidates = nums;// 赋给类变量，方便后面调用
Arrays.sort(candidates);// 从小到大排序
fun(0, target, new ArrayList<>());
return resultList;
}
// index为候选数组中开始选择相加的位置，target为要求的和，record为一条结果
public void fun(int index, int target, List<Integer> record) {
if(target<0){ //递归退出条件
return;
}
if(target==0){//表示该组合成功
resultList.add(new ArrayList<>(record));
return;
}
for(int i=index;i<candidates.length;i++){
if(i!=0 && candidates[i]==candidates[i-1]){//跳过有重复的项
continue;
}
if(candidates[i] > target){//相减的话，target一定是负数了，直接退出
return;
}
record.add(candidates[i]);
fun(i,target-candidates[i],record);//从此项递归
record.remove(record.size() - 1); //注意移除这一个，以便下次循环，添加下一个
}
}
}
n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击（不能在同一行、同一列、同一对角线）。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
Example:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
题解：
设一个数组a用来存放每一行皇后的位置，元素值表示第几列（如a[1]=5表示第一行的皇后处于第五个格）。然后只需要求出数组a的值 问题就解决了。
从第一行的皇后一直深入去找第二行、第三行…皇后的位置。深度优先搜索，遇到不满足的情况就进行回溯。一般而言，深度优先搜索都是可以用递归来实现的。每一层递归表示一行皇后，j表示列，即a[i]=j表示第i行的皇后位置在第j列。
check(int n) 函数解析
某一行的皇后a[n]不能和之前的皇后a[i]位置有冲突，约束条件为：
a、不在同一列：a[n] != a[i]
b、不在同一行：因为现在是每一行求一个皇后的位置，所以同一行不会有冲突，不需要考虑。
c、不在同一对左角线：a[n]-a[i] != n-i
d、不在同一右对角线：a[n]-a[i] != -(n-i)
条件c和d可以合成：abs(a[n]-a[i]) != abs(n-i)
class Solution {
List<List<String>> result=new ArrayList<List<String>>();
int n;// n皇后问题
int[] a=new int[256];//记录每行皇后位置，a[i]=j表示第i行的皇后位置在第j列
public List<List<String>> solveNQueens(int nn) {
if(nn<1||nn==2||nn==3) return new ArrayList<>();
n=nn;
fun(1);//从第1行开始搜索
return result;
}
private void fun(int i) {
for(int j=1;j<=n;j++){
a[i]=j;//遍历，第i行的皇后在第j个位置上
if(check(i)){//如果第j列不会与之前的皇后冲突
if(i<n){//还读到n个皇后，继续递归
fun(i+1);
}else{//找到了一组解
List<String> oneAnswer=new ArrayList<>();
for(int k=1;k<=n;k++){
StringBuilder sb=new StringBuilder();
for(int m=1;m<=n;m++){
if(m==a[k]){
sb.append("Q");
}else{
sb.append(".");
}
}
oneAnswer.add(sb.toString());
}
result.add(oneAnswer);
}
}
}
}
private boolean check(int n) {//检验第n行的皇后是否和之前的皇后有冲突，没有的话返回true
for(int i=1;i<n;i++){
if(a[i]==a[n]||Math.abs(a[i]-a[n])==Math.abs(i-n)){
return false;
}
}
return true;
}
}
跟上个方法本质一样，只是用List<Integer> rows 存储每行皇后的位置，而不是用数组，仍然是从第一行开始变量每个位置然后深度优先搜索。
class Solution {
List<List<String>> result = new ArrayList<List<String>>();//返回的结果列表
int n;// n皇后问题
public List<List<String>> solveNQueens(int nn) {
if (nn < 1 || nn == 2 || nn == 3)
return new ArrayList<>();
n = nn;
fun(new ArrayList<Integer>());// 从第1行开始搜索
return result;
}
private void fun(List<Integer> rows) {// 存储每行皇后的位置，即列号，从0开始
if (rows.size() == n) {// 递归退出条件，深度到了n行了
result.add(drawChessboard(rows));
return;
}
for (int i = 0; i < n; i++) {
if (!isValid(rows, i)) {// 如果该行皇后位置为 i ,检测是否和之前的皇后冲突，如果冲突则跳过
continue;
}
rows.add(i);
fun(rows);
rows.remove(rows.size() - 1);
}
}
private List<String> drawChessboard(List<Integer> rows) {// 根据每行皇后的位置画出棋盘
List<String> chessboard = new ArrayList<>();
for (int i = 0; i < rows.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < rows.size(); j++) {
sb.append(j == rows.get(i) ? 'Q' : '.');
}
chessboard.add(sb.toString());
}
return chessboard;
}
private boolean isValid(List<Integer> rows, int column) {// 检验rows第column行的皇后是否和之前的皇后有冲突，没有的话返回true
for (int i = 0; i < rows.size(); i++) {
if (rows.get(i) == column || Math.abs(rows.get(i) - column) == Math.abs(rows.size() - i)) {
return false;
}
}
return true;
}
}
5、LeetCode 17. Letter Combinations of a Phone Number
给出一个字符串，包含数组 2-9，返回所有可能的字符组合。
数组和字符的映射如下图所示：
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
以上的答案是按照词典编撰顺序进行输出的，不过，在做本题时，你也可以任意选择你喜欢的输出顺序。
题解：
依然是老套路，遍历循环、递归。
class Solution {
String[] numStrs={"abc","def","ghi","jkl","nmo","pqrs","tuv","wxyz"};
int n;//按键个数，即字母个数
int[] digitsNum;//记录数字
List<String> result=new ArrayList<String>();//结果
public List<String> letterCombinations(String digits) {
if(digits==null||digits.length()==0){
return result;
}
n=digits.length();
String[] digitsStr=digits.split("");//分成单个数字字符串
digitsNum=new int[n];//记录数字
for(int i=0;i<n;i++){
digitsNum[i]=Integer.parseInt(digitsStr[i])-2;//将按键数字转换为对应字符数组的下标
}
fun(0,"");//从digitsNum[]的0位置开始，即从第一个按键开始
return result;
}
private void fun(int num,String resultStr) {
if(resultStr.length()==n){
result.add(resultStr);
return;
}
String str=numStrs[digitsNum[num]];
for(int i=0;i<str.length();i++){
fun(num+1,resultStr+str.charAt(i));
}
}
}
编写一个程序，通过填充空单元来解决数独难题。
空单元由数字'.'表示。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 一个数独。
 答案被标成红色。
Note:
给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
题解：
给出的结题的函数，居然没有返回值，不用担心这个，OJ应该会根据你最后borad[][] 的值判断正误。
采用递归+回溯模板
判定DFS的退出条件。
(1) y越界，应该往下一行继续解。
(2) x越界，代表数独解完，应该返回。 DFS的主体部分：
把9个可能的值遍历一次，如果是OK的（使用独立 的Valid函数来判定行，列，BLOCK是否符合），继续DFS，否则回溯。 最后的返回值：
如果所有的可能性遍历都没有找到TRUE，最后应该返回FALSE，也就是当前情况无解。这个时候DFS会自动回溯到上一层再查找别的可能解。
DFS就是针对本轮的所有可能解进行逐一尝试，找到本轮的一个可能解后，这时要调用递归，基于本轮的解对下一轮（子问题）进行求解。如果下一轮（子问题）求解成功，则说明大功告成，及时返回true，停止之后的尝试。
否则如果下一轮（子问题）求解失败，则说明本轮的解不适合子问题，因此，必须换一个本轮的解，然后基于本轮的新解，继续尝试子问题。如果已经本轮所有的解都尝试过了，也都失败了，说明本问题无解，返回false。
当然在每次尝试子问题前和如果失败返回后，都要恢复原来的环境（撤销动作）。
所以，要想使DFS成功返回，条件就是找到满足本轮的解和这个解也要满足下一轮（子问题）。
为什么前面的递归都不用返回值，而此处的要返回boolean 类型 呢，个人理解：因为此处每个位置搜索不是按需的，有的位置是数字就要跳过， 所以回溯的时候不好回溯到上一个位置，所以需要按每轮是否符合条件判断。
class Solution {
public void solveSudoku(char[][] board) {
fun(board, 0, 0);
}
private boolean fun(char[][] board, int x, int y) {
if (x > 8) {// 深搜完成
return true;
}
if (y > 8) {// 要换行了
return fun(board, x + 1, 0);
}
if (board[x][y] == '.') {// 如果该位置上是'.'，说明可以填数
for (int i = 1; i <= 9; i++) {
board[x][y] = (char) (i + '0');
if (isValid(board, x, y)) {// 该位置填这个数，如果是有效的
if (fun(board, x, y + 1)) {//注意：在此一定要接收递归返回值，因为在有返回值的递归函数中，最后一层的return 只会返回到上一层，不会直接整体退出
return true;
}
}
board[x][y] = '.';
}
return false;
} else {
return fun(board, x, y + 1);
}
}
private boolean isValid(char[][] board, int x, int y) {
for (int i = 0; i < 9; i++) {
if (i != x && board[i][y] == board[x][y]) {// 这一列有与它重复的
return false;
}
if (i != y && board[x][i] == board[x][y]) {// 这一行有与它重复的
return false;
}
}
for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++) {//判断3x3 宫是否重复
for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++) {
if ((i != x || j != y) && board[i][j] == board[x][y]) {
return false;
}
}
}
return true;
}
}
|
