前言

• 擁有最多糖果的孩子
• 改變一個(gè)整數(shù)能得到的最大差值
• 檢查一個(gè)字符串是否可以打破另一個(gè)字符串
• 每個(gè)人戴不同帽子的方案數(shù)

擁有最多糖果的孩子

• 題目鏈接
• 解釋?zhuān)杭匆笈袛嗝總€(gè)孩子目前所擁有的糖果數(shù)量加上extraCandies是否大于等于孩子們所擁有糖果數(shù)目的最大值

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int maxValue = 0;
        for (int candy : candies)
            maxValue = Math.max(maxValue, candy);
        
        List<Boolean> ans = new ArrayList<>();
        for (int e : candies) {
            ans.add((e+extraCandies) >= maxValue);
        }
        return ans;
    }
}

• 復(fù)雜度分析
  時(shí)間復(fù)雜度：
  空間復(fù)雜度： 不包括結(jié)果數(shù)組

改變一個(gè)整數(shù)能得到的最大差值

• 題目鏈接
• 分析：即要求我們分別找到將原數(shù)中某一位全部替換成另外一個(gè)數(shù)字后的最大值和最小值，求其差。要求是替換后不能有前導(dǎo)0以及為0。貪心算法。

求最大值的方法：

從左到右，找到第一位小于9的數(shù)字，將所有該數(shù)字替換為9，即為最大值

求最小值的方法：

為了沒(méi)有前導(dǎo)0和本身為0，需要分類(lèi)討論

1. 若原數(shù)中首位數(shù)字大于1,則將原數(shù)中所有該數(shù)字替換為1，即得最小值 。
2. 否則，從左到右找到第一個(gè)大于等于2的數(shù)字，將其全部替換為0，即得最小值

• 代碼

class Solution {
   public int maxDiff(int num) {
       return getMax(num)-getMin(num);
   }
   // 從左到右找到第一個(gè)不為`9`的數(shù)字，把他們替換成`9`
   private int getMax(int num) {
       char[] cs = String.valueOf(num).toCharArray();
       char ori = '9';
       for (char c : cs) {
           if (c != '9') {
               ori = c;
               break;
           }
       }
       return replace(cs, ori, '9');
   }
   // 1. 如果首位是>`1`，則把所有首位數(shù)字替換成`1`
   // 2. 否則找一個(gè)最靠左，且不是首位并且大等于于`2`的數(shù)字，將所有該數(shù)字替換成`0`
   private int getMin(int num) {
       char[] cs = String.valueOf(num).toCharArray();
       if (cs[0] > '1') return replace(cs, cs[0], '1');
       
       char ori = '2';
       for (int i = 1; i < cs.length; i++) {
           if (cs[i] >= ori) {
               ori = cs[i];
               break;
           }
       }
       return replace(cs, ori, '0');
   }
   private int replace(char[] cs, char ori, char dst) {
       
       for (int i = 0; i < cs.length; i++) {
           if (cs[i] == ori) cs[i] = dst;
       }
       return Integer.parseInt(new String(cs));
   }
}

• 復(fù)雜度分析：
  時(shí)間復(fù)雜度： len(num)為num的位數(shù)
  空間復(fù)雜度: len(num)為num的位數(shù)

檢查一個(gè)字符串是否可以打破另一個(gè)字符串

• 題目鏈接

• 分析：要求我們找出字符串s1和s2中的一個(gè)排列，使得所有對(duì)應(yīng)位置上的字符，總有s1[i] <= s2[i]或 所有對(duì)應(yīng)位置上的字符,總有s1[i] >= s2[i]。使用貪心算法，將2個(gè)字符串中的字符均由小到大排列，判斷是否滿足條件即可。

• 代碼

class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        char[] ss1 = s1.toCharArray();
        char[] ss2 = s2.toCharArray();
        Arrays.sort(ss1);
        Arrays.sort(ss2);
        return can(ss1, ss2) || can(ss2, ss1);
    }
    private boolean can(char[] ss1, char[] ss2) {
        int n = ss1.length;
        for (int i = 0; i < n; i++) {
            if (ss1[i] >= ss2[i]) continue;
            else return false;
        }
        return true;
    }
}

• 復(fù)雜度分析：
  時(shí)間復(fù)雜度： 為字符串長(zhǎng)度，開(kāi)銷(xiāo)來(lái)自于排序算法
  空間復(fù)雜度：

每個(gè)人戴不同帽子的方案數(shù)

• 題目鏈接
• 分析： 一共有40種不同的帽子和n個(gè)人，每個(gè)人有自己喜歡的帽子，求每個(gè)人都帶到自己喜歡的帽子且n個(gè)人帽子都不相同的方案數(shù)

記憶化搜索&狀態(tài)壓縮：

因?yàn)楣灿?code>40種帽子，以及n<=10個(gè)人，因此可想到壓縮成一個(gè)Long型的值，其中40位表示這40種帽子哪些被人戴過(guò)了，還有1位表示當(dāng)前給第幾個(gè)人分配帽子，我們把該狀態(tài)存進(jìn)一個(gè)Map對(duì)象里，防止重復(fù)計(jì)算。不幸的是，因?yàn)?code>40種帽子，則有種不同的狀態(tài)，會(huì)引起超市

• 超時(shí)的解法

class Solution {
    private int mod = 1_000_000_000 + 7;
    private List<List<Integer>> hats;
    private Map<Long, Integer> mem;
    public int numberWays(List<List<Integer>> hats) {
        this.hats = hats;
        this.mem = new HashMap<>();
        int n = hats.size();
        
        return helper(0, n);
    }
    private int helper(long cur, long n) {
        long i = cur % 10;
        long k = cur / 10;
        if (i == n) return 1;
        if (mem.containsKey(cur)) return mem.get(cur);
        
        List<Integer> cand = hats.get((int)i);
        int ans = 0;
        for (int e : cand) {
            if ((k&(1<<e))==0) {
                long tmp = (k|(1<<e))*10+(i+1);
                ans += helper(tmp, n);
                ans %= mod;
            }
        }
        mem.put(cur, ans);
        return ans;
    }
}

• 時(shí)間復(fù)雜度

改進(jìn)

考慮到帽子有40種，但是人n最多只有10個(gè)，因此我們可以將問(wèn)題轉(zhuǎn)化為，將每種帽子，選擇一個(gè)人來(lái)占有它，直到n個(gè)人都有帽子為止，此時(shí)最多只有種狀態(tài)，我們同樣采用狀態(tài)壓縮的方式，當(dāng)n個(gè)人都有帽子時(shí)停止搜索，注意每個(gè)帽子我們可以選擇分配或不分配(即n個(gè)人中沒(méi)有一個(gè)人戴此帽)

• 優(yōu)化的解法

class Solution {
    private int mod = 1_000_000_000 + 7;
    private int target;
    private List<List<Integer>> people;
    private Map<Integer, Integer> mem;
    public int numberWays(List<List<Integer>> hats) {
        this.mem = new HashMap<>();
        this.people = new ArrayList<>();
        for (int i = 0; i <= 40; i++)
            people.add(new ArrayList<>());
        
        int n = hats.size();
        this.target = (1<<n)-1;
        for (int i = 0; i < n; i++) {
            List<Integer> hat = hats.get(i);
            for (int e : hat) {
                people.get(e).add(i);
            }
        }
        
        return helper(1);
    }
    private int helper(int cur) {
        
        int i = cur % 100;
        int k = cur / 100;
        
        
        if (k == target) return 1;
        if (i == 41) return 0;
        if (mem.containsKey(cur)) return mem.get(cur);
        int ans = helper(cur+1);
        List<Integer> p = people.get(i);
        for (int e : p) {
            if ((k&(1<<e))==0) {
                int t = (k|(1<<e))*100+(i+1);
                ans += helper(t);
                ans %= mod;
            }
        }
        mem.put(cur, ans);
        return ans;
                
    }
}

• 復(fù)雜度分析
  時(shí)間復(fù)雜度：
  空間復(fù)雜度：