练习一：替换所有的问号
[1576. 替换所有的问号]
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); } }
练习二：提莫攻击
[495. 提莫攻击]
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 字形变换
[6. 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[] 类型来使用
练习四：外观数列
[38. 外观数列]
class Solution { public String countAndSay(int n) { String s = "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; } } sb.append(right - left).append(ch[left]); s = sb.toString(); } return s; } }