526. 优美的排列
image.png
题目给的n的范围时1-15所以用回溯效率应该是够的，这边思路也是很简单，主要是用一个used数组来保存每个数字在深度遍历的时候是否被使用过，然后进一步如果是一个没有被使用过的，然后再通过valid函数判断他是否合法，如果也符合要求那么就加入到path中，然后最后把所有符合条件的path加入到res，返回res的长度就是答案。
package 剑指0ffer.回溯;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class 优美的排列 {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public int countArrangement(int n) {
boolean used[] = new boolean[n+1];
bacetrack(n,used);
System.out.println(res);
return res.size();
}
void bacetrack(int n,boolean[] used){
if(path.size()==n){
res.add(new ArrayList<>(path));
}
for(int i=1;i<n+1;i++){
if(used[i]){
continue;
}
if(isValid(i,path.size()+1)){
path.add(i);
used[i] = true;
bacetrack(n,used);
path.removeLast();
used[i] = false;
}
}
}
boolean isValid(int num,int index){
return num%index==0||index%num==0;
}
public static void main(String[] args) {
优美的排列 so = new 优美的排列();
System.out.println(so.countArrangement(3));
}
}
638. 大礼包
image.png
相信有些人应该和我一样看了答案一开始以为答案里面的策略是错的，但是要注意的是这题里面说了必须要严格满足个数要求，是不能多买的。所以本题的思路其实是用need来做回溯，代码如下：
class Solution {
//把这些提出来是为了回溯的参数简单
List<Integer> price = new ArrayList<>();
List<List<Integer>> special = new ArrayList<>();
Map<List<Integer>,Integer> map = new HashMap<>();
int n;
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
this.price = price;
this.special = special;
this.n = needs.size();
return bacetrack(needs);
}
int bacetrack(List<Integer> nextneed){
//加入记忆功能，用map记录某个需求的最小值
if(map.containsKey(nextneed)) return map.get(nextneed);
//先试用最贵的方法买下需要的物品
int min = 0;
for(int i=0;i<nextneed.size();i++){
min += nextneed.get(i)*price.get(i);
}
//每一层遍历所有的大礼包
for(int i=0;i<special.size();i++){
//List<Integer> needtemp = nextneed;不能这么写，这样就是引用了。
List<Integer> needtemp = new ArrayList<>(nextneed);
//记录一下这个大礼包是否可以用
boolean flag = true;
for(int j=0;j<n;j++){
//如果大礼包给的东西超过了我要的货物，就不能用
if(special.get(i).get(j)>needtemp.get(j)){
flag = false;
}
needtemp.set(j,needtemp.get(j)-special.get(i).get(j));
}
if(!flag){
continue;
}
//计算用了大礼包之后的最小值变化
min = Math.min(min,bacetrack(needtemp)+special.get(i).get(n));
}
//每次递归记录这个需求下的最小值
map.put(nextneed,min);
return min;
}
}
698. 划分为k个相等的子集
image.png
本题是很有意思的回溯题，推荐参考大佬的思路把题目好好掌握一遍。
链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solution/by-lfool-d9o7/
要注意的点首先是回溯的结束条件最好设置成index==nums.length;还有就是因为是找到一个解就可以返回，所以bacetrack的类型位boolean。
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
Arrays.sort(nums);
int l = 0;
int r= nums.length-1;
//逆序的数组计算效率是更高的
while (l<r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
int sum = 0;
for(int i:nums){
sum+=i;
}
int[] buket = new int[k];
int target = sum/k;
if(sum%k!=0){
return false;
}
return bacetrack(nums,k,buket,0,target);
}
public boolean bacetrack(int[] nums,int k,int[] bukets,int index,int target){
if(index==nums.length){
return true;
}
for(int i=0;i<k;i++){
//这是剪枝策略，如果两个篮子剩余空间是相同的，同一个index的求就不要把这两个桶都计算一次了，不符合上一个桶这次的桶也就直接跳过了。
if(i>0&&bukets[i]==bukets[i-1]){
continue;
}
if(bukets[i]+nums[index]>target){
continue;
}
bukets[i] += nums[index];
if(bacetrack(nums,k,bukets,index+1,target)) return true;
bukets[i]-=nums[index];
}
return false;
}
}
784. 字母大小写全排列
image.png
本题其实就是一个求子集的问题，然后额外需要注意的是判断并转化字母大小写的程序代码，代码总体如下：
class Solution {
List<String> res = new ArrayList<>();
public List<String> letterCasePermutation(String s) {
bacetrack(s,0);
return res;
}
void bacetrack(String s,int index){
// if(index>=s.length()-1){
// return ;
// }
res.add(s);
for(int i=index;i<s.length();i++){
if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
continue;
}else {
String s2 = isValid(s,i);
bacetrack(s2,i+1);
}
}
}
public String isValid(String s,int index){
String b = s.substring(0,index)+(Character.isLowerCase(s.charAt(index))?Character.toUpperCase(s.charAt(index)):Character.toLowerCase(s.charAt(index)))+s.substring(index+1);
return b;
}
}
将数组拆分成斐波那契序列
image.png
本题的思路是回溯，也算是回溯中比较经典的题型，自己的绘制这个dfs树的时候会发现其实每一层要做的就是划分出2，23，234，2345，23456...这样的类似字符串裁剪的序列，不是普通的2，3，4，5这样单独的一个常量。其实也没多大区别，唯一要注意的是你多些一个函数来生成从2到单独常量的序列，start记录每一层的起点元素索引，然后i就可以作为结束元素索引。可以先写出下面这样的代码，对啦这个题目是找到一个答案就返回，所以bacetrack返回值类型用boolean。
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> splitIntoFibonacci(String num) {
char[] numarr = num.toCharArray();
bacetrack(numarr,0);
return res;
}
boolean bacetrack(char[] num,int start){
if(start>=num.length&&res.size()>=3){
return true;
}
for(int i=start;i<num.length;i++){
if (num[start] == '0' && i > start) {
break;
}
long sub = isValid(num,start,i+1);
if (sub > Integer.MAX_VALUE) {
break;
}
int size = res.size();
//如果截取的数字大于res中前两个数字的和，说明这次截取的太大，直接终止，因为后面越截取越大
if (size >= 2 && sub > res.get(size - 1) + res.get(size - 2)) {
break;
}
if(res.size()<=1||res.get(res.size()-1)+res.get(res.size()-2)==sub){
res.add((int)sub);
if(bacetrack(num,i+1))
return true;
res.remove(res.size()-1);
}
}
return false;
}
long isValid(char[]num,int start,int end){
long res = 0;
for (int i = start; i < end; i++) {
res = res * 10 + num[i] - '0';
}
return res;
}
}
1079. 活字印刷
image.png
class Solution {
LinkedList<Character> path = new LinkedList<>();
int res = 0;
public int numTilePossibilities(String tiles) {
char[] arr = tiles.toCharArray();
boolean[] used = new boolean[arr.length];
Arrays.sort(arr);
bacetrack(arr,used);
return res;
}
void bacetrack(char[] arr,boolean[] used){
if(!path.isEmpty()){
res++;
}
for(int i=0;i<arr.length;i++){
//同一个位置元素用过不能再用
if(used[i] == true){
continue;
}
//同一层遍历到想同值的元素用过不能再用
if(i>0&&arr[i-1]==arr[i]&&used[i-1]==false){
continue;
}
used[i] =true;
path.add(arr[i]);
bacetrack(arr,used);
path.removeLast();
used[i] = false;
}
}
}
1219. 黄金矿工
image.png
本题有点像n宫格的岛屿题目，dfs的时候返回值类型定义为int，然后手动写一个方向数组，每次遍历的时候把遍历过的点变成0就不需要额外建立一个visit数组（也可以用）。
class Solution {
int res = 0;
int[][] nums;
final int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
public int getMaximumGold(int[][] grid) {
nums = grid;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
res = Math.max(res,dfs(i,j));
}
}
return res;
}
int dfs(int i,int j){
if(!isInarea(i,j)||nums[i][j]==0){
return 0;
}
int cur = nums[i][j];
int max = 0;
nums[i][j] = 0;
for(int [] d:dirs){
max = Math.max(max,dfs(i+d[0],j+d[1]));
}
nums[i][j] = cur;
return cur+max;
}
boolean isInarea(int i,int j){
return (i>=0&&i<nums.length)&&(j>=0&&j<nums[0].length);
}
}
2375. 根据模式串构造最小数字
image.png
本题用拓扑排序的思路会更好，但是是一道很不错的dfs题目，因为本题要根据当前的字母是i考虑下一个层的范围，也就是下一层的范围不只是简单的i++或者从0开始。所以首先遍历1到9，模拟以1到9开头的每种情况。然后开始回溯，回溯的时候判断当前字母是不是I，如果是I，则i从pre+1继续，然后结束就是10，但是如果当前字母是D，则i从1开始，结束则是pre。
class Solution {
private String ans = "";
private boolean[] vis;
public void dfs(int index, int pre, StringBuilder sb, char[] pattern){
if (index == pattern.length){
// 比较结果取较小值
if (ans == "" || ans.compareTo(sb.toString()) > 0) ans = sb.toString();
return;
}
// 根据pattern的值控制枚举范围，'I':(pre, 9], 'D':[1, pre)
for (int i = (pattern[index] == 'I' ? pre + 1 : 1); i < (pattern[index] == 'I' ? 10 : pre); ++i){
if (!vis[i]){
sb.append(i);
vis[i] = true;
dfs(index + 1, i, sb, pattern);
vis[i] = false;
sb.deleteCharAt(sb.length() - 1);
}
}
}
public String smallestNumber(String pattern) {
vis = new boolean[10];
// 枚举第一个数字
for (int i = 1; i <= 9; ++i){
vis[i] = true;
dfs(0, i, new StringBuilder(String.valueOf(i)), pattern.toCharArray());
vis[i] = false;
}
return ans;
}
}
698. 划分为k个相等的子集
image.png
本题回溯的思路就不是一般的情况，一般下每层都是把nums里面的元素，现在则是根据k来确定桶的数量，然后每层是遍历桶的数量放入元素。
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
Arrays.sort(nums);
int l = 0;
int r= nums.length-1;
while (l<r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
int sum = 0;
for(int i:nums){
sum+=i;
}
int[] buket = new int[k];
int target = sum/k;
if(sum%k!=0){
return false;
}
return bacetrack(nums,k,buket,0,target);
}
public boolean bacetrack(int[] nums,int k,int[] bukets,int index,int target){
if(index==nums.length){
return true;
}
for(int i=0;i<k;i++){
if(i>0&&bukets[i]==bukets[i-1]){
continue;
}
if(bukets[i]+nums[index]>target){
continue;
}
bukets[i] += nums[index];
if(bacetrack(nums,k,bukets,index+1,target)) return true;
bukets[i]-=nums[index];
}
return false;
}
}
2305. 公平分发饼干](https://leetcode.cn/problems/fair-distribution-of-cookies/)
image.png
本题虽然不是dfs最优解，但是考验了剪枝的想法。大家都可以尝试一下！！！
class Solution {
int ans = Integer.MAX_VALUE;
int[] cookies;
int n;
int k;
public int distributeCookies(int[] cookies, int k) {
//技巧：先发饼干较多的包，这样让回溯过程更快。下面的回溯代码是从最后一个饼干包开始发所以这里是从小到大排序
Arrays.sort(cookies);
this.cookies = cookies;
n = cookies.length;
this.k = k;
//启动回溯
backtrack(new int[k], n-1);
return ans;
}
//bucket数组存放k个小朋友每个人当前的饼干数量，start为下一个要分发的饼干包下标
public void backtrack(int[] bucket, int start){
//饼干发完了，统计哪个小朋友获得的饼干最多，更新答案。
if (start < 0){
int curAns = Integer.MIN_VALUE;
for (int count : bucket){
curAns = Math.max(curAns, count);
}
ans = Math.min(ans, curAns);
return;
}
//剪枝1：如果剩余的饼干包不够空手的小朋友分了，直接返回。
int zeroCount = 0;
for (int count : bucket){
if (count == 0) zeroCount++;
}
if (zeroCount > start + 1) return;
//剪枝2：如果某位小朋友的饼干数量比当前的答案还多，显然继续回溯下去也无法成为最优答案，直接返回。
for (int i = 0; i < k; i++){
if (bucket[i] > ans) return;
}
for (int i = 0; i < k; i++){
//剪枝3：第一个零食包不管给哪个小朋友，所开启的回溯树都一样，只要给一个小朋友就行了，这样的回溯树一下子就少了很多。
if (start == n - 1 && i > 0) return;
//标准回溯代码
bucket[i] += cookies[start];
backtrack(bucket, start - 1);
bucket[i] -= cookies[start];
}
return;
}
}
2002. 两个回文子序列长度的最大乘积
image.png
本题可能一看不会想回溯，不过确实看到了一个大神的思路，所有字母有三个选择，加入第一个子序列，加入第二个子序列，或者都不加入任何序列。
class Solution {
int ans = 0;
public int maxProduct(String s) {
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
dfs(s, sb1, sb2, 0);
return ans;
}
public void dfs(String s, StringBuilder sb1, StringBuilder sb2, int index) {
if(check(sb1) && check(sb2)) {
ans = Math.max(ans, sb1.length() * sb2.length());
}
if(index == s.length()) return;
dfs(s, sb1.append(s.charAt(index)), sb2, index + 1); // 子序列s1 使用
sb1.setLength(sb1.length() - 1);
dfs(s, sb1, sb2.append(s.charAt(index)), index + 1); // 子序列 s2 使用
sb2.setLength(sb2.length() - 1);
dfs(s, sb1, sb2, index + 1); // 子序列 sb1 和 sb2 者均不使用
}
public boolean check(StringBuilder sb1) { // 检查是否为回文字符串
int left = 0, right = sb1.length() - 1;
while(left < right) {
if(sb1.charAt(left) == sb1.charAt(right)) {
left++;
right--;
} else {
return false;
}
}
return true;
}
}
