本文共 6570 字，大约阅读时间需要 21 分钟。

1. 比赛结果

全国排名：718 / 1832，39.2%；全球排名：2951 / 7699，38.3%

2. 题目

1. LeetCode 5384. 拥有最多糖果的孩子 easy

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

示例 1：输入：candies = [2,3,5,1,3], extraCandies = 3输出：[true,true,true,false,true] 解释：孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。示例 2：输入：candies = [4,2,1,1,2], extraCandies = 1输出：[true,false,false,false,false] 解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。示例 3：输入：candies = [12,1,12], extraCandies = 10输出：[true,false,true] 提示：2 <= candies.length <= 1001 <= candies[i] <= 1001 <= extraCandies <= 50

---

解答：

比赛解：没想那么多，拼手速呢，数据规模很小，直接暴力

class Solution {
   public:    vector
   
     kidsWithCandies(vector
    
     & candies, int extraCandies) {
           int i, j, k = 0, n = candies.size();        bool flag = true;        vector
     
       ans(n,false);        for(i = 0; i < n; ++i)        {
               flag = true;            for(j = 0; j < n; ++j)            {
                   if(candies[i]+extraCandies < candies[j])                {
                       flag = false;                    break;                }            }            ans[k++] = flag;        }        return ans;    }};
     
    
   

赛后优化解：

• 先把最大的找到，在一次遍历

class Solution {
   public:    vector
   
     kidsWithCandies(vector
    
     & candies, int extraCandies) {
           int i, j=0, maxCandy = *max_element(candies.begin(),candies.end()), n = candies.size();        vector
     
       ans(n,false);        for(i = 0; i < n; ++i)        {
               ans[j++] = (candies[i]+extraCandies >= maxCandy);        }        return ans;    }};
     
    
   

8 ms 9 MB

2. LeetCode 5385. 改变一个整数能得到的最大差值 medium

给你一个整数 num 。你可以对它进行如下步骤恰好 两次 ：

• 选择一个数字 x (0 <= x <= 9).
• 选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
• 将 num 中所有出现 x 的数位都用 y 替换。
• 得到的新的整数 不能 有前导 0 ，得到的新整数也 不能 是 0 。

令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的 最大差值 。

示例 1：输入：num = 555输出：888解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。现在，我们有 a = 999 和 b = 111 ，最大差值为 888示例 2：输入：num = 9输出：8解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。现在，我们有 a = 9 和 b = 1 ，最大差值为 8示例 3：输入：num = 123456输出：820000示例 4：输入：num = 10000输出：80000示例 5：输入：num = 9288输出：8700 提示：1 <= num <= 10^8

---

解题：

• 大数，找到第一个不为9的，将所有的替换掉
• 小数，找到第一个不为1也不为0的，如果这个数它是首位就用1替换，不是就用0替换

class Solution {
   public:    int maxDiff(int num) {
           vector
   
     big;        int n, i = 0, first;        while(num)        {
               big.insert(big.begin(),num%10);            num /= 10;        }        vector
    
      small(big);        n = big.size();        while(i < n)        {
               if(big[i]==9)                i++;            else                break;        }        if(i != n)        {
               first = big[i];            for( ; i < n; ++i)                if(big[i]==first)                    big[i] = 9;//换成9        }        i = 0;        while(i < n)         {
               if(small[i]<2)                i++;            else                break;        }        if(i < n)        {
               first = small[i];            if(first == small[0])//等于首位            {
                   for(i = 0; i < n; ++i)                    if(small[i]==first)                        small[i] = 1;//都变成1            }            else//不等于首位            {
                   for(i = 0; i < n; ++i)                    if(small[i]==first)                        small[i] = 0;//都变成0            }        }        int a =0, b = 0;        for(int i = 0; i < big.size(); ++i)            a = a*10+big[i];        for(int i = 0; i < big.size(); ++i)            b = b*10+small[i];        return a-b;    }};
    
   

3. LeetCode 5386. 检查一个字符串是否可以打破另一个字符串 medium

给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。

示例 1：输入：s1 = "abc", s2 = "xya"输出：true解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。示例 2：输入：s1 = "abe", s2 = "acd"输出：false 解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。示例 3：输入：s1 = "leetcodee", s2 = "interview"输出：true 提示：s1.length == ns2.length == n1 <= n <= 10^5所有字符串都只包含小写英文字母。

---

解题：

• 对s1,s2排序，依次进行对比就行，最多两次遍历

class Solution {
   public:    bool checkIfCanBreak(string s1, string s2) {
           sort(s1.begin(),s1.end());        sort(s2.begin(),s2.end());        bool flag = true;        for(int i = 0; i < s1.size(); ++i)        {
               flag &= (s1[i]>=s2[i]);            if(!flag)                break;        }        if(flag)            return flag;        flag = true;        for(int i = 0; i < s1.size(); ++i)        {
               flag &= (s1[i]<=s2[i]);            if(!flag)                break;        }        return flag;    }};

460 ms 11.8 MB

4. LeetCode 5387. 每个人戴不同帽子的方案数 hard

总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。

给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。

请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。

由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。

示例 1：输入：hats = [[3,4],[4,5],[5]]输出：1解释：给定条件下只有一种方法选择帽子。第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。示例 2：输入：hats = [[3,5,1],[3,5]]输出：4解释：总共有 4 种安排帽子的方法：(3,5)，(5,3)，(1,3) 和 (1,5)示例 3：输入：hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]输出：24解释：每个人都可以从编号为 1 到 4 的帽子中选。(1,2,3,4) 4 个帽子的排列方案数为 24 。示例 4：输入：hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]输出：111 提示：n == hats.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i] 包含一个数字互不相同的整数列表。

---

解题：

• 参考的思路

class Solution {
   public:    int numberWays(vector
   
    
     >& hats) {
       	int i, state, mod = 1e9+7, n = hats.size();//n个人    	int N = (1<
     
      > dp(41,vector
      
       (N,0));    	//dp[i][j]表示戴上第i个帽子后，人们戴帽子状态为 j(拆成二进制位0没戴，1戴了)的戴帽子方案数    	//初始化    	dp[0][0] = 1;//都没戴帽子1种情况    	vector
       
        
         > hat_p(41);//某个帽子可以戴的人 for(i = 0; i < n; ++i) for(int hat : hats[i]) hat_p[hat].insert(i); for(i = 1; i <= 40; ++i)//遍历每个帽子 { dp[i] = dp[i-1];//第i个帽子不戴 //以下处理第i个帽子要戴的情况（前提那个人i-1时候没有戴帽子） for(int p : hat_p[i])//该帽子可以戴的人p { for(state = 0; state < N; ++state)//遍历所有可能的状态 { if(((((state-(1<
         
          >p)&1)==0) { //到达state状态之前的状态是state-(1<
         
        
       
      
     
    
   

或者这么写也是对的

if(((state>>p)&1)==0){
      //上一个状态是state，状态的p位为0，没戴帽子，到达的状态该位 | 1 	dp[i][state|(1<

20 ms 13.6 MB

转载地址：https://michael.blog.csdn.net/article/details/105897792 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！