Java 算法：模拟类题目实战

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. 如果行数为 1，或者字符串长度小于等于行数，则直接返回字符串
2. 模拟图解逻辑：
   • 第 0 行和最后一行：在行数的基础上每个周期加上一个公差 (d = 2n-2)
   • 其余行：两个元素为一组，每个周期加上一个公差，例如第 i 行，周期为 0，两个元素的下标表示为：(i, d-i)；(其中 d 为公差)

细节问题

1. 周期次数放在 if-else 判断外，以免产生死循环
2. 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; } }