网站精简布局,网站收录引擎,建站排名,青岛胶州网站建设文章目录1. 比赛结果2. 题目1. LeetCode 5384. 拥有最多糖果的孩子 easy2. LeetCode 5385. 改变一个整数能得到的最大差值 medium3. LeetCode 5386. 检查一个字符串是否可以打破另一个字符串 medium4. LeetCode 5387. 每个人戴不同帽子的方案数 hard1. 比赛结果
做出来了 1、2…
文章目录1. 比赛结果2. 题目1. LeetCode 5384. 拥有最多糖果的孩子 easy2. LeetCode 5385. 改变一个整数能得到的最大差值 medium3. LeetCode 5386. 检查一个字符串是否可以打破另一个字符串 medium4. LeetCode 5387. 每个人戴不同帽子的方案数 hard1. 比赛结果
做出来了 1、2、3 题1个小时做出来3题拼手速第2题有点卡壳第4题动态规划很难不会继续加油冲啊
全国排名718 / 183239.2%全球排名2951 / 769938.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:vectorbool kidsWithCandies(vectorint candies, int extraCandies) {int i, j, k 0, n candies.size();bool flag true;vectorbool 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:vectorbool kidsWithCandies(vectorint candies, int extraCandies) {int i, j0, maxCandy *max_element(candies.begin(),candies.end()), n candies.size();vectorbool 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) {vectorint big;int n, i 0, first;while(num){big.insert(big.begin(),num%10);num / 10;}vectorint small(big);n big.size();while(i n){if(big[i]9)i;elsebreak;}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;elsebreak;}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*10big[i];for(int i 0; i big.size(); i)b b*10small[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 是 s2xya 的一个排列
abc 是字符串 s1abc 的一个排列且 ayx 可以打破 abc 。示例 2
输入s1 abe, s2 acd
输出false
解释s1abe 的所有排列包括abeaebbaebeaeab 和 eba
s2acd 的所有排列包括acdadccadcdadac 和 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(vectorvectorint hats) {int i, state, mod 1e97, n hats.size();//n个人int N (1n);//n个人带帽子或不戴帽子有2^n种可能(这个维度比较小n最大10)vectorvectorlong long dp(41,vectorlong long(N,0));//dp[i][j]表示戴上第i个帽子后人们戴帽子状态为 j(拆成二进制位0没戴1戴了)的戴帽子方案数//初始化dp[0][0] 1;//都没戴帽子1种情况vectorsetint 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-(1p)))p)1)0){ //到达state状态之前的状态是state-(1p)该位为0p号人没有戴帽子dp[i][state] dp[i-1][state-(1p)];} //所有i-1没戴帽子的满足条件的戴上i号帽子加总}}}return dp[40][N-1]%mod;//N-1表示二进制111...11都戴了帽子}
};或者这么写也是对的
if(((statep)1)0)
{ //上一个状态是state状态的p位为0没戴帽子到达的状态该位 | 1 dp[i][state|(1p)] dp[i-1][state];
}20 ms 13.6 MB
