第25場雙周賽

前言

擁有最多糖果的孩子 ${\color{green}{\text{[簡單]}}}$
改變一個整數(shù)能得到的最大差值 ${\color{orange}{\text{[中等]}}}$
檢查一個字符串是否可以打破另一個字符串 ${\color{orange}{\text{[中等]}}}$
每個人戴不同帽子的方案數(shù) ${\color{red}{\text{[困難]}}}$

擁有最多糖果的孩子

題目鏈接
解釋：即要求判斷每個孩子目前所擁有的糖果數(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ù)雜度分析
時間復(fù)雜度： $O(N)$
空間復(fù)雜度： $O(1)$ 不包括結(jié)果數(shù)組

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

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

求最大值的方法：

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

求最小值的方法：

為了沒有前導(dǎo)0和本身為0湖员，需要分類討論

若原數(shù)中首位數(shù)字大于1,則將原數(shù)中所有該數(shù)字替換為1，即得最小值嘴高。

否則竿音，從左到右找到第一個大于等于2的數(shù)字和屎，將其全部替換為0，即得最小值

代碼

class Solution {
   public int maxDiff(int num) {
       return getMax(num)-getMin(num);
   }
   // 從左到右找到第一個不為`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. 否則找一個最靠左，且不是首位并且大等于于`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ù)雜度分析：
時間復(fù)雜度： $O(len(num))$ len(num)為num的位數(shù)
空間復(fù)雜度: $O(len(num))$ len(num)為num的位數(shù)

檢查一個字符串是否可以打破另一個字符串

題目鏈接
分析：要求我們找出字符串s1和s2中的一個排列颠印，使得所有對應(yīng)位置上的字符，總有s1[i] <= s2[i]或所有對應(yīng)位置上的字符,總有s1[i] >= s2[i]抹竹。使用貪心算法线罕，將2個字符串中的字符均由小到大排列，判斷是否滿足條件即可窃判。
代碼

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ù)雜度分析：
時間復(fù)雜度： $O(NlogN)$ $N$ 為字符串長度钞楼，開銷來自于排序算法
空間復(fù)雜度： $O(N)$

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

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

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

因為共有40種帽子询件，以及n<=10個人，因此可想到壓縮成一個Long型的值唆樊，其中40位表示這40種帽子哪些被人戴過了宛琅，還有1位表示當(dāng)前給第幾個人分配帽子，我們把該狀態(tài)存進(jìn)一個Map對象里逗旁，防止重復(fù)計算嘿辟。不幸的是，因為40種帽子片效，則有 $2^{40}$ 種不同的狀態(tài)红伦，會引起超市

超時的解法

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

時間復(fù)雜度 $O(N*2^{40})$

改進(jìn)

考慮到帽子有40種，但是人n最多只有10個淀衣，因此我們可以將問題轉(zhuǎn)化為昙读，將每種帽子，選擇一個人來占有它膨桥，直到n個人都有帽子為止蛮浑，此時最多只有 $40*(2^n)$ 種狀態(tài)，我們同樣采用狀態(tài)壓縮的方式国撵，當(dāng)n個人都有帽子時停止搜索陵吸，注意每個帽子我們可以選擇分配或不分配(即n個人中沒有一個人戴此帽)

優(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ù)雜度分析
時間復(fù)雜度： $O(40*2^{N})$
空間復(fù)雜度： $O(40*2^{N})$