文章目錄

• • 1. 比賽結(jié)果
  • 2. 題目
  • • 1. LeetCode 5468. 第 k 個缺失的正整數(shù) easy
    • 2. LeetCode 5469. K 次操作轉(zhuǎn)變字符串 medium
    • 3. LeetCode 5470. 平衡括號字符串的最少插入次數(shù) medium
    • 4. LeetCode 5485. 找出最長的超贊子字符串 hard

1. 比賽結(jié)果

兩題選手報道，繼續(xù)加油！

全國排名： 983 / 2957，33.2%；全球排名： 2962 / 10463，28.3%

2. 題目

1. LeetCode 5468. 第 k 個缺失的正整數(shù) easy

題目鏈接

給你一個 嚴(yán)格升序排列 的正整數(shù)數(shù)組 arr 和一個整數(shù) k 。

請你找到這個數(shù)組里第 k 個缺失的正整數(shù)。

示例 1： 輸入：arr = [2,3,4,7,11], k = 5 輸出：9 解釋：缺失的正整數(shù)包括 [1,5,6,8,9,10,12,13,...] 。 第 5 個缺失的正整數(shù)為 9 。示例 2： 輸入：arr = [1,2,3,4], k = 2 輸出：6 解釋：缺失的正整數(shù)包括 [5,6,7,...] 。 第 2 個缺失的正整數(shù)為 6 。提示： 1 <= arr.length <= 1000 1 <= arr[i] <= 1000 1 <= k <= 1000 對于所有 1 <= i < j <= arr.length 的 i 和 j 滿足 arr[i] < arr[j]

---

解題：

class Solution { public:int findKthPositive(vector<int>& arr, int k) {int num = 1, ans = 1, idx = 0;while(idx < arr.size()){if(arr[idx] != num){ //不等的時候k--;ans = num;}elseidx++;//相等時，跳過該數(shù)if(k == 0)break;num++;}return k!=0 ? arr[arr.size()-1]+k : ans;} };

2. LeetCode 5469. K 次操作轉(zhuǎn)變字符串 medium

題目鏈接

給你兩個字符串 s 和 t ，你的目標(biāo)是在 k 次操作以內(nèi)把字符串 s 轉(zhuǎn)變成 t 。

在第 i 次操作時（1 <= i <= k），你可以選擇進(jìn)行如下操作：

• 選擇字符串 s 中滿足 1 <= j <= s.length 且之前未被選過的任意下標(biāo) j （下標(biāo)從 1 開始），并將此位置的字符切換 i 次。
  不進(jìn)行任何操作。
• 切換 1 次字符的意思是用字母表中該字母的下一個字母替換它（字母表環(huán)狀接起來，所以 ‘z’ 切換后會變成 ‘a(chǎn)’）。

請記住任意一個下標(biāo) j 最多只能被操作 1 次。

如果在不超過 k 次操作內(nèi)可以把字符串 s 轉(zhuǎn)變成 t ，那么請你返回 true ，否則請你返回 false 。

示例 1： 輸入：s = "input", t = "ouput", k = 9 輸出：true 解釋：第 6 次操作時，我們將 'i' 切換 6 次得到 'o' 。 第 7 次操作時，我們將 'n' 切換 7 次得到 'u' 。示例 2： 輸入：s = "abc", t = "bcd", k = 10 輸出：false 解釋：我們需要將每個字符切換 1 次才能得到 t 。 我們可以在第 1 次操作時將 'a' 切換成 'b' ， 但另外 2 個字母在剩余操作中無法再轉(zhuǎn)變?yōu)?t 中對應(yīng)字母。示例 3： 輸入：s = "aab", t = "bbb", k = 27 輸出：true 解釋：第 1 次操作時，我們將第一個 'a' 切換 1 次得到 'b' 。 在第 27 次操作時，我們將第二個字母 'a' 切換 27 次得到 'b' 。提示： 1 <= s.length, t.length <= 10^5 0 <= k <= 10^9 s 和 t 只包含小寫英文字母。

---

解題：

• 每個字符找對應(yīng)的字符，如果兩對字符都是相差5，那么第二對就要多轉(zhuǎn)一圈，5+26

class Solution { public:bool canConvertString(string s, string t, int k) {if(s.size() != t.size())return false;int diff;vector<int> count(26, 0);for(int i = 0; i < s.size(); ++i){if(s[i] == t[i])continue;if(s[i] < t[i])diff = t[i]-s[i];else if(s[i] > t[i])diff = 'z'-s[i]+t[i]-'a'+1;count[diff]++;//diif次轉(zhuǎn)換，有多少次}for(int i = 0; i < 26; ++i){if((count[i]-1)*26+i > k)//需要的轉(zhuǎn)換次數(shù)最大值，超了return false;}return true;} };

3. LeetCode 5470. 平衡括號字符串的最少插入次數(shù) medium

題目鏈接

給你一個括號字符串 s ，它只包含字符 '(' 和 ')' 。一個括號字符串被稱為平衡的當(dāng)它滿足：

• 任何左括號 '(' 必須對應(yīng)兩個連續(xù)的右括號 '))' 。
• 左括號 '(' 必須在對應(yīng)的連續(xù)兩個右括號 '))' 之前。

比方說 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

請你返回讓 s 平衡的最少插入次數(shù)。

示例 1： 輸入：s = "(()))" 輸出：1 解釋：第二個左括號有與之匹配的兩個右括號， 但是第一個左括號只有一個右括號。 我們需要在字符串結(jié)尾額外增加一個 ')' 使字符串變成平衡字符串 "(())))" 。示例 2： 輸入：s = "())" 輸出：0 解釋：字符串已經(jīng)平衡了。示例 3： 輸入：s = "))())(" 輸出：3 解釋：添加 '(' 去匹配最開頭的 '))' ， 然后添加 '))' 去匹配最后一個 '(' 。示例 4： 輸入：s = "((((((" 輸出：12 解釋：添加 12 個 ')' 得到平衡字符串。示例 5： 輸入：s = ")))))))" 輸出：5 解釋：在字符串開頭添加 4 個 '(' 并在結(jié)尾添加 1 個 ')' ， 字符串變成平衡字符串 "(((())))))))" 。提示： 1 <= s.length <= 10^5 s 只包含 '(' 和 ')' 。

---

解題：
類似題目：LeetCode 921. 使括號有效的最少添加（棧）

class Solution { public:int minInsertions(string s) {int sum = 0;stack<char> stk;int n = s.size();for(int i = 0; i < n; ++i){if(s[i] == '(')stk.push('(');else if(s[i] == ')'){if(i+1 < n && s[i+1] == ')'){if(!stk.empty())stk.pop();// ())消除elsesum++;//補一個左括號i++;//后面的 ) 已經(jīng)處理了}else//后面沒有 ）{if(!stk.empty()){ //有左括號stk.pop();sum++;// 補一個右括號}else//沒有左括號sum += 2;//補一個左，一個右括號}}}while(!stk.empty()){stk.pop();sum += 2;}return sum;} };

借助921題思路

class Solution { public:int minInsertions(string s) {//先預(yù)處理，把 ）） 變成 ）string ans;int l = 0, r = 0, sum = 0;for(int i = 0; i < s.size(); ++i){if(i+1 < s.size() && s[i]==')' && s[i+1] == ')'){ans += ")";//連續(xù)的兩個變成1個 ）i++;continue;}if(s[i] == ')')sum++;//落單的 ）記錄下來有多少個ans += s[i];}for(int i = 0; i < ans.size(); ++i){ //921 題的套路if(ans[i] == '(') l++;else{if(l>0) //右括號可以與之匹配l--;else //右括號沒有相應(yīng)的左括號匹配r++;} }return 2*l+r+sum;} };

4. LeetCode 5485. 找出最長的超贊子字符串 hard

題目鏈接

給你一個字符串 s 。請返回 s 中最長的 超贊子字符串 的長度。

「超贊子字符串」需滿足滿足下述兩個條件：

• 該字符串是 s 的一個非空子字符串
• 進(jìn)行任意次數(shù)的字符交換重新排序后，該字符串可以變成一個回文字符串

示例 1： 輸入：s = "3242415" 輸出：5 解釋："24241" 是最長的超贊子字符串， 交換其中的字符后，可以得到回文 "24142"示例 2： 輸入：s = "12345678" 輸出：1示例 3： 輸入：s = "213123" 輸出：6 解釋："213123" 是最長的超贊子字符串， 交換其中的字符后，可以得到回文 "231132"示例 4： 輸入：s = "00" 輸出：2提示： 1 <= s.length <= 10^5 s 僅由數(shù)字組成

---

解題：

• 狀態(tài)壓縮+哈希記錄第一次出現(xiàn)的狀態(tài)

class Solution { public:int longestAwesome(string s) {if(s.size() <= 1) return s.size();unordered_map<int, int> m;m[0] = -1;//空字符所有的0-9位都是0int maxlen = 1, state = 0;for(int i = 0; i < s.size(); ++i){state ^= (1<<(s[i]-'0'));//該數(shù)位奇偶變化了if(m.count(state))//相同的狀態(tài)，同奇同偶，相減還是偶數(shù)個maxlen = max(maxlen, i-m[state]);elsem[state] = i;//考慮有一個位不一樣，就是相減后只有一個位是奇數(shù)，還是回文for(int j = 0; j < 10; ++j){int odd_state = state^(1<<j);if(m.count(odd_state))maxlen = max(maxlen, i-m[odd_state]);}}return maxlen;} };

---

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

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

總結(jié)

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

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