目錄

1、1576. 替換所有的問號

2、?495. 提莫攻擊

3、6. Z 字形變換

4、38. 外觀數列

5、?1419. 數青蛙

---

1、1576. 替換所有的問號

思路：分情況討論

• ?zs：左邊沒有元素，則僅需保證替換元素與右側不相等；
• z?s：左右都有元素，則問號兩側都需要保證替換元素與其不相等；
• zs? ：右邊沒有元素，則僅需保證替換元素與左側不相等。

class Solution {
public:string modifyString(string s) {int n = s.size();for (int i = 0; i < n; i++) {if (s[i] == '?') {for (char ch = 'a'; ch <= 'z'; ch++) {if ((i == 0 || ch != s[i - 1]) &&(i == n - 1 || ch != s[i + 1])) {s[i] = ch;break;}}}}return s;}
};

2、?495. 提莫攻擊

思路：分情況討論

相鄰兩次受到攻擊的時間差與中毒持續時間進行比較，時間差大于等于中毒持續時間，則可以收到完整中毒時長，否則只能接受到時間差的中毒時長。

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int sum = 0;for (int i = 1; i < timeSeries.size(); i++) {int x = timeSeries[i] - timeSeries[i - 1];if (x >= duration)sum += duration;elsesum += x;}return sum + duration;}
};

3、6. Z 字形變換

思路：畫圖找規律

示例解釋

以 "PAYPALISHIRING" 為例，numRows = 3?時，周期?d = 4。

• 第一行字符：P（0），A（4），H（8），N（12）
• 第二行字符：A（1），P（3），L（5），S（7），I（9），I（11），G（13）
• 第三行字符：Y（2），I（6），R（10）

按行讀取這些字符后得到的新字符串是 "PAHNAPLSIIGYIR"。

1. 特殊情況處理：如果?numRows?為 1，則不需要進行任何變換，直接返回原字符串?s。

2. 周期計算：整個 Z 字形排列的一個循環周期?d?是?2 * numRows - 2。這個周期是由于從上到下再到上的一個完整循環所包含的字符數量。例如，當?numRows?為 3 時，d?為 4。

3. 第一行的字符添加：第一行的字符在原字符串中的位置就是周期?d?的倍數，即?0, d, 2d, ...。

4. 中間行的字符添加：

   • 對于中間的每一行，每個周期內都有兩個字符需要被添加到結果字符串中。第一個字符的位置是周期起始位置加行數，第二個字符的位置是周期結束位置減行數。
   • 具體來說，對于行?k（從 0 開始計數），在周期?i?中，第一個字符的位置是?i + k，第二個字符的位置是?i + d - k。
   • 注意，每次添加第二個字符時需要檢查其位置是否超出了原字符串的長度。

5. 最后一行的字符添加：最后一行的字符在原字符串中的位置是周期起始位置加?numRows - 1，即?numRows - 1, numRows - 1 + d, numRows - 1 + 2d, ...。

6. 返回結果：按照上述規則，將所有行的字符依次添加到結果字符串?ret?中后，返回?ret。

class Solution {
public:string convert(string s, int numRows) {if (numRows == 1)return s;string ret;int d = 2 * numRows - 2;int n = s.size();for (int i = 0; i < n; i += d) {ret += s[i];}for (int k = 1; k < numRows - 1; k++) {for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {ret += s[i];if (j < n)ret += s[j];}}for (int i = numRows - 1; i < n; i += d) {ret += s[i];}return ret;}
};

4、38. 外觀數列

思路：外層遍歷數組元素，內層使用雙指針尋找相同字符區間，區間相減就是相同字符的個數，區間左端點就是字符。

class Solution {
public:string countAndSay(int n) {string ret = "1";for (int i = 1; i < n; i++) {string tmp;int n = ret.size();for (int left = 0, right = 0; right < n;) {while (right < n && ret[left] == ret[right])right++;tmp += to_string(right - left) + ret[left];left = right;}ret = tmp;}return ret;}
};

5、?1419. 數青蛙

思路：

• 計數邏輯：通過追蹤每個 "croak" 中字符的狀態，確保蛙鳴聲的順序正確無誤。
• 順序檢測：確保每個蛙鳴聲都是按照正確的順序 "croak" 發出的。

1. 初始化變量：

   • s = "croak"：定義了一個青蛙蛙鳴的順序。
   • n = s.size()：蛙鳴聲 "croak" 的長度，這里是5。
   • hash：一個大小為5的向量（數組），用于追蹤 "croak" 中每個字母的狀態。
   • index：一個哈希表（unordered_map），用于映射每個字符到它在 "croak" 中的索引。

2. 處理字符串：

   • 遍歷輸入的?croakOfFrogs?字符串中的每個字符。
   • 如果字符是 'c'，表示一個新的蛙鳴聲開始。如果在?hash?的最后一個位置（對應 'k' 字符的位置）有計數，表示有一個青蛙完成了蛙鳴，可以開始新的蛙鳴，因此減少 'k' 的計數，并增加 'c' 的計數。
   • 對于 'r', 'o', 'a', 'k' 之外的 'c'，需要檢查前一個字符是否已經存在（即前一個狀態的計數是否大于0）。如果是，將前一個字符的計數減1，當前字符的計數加1。如果不是，表示蛙鳴聲的順序被打斷了，返回 -1。

3. 驗證和返回結果：

   • 遍歷?hash?向量，檢查 'c', 'r', 'o', 'a' 的計數是否都為0。如果這些位置的計數不為0，表示有蛙鳴聲沒有完成，返回 -1。
   • 如果所有 'c', 'r', 'o', 'a' 的計數都為0，最后返回 'k' 的計數，即為所需的最少青蛙數量。

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string s = "croak";int n = s.size();vector<int> hash(n);unordered_map<char, int> index;for (int i = 0; i < n; i++)index[s[i]] = i;for (auto c : croakOfFrogs) {if (c == 'c') {if (hash[n - 1] != 0)hash[n - 1]--;hash[0]++;} else {int i = index[c];if (hash[i - 1] == 0)return -1;hash[i - 1]--;hash[i]++;}}for (int i = 0; i < n - 1; i++) {if (hash[i] != 0)return -1;}return hash[n - 1];}
};