專欄：算法的魔法世界

個人主頁：手握風云

目錄

一、模擬

二、例題講解

2.1.?替換所有的問號

2.2.?提莫攻擊

2.3.?Z字形變換

2.4.?外觀數列

2.5.?數青蛙

---

一、模擬

? ? ? ? 模擬算法說簡單點就是照葫蘆畫瓢，現在草稿紙上模擬一遍算法過程，再把算法過程轉化為代碼。

二、例題講解

2.1.?替換所有的問號

? ? ? ? 方法中所給的字符串s只含小寫字母和問號，我們需要把這個問號轉化為某個小寫字母，得到一個連續重復字符的新字符串。

? ? ? ? 我們先將字符串轉化為字符數組，然后從前遍歷這個字符數組。當遇到"?"時，從26個英文字母找到第一個既不等與它的前一位有不等于它的后一位的字符。當我們還需要注意一下邊界情況，比如"?"在數組的第0位上，前一位不存在，只需要比較后面一位即可。

? ? ? ? 完整代碼實現：

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

2.2.?提莫攻擊

? ? ? ? 艾希受到提莫的攻擊，會對艾希造成持續兩秒的中毒效果，如果在中毒期間再次受到攻擊，那么中毒時間還會重置，題目要求我們輸出中毒的總時長。

? ? ? ? ·我們需要遍歷一邊數組，計算每兩個相鄰元素的差x，如果x大于等于中毒持續時間duration，則中毒時間ret加上duration；如果x小于duration，則ret直接加上x。但比較容易忽略的一點是數組的最后一個元素沒有下一個元素，所以最后的返回值再要加上一個duration。

? ? ? ? 完整代碼實現：

class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int ret = 0;for (int i = 1; i < timeSeries.length; i++) {int x = timeSeries[i] - timeSeries[i - 1];if(x >= duration) ret += duration;else ret += x;}return ret + duration;}
}

2.3.?Z字形變換

? ? ? ? 題目要求我們將給定的字符串變為倒Z排列，然后再以從左到右的順序輸出，得到一個新字符串。我們要想成功模擬出這個過程，需要借助一個矩陣來儲存字符。我們以示例1為例，先創建一個n行的矩陣，先向下填充，當x=n時，開始右上填充，當x=0時，又開始向下填充……。假設字符串長度為len，因為我們記得遍歷字符串又得遍歷矩陣，所以時間復雜度和空間復雜度都為。

? ? ? ? 我們接下來可以通過找規律來對算法進行優化。如果矩陣里面填充的是字符的下標，那我們就可以發現規律了。第0行和第n-1行的數字正好構成了等差數列，且公差d為2n-2。接下來枚舉第1行到第n-1行，1、5、9、13依然是構成了等差數列，3、7、11構成等差數列，(1,3)->(5,7)->(9,11)。

? ? ? ? 完整代碼：

class Solution {public String convert(String s, int numRows) {//處理一下邊界情況if(numRows == 1) return s;int d = 2 * numRows - 2, n = s.length();StringBuilder ret = new StringBuilder();//1.處理第一行for (int i = 0; i < n; i += d)ret.append(s.charAt(i));//2.處理中間行for (int k = 1; k < numRows - 1; k++) {//一次枚舉中間行for (int i = k, j = d - i; i < n || j < n; i += d, j += d) {if (i < n) ret.append(s.charAt(i));if (j < n) ret.append(s.charAt(j));}}//3.處理最后一行for (int i = numRows - 1; i < n; i += d) {ret.append(s.charAt(i));}return ret.toString();}
}

2.4.?外觀數列

? ? ? ? 本題的輸出結果就是對第n-1的解釋，當n=1時，字符串s="1"；當n=2時，前一項是1個1，記為"11"；當n=3時，前一項是2個1，記為"21"；當n=4時，前一項時1個2和1個1，記為"1211"……規律就是對上一項連續相同的字符元素進行分類。

? ? ? ? 我們可以利用雙指針進行模擬。先初始化兩個指針left和right，比較left和right是否相等，相等right就向右移動，當right的指向與left不相等時，right就停止，此時的left直接移動到right的位置。以此循環，直到right移動到字符串的結尾的后一位。前一類元素個數的計算right-1-left+1，作為對上一類元素的解釋。

? ? ? ? 完整代碼實現：

class Solution {public String countAndSay(int n) {String ret = "1";//先初始化n=1時的字符串for (int i = 1; i < n; i++) {StringBuilder tmp = new StringBuilder();int len = ret.length();for (int left = 0,right = 0;right < len;){while(right < len && (ret.charAt(left) == ret.charAt(right))) right++;tmp.append(Integer.toString(right - left));tmp.append(ret.charAt(left));left = right;}ret = tmp.toString();}return ret;}
}

2.5.?數青蛙

????????題目要求我們根據給定的字符串，計算出最少需要多少只青蛙才能完成鳴叫的過程。鳴叫的過程必須按照"croak"的順序進行。比如"croakcroak"，一只青蛙先叫完1聲，還可以接著叫第2聲；"crcoakroak"，"cr"后面是"c"，就需要另一只青蛙開始叫。

? ? ? ? 我們先從頭到尾遍歷一遍字符串，，比如我們遍歷到a時，只需確定a的前面是不是r，所以我們還需要一個哈希表來記錄每個字符出現的情況。當遍歷到c時，哈希表中c加1；如果遍歷到r時，檢查前一個是不是c，如果是，則c--，r++。重復以上操作，

? ? ? ? 如上圖，k后面又是c，我們還需要給c記錄上1，而我們要求的是所需不同青蛙的最少數目，所以我們從k里面借一個1，再去遍歷最后一個"croak"，最終k里面存的就是最終結果。當遍歷完字符串之后，k前面還有非0元素，說明還有青蛙沒有叫完，則返回-1。

? ? ? ? 還有一種情況，如果給定的字符串是"crroak"，遍歷到第二個r時，哈希表中的c為0，直接返回-1。所以我們可以總結出：當r、o、a、k的前驅字符再哈希表時，前驅個數--，當前字符++，不存在直接返回-1；如果是c，找k是否存在于哈希表中，存在前驅個數--，當前字符++，不存在直接返回-1。

????????完整代碼實現：

class Solution {public int minNumberOfFrogs(String croakOfFrogs) {char[] croakOf = croakOfFrogs.toCharArray();String t = "croak";int n = t.length();int[] hash = new int[5];Map<Character,Integer> index = new HashMap<>();for (int i = 0; i < n; i++)index.put(t.charAt(i),i);for (char ch : croakOf) {if(ch == t.charAt(0)) {if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;}else {int i = index.get(ch);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];}
}