[Java 算法] 模拟
练习一 : 替换所有的问号
class Solution { public String modifyString(String s) { char[] ch = s.toCharArray(); for(int i = 0;i<ch.length;i++){ if(ch[i] == '?'){ for(char tmp = 'a';tmp<='z';tmp++){ if((i == 0||tmp!=ch[i-1])&&(i ==ch.length-1||tmp!=ch[i+1])){ ch[i] = tmp; break; } } } } return String.valueOf(ch); } }练习二 : 提莫攻击
class Solution { public int findPoisonedDuration(int[] nums, int duration) { int ret = 0; for(int i = 0;i<nums.length;i++){ if((i == nums.length-1)||(nums[i+1]-nums[i]>=duration)){ ret+=duration; }else{ ret+=nums[i+1]-nums[i]; } } return ret; } }练习三 : Z 字形变换
class Solution { public String convert(String s, int numRows) { char[] ch = s.toCharArray(); if(numRows == 1||s.length()<=numRows){ return s; } StringBuilder sb = new StringBuilder(); int d = 2*numRows-2; for(int i = 0;i<numRows;i++){ ; int k = 0; while(i+k*d<ch.length){ if(i == 0||i == numRows-1){ sb.append(ch[i+k*d]); }else{ sb.append(ch[i+k*d]); if((d-i+k*d)<s.length()){ sb.append(ch[d-i+k*d]); } } k++; } } return sb.toString(); } }图解 :
算法原理 :
- 如果行数位 1 , 或者字符串长度小于等于行数 , 则直接返回字符串
- 模拟以上图解 :
第 0 行和最后一行 : 在行数的基础上每个周期 , 加上一个公差(d = 2n-2)
其余行 : 两个元素为一组 , 每个周期加上一个公差 , 例如 第 i 行 , 周期为 0 , 两个元素的下标表示为 : (i , d-i) ; (其中 d 为公差)
细节问题 :
① 周期次数放在 if-else 判断外 , 以免产生死循环
② String 类型为不可变类型 , 使用时需要配合 StringBuilder 和 char[] 类型来使用
练习四 : 外观数列
class Solution { public String countAndSay(int n) { // 初始值：n=1时结果为"1" String s = "1"; // 核心：只需要循环n-1次（因为初始已经是n=1的结果） for (int i = 2; i <= n; i++) { char[] ch = s.toCharArray(); StringBuilder sb = new StringBuilder(); int left = 0, right = 0; // 双指针统计连续相同字符 while (right < ch.length) { if (ch[left] == ch[right]) { right++; } else { // 统计数量 + 拼接字符 sb.append(right - left).append(ch[left]); left = right; } } // 处理最后一组连续字符（循环结束后left未到末尾） sb.append(right - left).append(ch[left]); // 更新s为当前轮的结果，供下一轮描述 s = sb.toString(); } return s; } }
