【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=1
if (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];
}
}