【Java 优选算法】模拟

欢迎关注个人主页：逸狼

创造不易，可以点点赞吗~

如有错误，欢迎指出~

模拟算法的思路比较简单,根据题目描述列出流程,找出规律,将流程转化为代码

替换所有的问号

题目链接

解法

直接根据题目给出条件模拟示例,找出规律

1.先找出字符?,再让满足条件的字符ch替换字符?,该条件为(字符? != 前一个字符) 并且 (字符? != 后一个字符) ,

在代码中就是(s[i - 1] != ch) && ( s[i + 1] != ch)

2.处理边界情况 : 当字符? 处在0下标处时,因为没有前一个字符,所以可以直接满足第一个条件

同理当字符? 处在n-1下标处时,因为没有后一个字符,所以可以直接满足第二个条件

在代码中就是(i == 0 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch)

画图举例

代码

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 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch)) {s[i] = ch;break;}}}}return String.valueOf(s);}
}

提莫攻击

题目链接

解法

找出规律当时间间隔x>=d时,结果ret+d,当x<d时,ret+x

画图举例

代码

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;//最后一次攻击,加上完整的中毒时间}
}

N字形变换

题目链接

解法

解法1: 利用数组模拟过程,按顺序一个个填入数组,再按要求输出

解法2: 在解法1的基础上找规律,将要输出的字符串分为3段, 在第一行中, 找到第一个字符和第二个字符的公差d = 2n - 2

第一段: 第一行;第一个放在0下标位置,第二个0+d,依次类推
第二段:中间的k行;以每两个为一组,第一组分别是k和d-k,后面依次+d
第三段:最后一行;第一个是n-1位置,后面依次+d

注意边界情况当n =1 时,直接输出原字符串

规律如下图

代码

class Solution {public String convert(String s, int numRows) {// 处理边界情况numRows=1if (numRows == 1)return s;int d = 2 * numRows - 2, n = s.length();StringBuilder ret = new StringBuilder();// 处理第一行for (int i = 0; i < n; i += d) {ret.append(s.charAt(i));}// 处理中间k行for (int k = 1; k < numRows - 1; k++) {//依次枚举中间行for (int i = k, j = d - k; 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();}
}

外观数列

题目链接

解法

模拟+ 双指针

举例如下图数组nums, 定义left=0,right=0,

当nums[left]==nums[right]时,right向后移动,直到不相等,
此时先拼接3的次数即right - left次,
再拼接该字符,依次类推

代码

class Solution {public String countAndSay(int n) {String ret = "1";for(int i = 1; i < n; i++){//从第一行开始,描述n-1次即可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;}
}

数青蛙

题目链接

解法

借用hash表用来时刻记录每个字符的出现情况

例如字符串crcoakroakcroak,从前往后扫描,以下为模拟过程

0位置字符为c,操作为c个数+1 ,
1位置字符为r,需要确认前面的字符是否有字符c,操作即为c个数-1,r个数+1
2位置字符为c,此时操作为c个数+1
重复以上操作,直到k的数为2(代表此时有两只青蛙)
最后一声croak可以叫前面2只的其中一只重复叫的(因为题目要求返回最少青蛙数), 此时操作 k - 1
当扫描到第三个k时, k+1, 最终返回 2

代码

class Solution {public int minNumberOfFrogs(String croakOfFrogs) {char[] c =croakOfFrogs.toCharArray();String t = "croak";int n = t.length();int[] hash = new int[n];//数组模拟哈希表Map<Character, Integer> index = new HashMap<>();//<x,x字符对应的下标>for(int i = 0; i < n; i++){index.put(t.charAt(i), i);}for(char ch : c){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];}
}