文章目录

• 1. 比赛结果
• 2. 题目
• 1. LeetCode 5384. 拥有最多糖果的孩子 easy
• 2. LeetCode 5385. 改变一个整数能得到的最大差值 medium
• 3. LeetCode 5386. 检查一个字符串是否可以打破另一个字符串 medium
• 4. LeetCode 5387. 每个人戴不同帽子的方案数 hard

1. 比赛结果

做出来了 1、2、3 题，1个小时做出来3题（拼手速），第2题有点卡壳，第4题动态规划很难，不会，继续加油！冲啊！

全国排名：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 <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

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

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int i, j, k = 0, n = candies.size();
        bool flag = true;
        vector<bool> 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<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int i, j=0, maxCandy = *max_element(candies.begin(),candies.end()), n = candies.size();
        vector<bool> 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<int> big;
        int n, i = 0, first;
        while(num)
        {
            big.insert(big.begin(),num%10);
            num /= 10;
        }
        vector<int> 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 == n
s2.length == n
1 <= 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.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] 包含一个数字互不相同的整数列表。

解题：

• 参考lc大佬的思路

class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
    	int i, state, mod = 1e9+7, n = hats.size();//n个人
    	int N = (1<<n);//n个人带帽子或不戴帽子有2^n种可能(这个维度比较小n最大10)
    	vector<vector<long long>> dp(41,vector<long long>(N,0));
    	//dp[i][j]表示戴上第i个帽子后，人们戴帽子状态为 j(拆成二进制位0没戴，1戴了)的戴帽子方案数
    	//初始化
    	dp[0][0] = 1;//都没戴帽子1种情况
    	vector<set<int>> 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)))>>p)&1)==0)
					{   //到达state状态之前的状态是state-(1<<p)，该位为0，p号人没有戴帽子
						dp[i][state] += dp[i-1][state-(1<<p)];
					}	//所有i-1没戴帽子的，满足条件的，戴上i号帽子，加总
				}
			}
		}
		return dp[40][N-1]%mod;//N-1表示二进制111...11，都戴了帽子
    }
};

或者这么写也是对的

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

20 ms 13.6 MB