第25场双周赛

前言

拥有最多糖果的孩子 ${\color{green}{\text{[简单]}}}$
改变一个整数能得到的最大差值 ${\color{orange}{\text{[中等]}}}$
检查一个字符串是否可以打破另一个字符串 ${\color{orange}{\text{[中等]}}}$
每个人戴不同帽子的方案数 ${\color{red}{\text{[困难]}}}$

拥有最多糖果的孩子

题目链接
解释：即要求判断每个孩子目前所拥有的糖果数量加上extraCandies是否大于等于孩子们所拥有糖果数目的最大值

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

复杂度分析
时间复杂度： $O(N)$
空间复杂度： $O(1)$ 不包括结果数组

改变一个整数能得到的最大差值

题目链接
分析：即要求我们分别找到将原数中某一位全部替换成另外一个数字后的最大值和最小值，求其差。要求是替换后不能有前导0以及为0。贪心算法。

求最大值的方法：

从左到右，找到第一位小于9的数字，将所有该数字替换为9，即为最大值

求最小值的方法：

为了没有前导0和本身为0，需要分类讨论

若原数中首位数字大于1,则将原数中所有该数字替换为1，即得最小值。

否则，从左到右找到第一个大于等于2的数字，将其全部替换为0，即得最小值

代码

class Solution {
   public int maxDiff(int num) {
       return getMax(num)-getMin(num);
   }
   // 从左到右找到第一个不为`9`的数字，把他们替换成`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`，则把所有首位数字替换成`1`
   // 2. 否则找一个最靠左，且不是首位并且大等于于`2`的数字，将所有该数字替换成`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));
   }
}

复杂度分析：
时间复杂度： $O(len(num))$ len(num)为num的位数
空间复杂度: $O(len(num))$ len(num)为num的位数

检查一个字符串是否可以打破另一个字符串

题目链接
分析：要求我们找出字符串s1和s2中的一个排列，使得所有对应位置上的字符，总有s1[i] <= s2[i]或所有对应位置上的字符,总有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;
    }
}

复杂度分析：
时间复杂度： $O(NlogN)$ $N$ 为字符串长度，开销来自于排序算法
空间复杂度： $O(N)$

每个人戴不同帽子的方案数

题目链接
分析：一共有40种不同的帽子和n个人，每个人有自己喜欢的帽子，求每个人都带到自己喜欢的帽子且n个人帽子都不相同的方案数

记忆化搜索&状态压缩：

因为共有40种帽子，以及n<=10个人，因此可想到压缩成一个Long型的值，其中40位表示这40种帽子哪些被人戴过了，还有1位表示当前给第几个人分配帽子，我们把该状态存进一个Map对象里，防止重复计算。不幸的是，因为40种帽子，则有 $2^{40}$ 种不同的状态，会引起超市

超时的解法

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

时间复杂度 $O(N*2^{40})$

改进

考虑到帽子有40种，但是人n最多只有10个，因此我们可以将问题转化为，将每种帽子，选择一个人来占有它，直到n个人都有帽子为止，此时最多只有 $40*(2^n)$ 种状态，我们同样采用状态压缩的方式，当n个人都有帽子时停止搜索，注意每个帽子我们可以选择分配或不分配(即n个人中没有一个人戴此帽)

优化的解法



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

复杂度分析
时间复杂度： $O(40*2^{N})$
空间复杂度： $O(40*2^{N})$