文章目錄

• • 1. 比賽結(jié)果
  • 2. 題目
  • • 1. LeetCode 5483. 整理字符串 easy
    • 2. LeetCode 5484. 找出第 N 個二進(jìn)制字符串中的第 K 位 medium
    • 3. LeetCode 5471. 和為目標(biāo)值的最大數(shù)目不重疊非空子數(shù)組數(shù)目 medium
    • 4. LeetCode 5486. 切棍子的最小成本 hard

1. 比賽結(jié)果

做出來3題，第二題暴力可以過，我想著不行，找規(guī)律失敗。繼續(xù)加油！

全國排名： 304 / 5614，5.42%；全球排名： 956 / 15616，6.12%

2. 題目

1. LeetCode 5483. 整理字符串 easy

題目鏈接

給你一個由大小寫英文字母組成的字符串 s 。

一個整理好的字符串中，兩個相鄰字符 s[i] 和 s[i + 1] 不會同時滿足下述條件：

• 0 <= i <= s.length - 2
• s[i] 是小寫字符，但 s[i + 1] 是相同的大寫字符；反之亦然 。

請你將字符串整理好，每次你都可以從字符串中選出滿足上述條件的 兩個相鄰 字符并刪除，直到字符串整理好為止。

請返回整理好的 字符串 。題目保證在給出的約束條件下，測試樣例對應(yīng)的答案是唯一的。

注意：空字符串也屬于整理好的字符串，盡管其中沒有任何字符。

示例 1： 輸入：s = "leEeetcode" 輸出："leetcode" 解釋：無論你第一次選的是 i = 1 還是 i = 2， 都會使 "leEeetcode" 縮減為 "leetcode" 。示例 2： 輸入：s = "abBAcC" 輸出："" 解釋：存在多種不同情況，但所有的情況都會導(dǎo)致相同的結(jié)果。例如： "abBAcC" --> "aAcC" --> "cC" --> "" "abBAcC" --> "abBA" --> "aA" --> ""示例 3： 輸入：s = "s" 輸出："s"提示： 1 <= s.length <= 100 s 只包含小寫和大寫英文字母

---

解題：

• 使用棧解題

class Solution { public:string makeGood(string s) {if(s.size() <= 1)return s;string ans;stack<char> stk;for(int i = 0; i < s.size(); ++i){if(!stk.empty() && ((s[i]-stk.top()==32)|| (stk.top()-s[i]==32)))stk.pop();//前后是大小寫關(guān)系elsestk.push(s[i]);}while(!stk.empty()){ans = stk.top()+ans;stk.pop();}return ans;} };

2. LeetCode 5484. 找出第 N 個二進(jìn)制字符串中的第 K 位 medium

題目鏈接

給你兩個正整數(shù) n 和 k，二進(jìn)制字符串 Sn 的形成規(guī)則如下：

• S1 = "0"
• 當(dāng) i > 1 時，Si = Si-1 + "1" + reverse(invert(Si-1))

其中 + 表示串聯(lián)操作，reverse(x) 返回反轉(zhuǎn) x 后得到的字符串，而 invert(x) 則會翻轉(zhuǎn) x 中的每一位（0 變?yōu)?1，而 1 變?yōu)?0）

例如，符合上述描述的序列的前 4 個字符串依次是：

S1 = "0" S2 = "011" S3 = "0111001" S4 = "011100110110001"

請你返回 S_n 的 第 k 位字符 ，題目數(shù)據(jù)保證 k 一定在 S_n 長度范圍以內(nèi)。

示例 1： 輸入：n = 3, k = 1 輸出："0" 解釋：S3 為 "0111001"，其第 1 位為 "0" 。示例 2： 輸入：n = 4, k = 11 輸出："1" 解釋：S4 為 "011100110110001"，其第 11 位為 "1" 。示例 3： 輸入：n = 1, k = 1 輸出："0"示例 4： 輸入：n = 2, k = 3 輸出："1"提示： 1 <= n <= 20 1 <= k <= 2^n - 1

---

解題：

• 比賽沒想著暴力法，暴力很簡單

class Solution { public:char findKthBit(int n, int k) {if(n==1 || k==1) return '0';string s = "0", next;while(--n){next = s+"1";for(int i = s.size()-1; i >= 0; --i)next += s[i]=='1' ? '0' : '1';s = next;}return s[k-1];} };

循環(huán)解法：

class Solution { public:char findKthBit(int n, int k) {if(k==1 || n==1)return '0';k--;int len = (1<<n)-1;//字符串長度為2^n-1if(k == len/2) return '1';bool reverse = false;while(n) {len = (1<<n)-1;//字符串長度為2^n-1if(k == 0)//找到最前面了，狀態(tài)不會再變break;else if(k > len/2) {reverse = !reverse;//后半部分會反轉(zhuǎn)狀態(tài)k = len-1-k;//位置對應(yīng)于前一個字符的位置}n--;}return reverse ? '1' : '0';} };

遞歸解法

class Solution { public:char findKthBit(int n, int k) {if(k==1 || n==1)return '0';k--;int len = (1<<n)-1;//字符串長度為2^n-1if(k == len/2) return '1';return dfs(n, k);}char dfs(int n, int k){if(n==1 || k == 0)return '0';int len = (1<<n)-1;if(k == len/2) return '1';if(k > len/2) return dfs(n-1, len-1-k)=='1' ? '0' : '1';return dfs(n-1, k);} };

3. LeetCode 5471. 和為目標(biāo)值的最大數(shù)目不重疊非空子數(shù)組數(shù)目 medium

題目鏈接

給你一個數(shù)組 nums 和一個整數(shù) target 。

請你返回 非空不重疊 子數(shù)組的最大數(shù)目，且每個子數(shù)組中數(shù)字和都為 target 。

示例 1： 輸入：nums = [1,1,1,1,1], target = 2 輸出：2 解釋：總共有 2 個不重疊子數(shù)組（加粗?jǐn)?shù)字表示） [1,1,1,1,1] ， 它們的和為目標(biāo)值 2 。示例 2： 輸入：nums = [-1,3,5,1,4,2,-9], target = 6 輸出：2 解釋：總共有 3 個子數(shù)組和為 6 。 ([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 個是不重疊的。示例 3： 輸入：nums = [-2,6,6,3,5,4,1,2,8], target = 10 輸出：3示例 4： 輸入：nums = [0,0,0], target = 0 輸出：3提示： 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 0 <= target <= 10^6

---

解題：

• 使用哈希記錄狀態(tài)，貪心，找到一個存在狀態(tài)，子數(shù)組+1，哈希清空(題目要求無重復(fù)的子數(shù)組)

class Solution { public:int maxNonOverlapping(vector<int>& nums, int target) {unordered_set<int> set;set.insert(0);//和為0存在int sum = 0, count = 0;for(int i = 0; i < nums.size(); ++i){sum += nums[i];if(set.count(sum-target)){count++;set.clear();}set.insert(sum);}return count;} };

4. LeetCode 5486. 切棍子的最小成本 hard

題目鏈接

有一根長度為 n 個單位的木棍，棍上從 0 到 n 標(biāo)記了若干位置。例如，長度為 6 的棍子可以標(biāo)記如下：

給你一個整數(shù)數(shù)組 cuts ，其中 cuts[i] 表示你需要將棍子切開的位置。

你可以按順序完成切割，也可以根據(jù)需要更改切割的順序。

每次切割的成本都是當(dāng)前要切割的棍子的長度，切棍子的總成本是歷次切割成本的總和。
對棍子進(jìn)行切割將會把一根木棍分成兩根較小的木棍（這兩根木棍的長度和就是切割前木棍的長度）。請參閱第一個示例以獲得更直觀的解釋。

返回切棍子的 最小總成本 。

示例 1：

輸入：n = 7, cuts = [1,3,4,5] 輸出：16 解釋：按 [1, 3, 4, 5] 的順序切割的情況如下所示： 第一次切割長度為 7 的棍子，成本為 7 。 第二次切割長度為 6 的棍子（即第一次切割得到的第二根棍子）， 第三次切割為長度 4 的棍子，最后切割長度為 3 的棍子。 總成本為 7 + 6 + 4 + 3 = 20 。 而將切割順序重新排列為 [3, 5, 1, 4] 后，總成本 = 16 （如示例圖中 7 + 4 + 3 + 2 = 16）。

示例 2： 輸入：n = 9, cuts = [5,6,1,4,2] 輸出：22 解釋：如果按給定的順序切割，則總成本為 25 。 總成本 <= 25 的切割順序很多， 例如，[4，6，5，2，1] 的總成本 = 22， 是所有可能方案中成本最小的。提示： 2 <= n <= 10^6 1 <= cuts.length <= min(n - 1, 100) 1 <= cuts[i] <= n - 1 cuts 數(shù)組中的所有整數(shù)都 互不相同

---

解題：

• 區(qū)間DP

class Solution {int ans = 0; public:int minCost(int n, vector<int>& cuts) {if(cuts.size() == 1) return n;cuts.push_back(0);cuts.push_back(n);sort(cuts.begin(), cuts.end());int m = cuts.size(), i, j;vector<vector<int>> dp(m, vector<int>(m, 0x7f7f7f7f));for(int i = 1; i < m; ++i)dp[i-1][i] = 0;//最小的段不需要切成本為0，最小區(qū)間for(int len = 2; len < m; ++len)//區(qū)間變大{for(int i = 0; i < m; ++i)//枚舉左端點(diǎn){int j = i+len;//右端點(diǎn)if(j >= m) continue;for(int k = j-1; k > i; --k)//從左右端點(diǎn)中間枚舉切分點(diǎn){dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+cuts[j]-cuts[i]);//左右兩段的成本+切開本次的成本cuts[j]-cuts[i]（總長度）}}}return dp[0][m-1];} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 第 201 场周赛（304/5614，前5.42%）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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