LeetCode 第 25 场双周赛（718/1832，前39.2%）
LeetCode 第 25 场双周赛（718/1832，前39.2%）
Michael阿明
发布于 2020-07-13 14:13:20
发布于 2020-07-13 14:13:20
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 <= 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
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/05/03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
