526. 優(yōu)美的排列

image.png

題目給的n的范圍時(shí)1-15所以用回溯效率應(yīng)該是夠的，這邊思路也是很簡(jiǎn)單，主要是用一個(gè)used數(shù)組來(lái)保存每個(gè)數(shù)字在深度遍歷的時(shí)候是否被使用過(guò)，然后進(jìn)一步如果是一個(gè)沒(méi)有被使用過(guò)的，然后再通過(guò)valid函數(shù)判斷他是否合法，如果也符合要求那么就加入到path中，然后最后把所有符合條件的path加入到res，返回res的長(zhǎng)度就是答案。

package 劍指0ffer.回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 優(yōu)美的排列 {
    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) {
        優(yōu)美的排列 so = new 優(yōu)美的排列();
        System.out.println(so.countArrangement(3));
    }

}

638. 大禮包

image.png

相信有些人應(yīng)該和我一樣看了答案一開(kāi)始以為答案里面的策略是錯(cuò)的，但是要注意的是這題里面說(shuō)了必須要嚴(yán)格滿足個(gè)數(shù)要求，是不能多買(mǎi)的。所以本題的思路其實(shí)是用need來(lái)做回溯，代碼如下：

class Solution {
    //把這些提出來(lái)是為了回溯的參數(shù)簡(jiǎn)單
    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記錄某個(gè)需求的最小值
        if(map.containsKey(nextneed)) return map.get(nextneed);
        //先試用最貴的方法買(mǎi)下需要的物品
        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;不能這么寫(xiě)，這樣就是引用了。
            List<Integer> needtemp = new ArrayList<>(nextneed);
            //記錄一下這個(gè)大禮包是否可以用
            boolean flag = true;
            for(int j=0;j<n;j++){
                //如果大禮包給的東西超過(guò)了我要的貨物，就不能用
                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;
            }
           //計(jì)算用了大禮包之后的最小值變化
            min = Math.min(min,bacetrack(needtemp)+special.get(i).get(n));
        }
        //每次遞歸記錄這個(gè)需求下的最小值
        map.put(nextneed,min);
        return min;
    }
}

698. 劃分為k個(gè)相等的子集

image.png

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0;
        int r= nums.length-1;
        //逆序的數(shù)組計(jì)算效率是更高的
        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++){
            //這是剪枝策略，如果兩個(gè)籃子剩余空間是相同的，同一個(gè)index的求就不要把這兩個(gè)桶都計(jì)算一次了，不符合上一個(gè)桶這次的桶也就直接跳過(guò)了。
            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. 字母大小寫(xiě)全排列

image.png

本題其實(shí)就是一個(gè)求子集的問(wèn)題，然后額外需要注意的是判斷并轉(zhuǎn)化字母大小寫(xiě)的程序代碼，代碼總體如下：

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

將數(shù)組拆分成斐波那契序列

image.png

本題的思路是回溯，也算是回溯中比較經(jīng)典的題型，自己的繪制這個(gè)dfs樹(shù)的時(shí)候會(huì)發(fā)現(xiàn)其實(shí)每一層要做的就是劃分出2，23，234，2345，23456...這樣的類(lèi)似字符串裁剪的序列，不是普通的2，3，4，5這樣單獨(dú)的一個(gè)常量。其實(shí)也沒(méi)多大區(qū)別，唯一要注意的是你多些一個(gè)函數(shù)來(lái)生成從2到單獨(dú)常量的序列，start記錄每一層的起點(diǎn)元素索引，然后i就可以作為結(jié)束元素索引。可以先寫(xiě)出下面這樣的代碼，對(duì)啦這個(gè)題目是找到一個(gè)答案就返回，所以bacetrack返回值類(lèi)型用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();
            //如果截取的數(shù)字大于res中前兩個(gè)數(shù)字的和，說(shuō)明這次截取的太大，直接終止，因?yàn)楹竺嬖浇厝≡酱?            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++){
            //同一個(gè)位置元素用過(guò)不能再用
            if(used[i] == true){
                continue;
            }
            //同一層遍歷到想同值的元素用過(guò)不能再用
            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

本題有點(diǎn)像n宮格的島嶼題目，dfs的時(shí)候返回值類(lèi)型定義為int，然后手動(dòng)寫(xiě)一個(gè)方向數(shù)組，每次遍歷的時(shí)候把遍歷過(guò)的點(diǎn)變成0就不需要額外建立一個(gè)visit數(shù)組（也可以用）。

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. 根據(jù)模式串構(gòu)造最小數(shù)字

image.png

本題用拓?fù)渑判虻乃悸窌?huì)更好，但是是一道很不錯(cuò)的dfs題目，因?yàn)楸绢}要根據(jù)當(dāng)前的字母是i考慮下一個(gè)層的范圍，也就是下一層的范圍不只是簡(jiǎn)單的i++或者從0開(kāi)始。所以首先遍歷1到9，模擬以1到9開(kāi)頭的每種情況。然后開(kāi)始回溯，回溯的時(shí)候判斷當(dāng)前字母是不是I，如果是I，則i從pre+1繼續(xù)，然后結(jié)束就是10，但是如果當(dāng)前字母是D，則i從1開(kāi)始，結(jié)束則是pre。

class Solution {
     private String ans = "";
        private boolean[] vis;
        public void dfs(int index, int pre, StringBuilder sb, char[] pattern){
            if (index == pattern.length){
                // 比較結(jié)果取較小值
                if (ans == "" || ans.compareTo(sb.toString()) > 0) ans = sb.toString();
                return;
            }

            // 根據(jù)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];
            // 枚舉第一個(gè)數(shù)字
            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個(gè)相等的子集

image.png

本題回溯的思路就不是一般的情況，一般下每層都是把nums里面的元素，現(xiàn)在則是根據(jù)k來(lái)確定桶的數(shù)量，然后每層是遍歷桶的數(shù)量放入元素。

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. 公平分發(fā)餅干](https://leetcode.cn/problems/fair-distribution-of-cookies/)

image.png

本題雖然不是dfs最優(yōu)解，但是考驗(yàn)了剪枝的想法。大家都可以嘗試一下?。?！

class Solution {
    
    int ans = Integer.MAX_VALUE;
    int[] cookies;
    int n;
    int k;
    
    public int distributeCookies(int[] cookies, int k) {
        
        //技巧：先發(fā)餅干較多的包，這樣讓回溯過(guò)程更快。下面的回溯代碼是從最后一個(gè)餅干包開(kāi)始發(fā)所以這里是從小到大排序
        Arrays.sort(cookies);
        
        this.cookies = cookies;
        n = cookies.length;
        this.k = k;
        
        //啟動(dòng)回溯
        backtrack(new int[k], n-1);
        
        return ans;
    }
    
    //bucket數(shù)組存放k個(gè)小朋友每個(gè)人當(dāng)前的餅干數(shù)量，start為下一個(gè)要分發(fā)的餅干包下標(biāo)
    public void backtrack(int[] bucket, int start){
        
        //餅干發(fā)完了，統(tǒng)計(jì)哪個(gè)小朋友獲得的餅干最多，更新答案。
        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：如果某位小朋友的餅干數(shù)量比當(dāng)前的答案還多，顯然繼續(xù)回溯下去也無(wú)法成為最優(yōu)答案，直接返回。
        for (int i = 0; i < k; i++){
            if (bucket[i] > ans) return;
        }
        
        for (int i = 0; i < k; i++){
            //剪枝3：第一個(gè)零食包不管給哪個(gè)小朋友，所開(kāi)啟的回溯樹(shù)都一樣，只要給一個(gè)小朋友就行了，這樣的回溯樹(shù)一下子就少了很多。
            if (start == n - 1 && i > 0) return;
            
            //標(biāo)準(zhǔn)回溯代碼
            bucket[i] += cookies[start];
            backtrack(bucket, start - 1);
            bucket[i] -= cookies[start];
        }
        return;
    }
}

2002. 兩個(gè)回文子序列長(zhǎng)度的最大乘積

image.png

本題可能一看不會(huì)想回溯，不過(guò)確實(shí)看到了一個(gè)大神的思路，所有字母有三個(gè)選擇，加入第一個(gè)子序列，加入第二個(gè)子序列，或者都不加入任何序列。

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