文章目錄

• • 1. 比賽結(jié)果
  • 2. 題目
  • • 1. LeetCode 5384. 擁有最多糖果的孩子 easy
    • 2. LeetCode 5385. 改變一個(gè)整數(shù)能得到的最大差值 medium
    • 3. LeetCode 5386. 檢查一個(gè)字符串是否可以打破另一個(gè)字符串 medium
    • 4. LeetCode 5387. 每個(gè)人戴不同帽子的方案數(shù) hard

1. 比賽結(jié)果

做出來(lái)了 1、2、3 題，1個(gè)小時(shí)做出來(lái)3題（拼手速），第2題有點(diǎn)卡殼，第4題動(dòng)態(tài)規(guī)劃很難，不會(huì)，繼續(xù)加油！沖啊！

全國(guó)排名：718 / 1832，39.2%；全球排名：2951 / 7699，38.3%

2. 題目

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

題目鏈接
給你一個(gè)數(shù)組 candies 和一個(gè)整數(shù) extraCandies ，其中 candies[i] 代表第 i 個(gè)孩子擁有的糖果數(shù)目。

對(duì)每一個(gè)孩子，檢查是否存在一種方案，將額外的 extraCandies 個(gè)糖果分配給孩子們之后，此孩子有 最多 的糖果。注意，允許有多個(gè)孩子同時(shí)擁有 最多 的糖果數(shù)目。

示例 1： 輸入：candies = [2,3,5,1,3], extraCandies = 3 輸出：[true,true,true,false,true] 解釋： 孩子 1 有 2 個(gè)糖果，如果他得到所有額外的糖果（3個(gè)），那么他總共有 5 個(gè)糖果，他將成為擁有最多糖果的孩子。 孩子 2 有 3 個(gè)糖果，如果他得到至少 2 個(gè)額外糖果，那么他將成為擁有最多糖果的孩子。 孩子 3 有 5 個(gè)糖果，他已經(jīng)是擁有最多糖果的孩子。 孩子 4 有 1 個(gè)糖果，即使他得到所有額外的糖果，他也只有 4 個(gè)糖果，無(wú)法成為擁有糖果最多的孩子。 孩子 5 有 3 個(gè)糖果，如果他得到至少 2 個(gè)額外糖果，那么他將成為擁有最多糖果的孩子。示例 2： 輸入：candies = [4,2,1,1,2], extraCandies = 1 輸出：[true,false,false,false,false] 解釋：只有 1 個(gè)額外糖果，所以不管額外糖果給誰(shuí)，只有孩子 1 可以成為擁有糖果最多的孩子。示例 3： 輸入：candies = [12,1,12], extraCandies = 10 輸出：[true,false,true]提示： 2 <= candies.length <= 100 1 <= candies[i] <= 100 1 <= extraCandies <= 50

---

解答：
比賽解：沒(méi)想那么多，拼手速呢，數(shù)據(jù)規(guī)模很小，直接暴力

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

賽后優(yōu)化解：

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

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. 改變一個(gè)整數(shù)能得到的最大差值 medium

題目鏈接
給你一個(gè)整數(shù) num 。你可以對(duì)它進(jìn)行如下步驟恰好 兩次 ：

• 選擇一個(gè)數(shù)字 x (0 <= x <= 9).
• 選擇另一個(gè)數(shù)字 y (0 <= y <= 9) 。數(shù)字 y 可以等于 x 。
• 將 num 中所有出現(xiàn) x 的數(shù)位都用 y 替換。
• 得到的新的整數(shù) 不能 有前導(dǎo) 0 ，得到的新整數(shù)也 不能 是 0 。

令兩次對(duì) num 的操作得到的結(jié)果分別為 a 和 b 。

請(qǐng)你返回 a 和 b 的 最大差值 。

示例 1： 輸入：num = 555 輸出：888 解釋：第一次選擇 x = 5 且 y = 9 ，并把得到的新數(shù)字保存在 a 中。 第二次選擇 x = 5 且 y = 1 ，并把得到的新數(shù)字保存在 b 中。 現(xiàn)在，我們有 a = 999 和 b = 111 ，最大差值為 888示例 2： 輸入：num = 9 輸出：8 解釋：第一次選擇 x = 9 且 y = 9 ，并把得到的新數(shù)字保存在 a 中。 第二次選擇 x = 9 且 y = 1 ，并把得到的新數(shù)字保存在 b 中。 現(xiàn)在，我們有 a = 9 和 b = 1 ，最大差值為 8示例 3： 輸入：num = 123456 輸出：820000示例 4： 輸入：num = 10000 輸出：80000示例 5： 輸入：num = 9288 輸出：8700提示： 1 <= num <= 10^8

---

解題：

• 大數(shù)，找到第一個(gè)不為9的，將所有的替換掉
• 小數(shù)，找到第一個(gè)不為1也不為0的，如果這個(gè)數(shù)它是首位就用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++;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*10+big[i];for(int i = 0; i < big.size(); ++i)b = b*10+small[i];return a-b;} };

3. LeetCode 5386. 檢查一個(gè)字符串是否可以打破另一個(gè)字符串 medium

題目鏈接
給你兩個(gè)字符串 s1 和 s2 ，它們長(zhǎng)度相等，請(qǐng)你檢查是否存在一個(gè) s1 的排列可以打破 s2 的一個(gè)排列，或者是否存在一個(gè) s2 的排列可以打破 s1 的一個(gè)排列。

字符串 x 可以打破字符串 y （兩者長(zhǎng)度都為 n ）需滿足對(duì)于所有 i（在 0 到 n - 1 之間）都有 x[i] >= y[i]（字典序意義下的順序）。

示例 1： 輸入：s1 = "abc", s2 = "xya" 輸出：true 解釋："ayx" 是 s2="xya" 的一個(gè)排列， "abc" 是字符串 s1="abc" 的一個(gè)排列，且 "ayx" 可以打破 "abc" 。示例 2： 輸入：s1 = "abe", s2 = "acd" 輸出：false 解釋：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ， s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。 然而沒(méi)有任何 s1 的排列可以打破 s2 的排列。也沒(méi)有 s2 的排列能打破 s1 的排列。示例 3： 輸入：s1 = "leetcodee", s2 = "interview" 輸出：true提示： s1.length == n s2.length == n 1 <= n <= 10^5 所有字符串都只包含小寫英文字母。

---

解題：

• 對(duì)s1,s2排序，依次進(jìn)行對(duì)比就行，最多兩次遍歷

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. 每個(gè)人戴不同帽子的方案數(shù) hard

題目鏈接
總共有 n 個(gè)人和 40 種不同的帽子，帽子編號(hào)從 1 到 40 。

給你一個(gè)整數(shù)列表的列表 hats ，其中 hats[i] 是第 i 個(gè)人所有喜歡帽子的列表。

請(qǐng)你給每個(gè)人安排一頂他喜歡的帽子，確保每個(gè)人戴的帽子跟別人都不一樣，并返回方案數(shù)。

由于答案可能很大，請(qǐng)返回它對(duì) 10^9 + 7 取余后的結(jié)果。

示例 1： 輸入：hats = [[3,4],[4,5],[5]] 輸出：1 解釋：給定條件下只有一種方法選擇帽子。 第一個(gè)人選擇帽子 3，第二個(gè)人選擇帽子 4，最后一個(gè)人選擇帽子 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 解釋：每個(gè)人都可以從編號(hào)為 1 到 4 的帽子中選。 (1,2,3,4) 4 個(gè)帽子的排列方案數(shù)為 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] 包含一個(gè)數(shù)字互不相同的整數(shù)列表。

---

解題：

• 參考lc大佬的思路

class Solution { public:int numberWays(vector<vector<int>>& hats) {int i, state, mod = 1e9+7, n = hats.size();//n個(gè)人int N = (1<<n);//n個(gè)人帶帽子或不戴帽子有2^n種可能(這個(gè)維度比較小n最大10)vector<vector<long long>> dp(41,vector<long long>(N,0));//dp[i][j]表示戴上第i個(gè)帽子后，人們戴帽子狀態(tài)為 j(拆成二進(jìn)制位0沒(méi)戴，1戴了)的戴帽子方案數(shù)//初始化dp[0][0] = 1;//都沒(méi)戴帽子1種情況vector<set<int>> hat_p(41);//某個(gè)帽子可以戴的人for(i = 0; i < n; ++i)for(int hat : hats[i])hat_p[hat].insert(i);for(i = 1; i <= 40; ++i)//遍歷每個(gè)帽子{dp[i] = dp[i-1];//第i個(gè)帽子不戴//以下處理第i個(gè)帽子要戴的情況（前提那個(gè)人i-1時(shí)候沒(méi)有戴帽子）for(int p : hat_p[i])//該帽子可以戴的人p{for(state = 0; state < N; ++state)//遍歷所有可能的狀態(tài){if(((((state-(1<<p)))>>p)&1)==0){ //到達(dá)state狀態(tài)之前的狀態(tài)是state-(1<<p)，該位為0，p號(hào)人沒(méi)有戴帽子dp[i][state] += dp[i-1][state-(1<<p)];} //所有i-1沒(méi)戴帽子的，滿足條件的，戴上i號(hào)帽子，加總}}}return dp[40][N-1]%mod;//N-1表示二進(jìn)制111...11，都戴了帽子} };

或者這么寫也是對(duì)的

if(((state>>p)&1)==0) { //上一個(gè)狀態(tài)是state，狀態(tài)的p位為0，沒(méi)戴帽子，到達(dá)的狀態(tài)該位 | 1 dp[i][state|(1<<p)] += dp[i-1][state]; }

20 ms 13.6 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 第 25 场双周赛（718/1832，前39.2%）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。