基础算法（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];
}
}原文地址：https://blog.csdn.net/Yuan_o_/article/details/142723645
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！