基础算法（6）——模拟

1. 替换所有的问号

题目描述：

算法思路：

从前往后遍历整个字符串，找到问号之后，尝试用 a ~ z 的每一个字符替换即可

注意点：需考虑数组开头和结尾是问号的边界情况

代码实现：

class Solution {public String modifyString(String ss) {char[] s = ss.toCharArray();int n = s.length;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 String.valueOf(s);}
}

2. 提莫攻击

题目描述：

算法思路：

代码实现：

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

3. Z 字形变换

题目描述：

解法一：模拟

算法思路：

代码实现：

这是东拼西凑写的，哪里报错改哪里，参考价值不大

class Solution {public static String convert(String s, int numRows) {int n = s.length();// 处理边界if (numRows == 1 || numRows >= n) return s;char[][] ret = new char[n][n];int x = 0;int y = 0;//将字符串填入矩阵中for (int i = 0; i < n; i++) {if (x < numRows) { // 当 x < numRows 时，向下移动ret[x][y] = s.charAt(i);x++;} else { // 向右上移动x--; // 因为上面 x++ 导致 x==numRows，所以此处--while (x != 0) {x--;y++;ret[x][y] = s.charAt(i);i++;if (i >= n) break; // 防止越界}x++; // 这里两步不知道为什么i--;}}// 将矩阵中数据添加到 ans 中StringBuilder ans = new StringBuilder();for (int i = 0; i < ret.length; i++) {for (int j = 0; j < ret.length; j++) {if (ret[i][j] != 0) {ans.append(ret[i][j]);}}}return ans.toString();}
}

解法二：找规律

算法思路：

代码实现：

class Solution {public String convert(String s, int numRows) {// 处理边界条件（若 numRows 等于 1，会造成死循环）if (numRows == 1) return s;int d = 2 * numRows - 2;int 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();}
}

4. 外观数列

题目描述：

解法：模拟 + 双指针

算法思路：

代码实现：

class Solution {public String countAndSay(int n) {String str = "1";for (int i = 1; i < n; i++) { // 由于循环从 1 开始，所以仅需解释 n-1 次即可StringBuilder ret = new StringBuilder();int len = str.length();//依次统计字符串中连续且相同的字符的个数for (int left = 0, right = 0; right < len; ) {while (right < len && str.charAt(left) == str.charAt(right)) right++;ret.append(right - left);ret.append(str.charAt(left));left = right; //  添加完之后，将 left 移动到 right 位置}str = ret.toString();}return str;}
}

5. 数青蛙

题目描述：

解法一：暴力实现

// 解法一：模拟实现，适用于解决“蛙鸣 croak” 长度少的题目
class Solution1 {public int minNumberOfFrogs(String croakOfFrogs) {char[] chars = croakOfFrogs.toCharArray();int n = chars.length;int c, r, o, a, k;c = 0; r = 0; o = 0; a = 0; k = 0;int ret = 0;for (int i = 0; i < n; i++) {if (chars[i] == 'c') {if (k > 0) k--;else ret++;c++;} else if (chars[i] == 'r') {c--; r++;} else if (chars[i] == 'o') {r--; o++;} else if (chars[i] == 'a') {o--; a++;} else if (chars[i] == 'k') {a--; k++;}if (c < 0 || r < 0 || o < 0 || a < 0) {return -1;}}if (c != 0 || r != 0 || o != 0 || a != 0) {return -1;}return ret;}
}

解法二：结合哈希表

算法思路：

当遇到 'r' 'o' 'a' 'k' 这四个字符的时候，去看看每个字符对应的前驱字符，有没有青蛙叫出来，若有，则让青蛙喊出当前字符，否则直接返回 -1

当遇到 'c' 这个字符时，去看看 'k' 这个字符有没有青蛙叫出来，若有，则让喊完 'k' 的青蛙来喊 'c'，否则重新搞一个青蛙来喊 'c'

总结：

当遇到 'r' 'o' 'a' 'k' 这四个字符的时候，找一下前驱字符是否在哈希表中

• 若存在，前驱个数--，当前字符++
• 若不在，返回-1

当遇到 'c' 字符，找最后一个字符是否在哈希表中存在

• 若存在，最后一个字符--，当前字符++
• 若不在，当前字符++

代码实现：

//解法二：模拟，用哈希表实现，适用于类似的所有题目
class Solution {public int minNumberOfFrogs(String croakOfFrogs) {char[] chars = croakOfFrogs.toCharArray();String t = "croak";int n = t.length();int[] hash = new int[n];Map<Character, Integer> index = new HashMap<>();for (int i = 0; i < n; i++) {index.put(t.charAt(i), i);}for (char ch : chars) {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];}
}