https://leetcode-cn.com/problems/zigzag-conversion/
做这道题，我的解答先从找规律开始
先放执行效率的图
容许我先狂笑10秒
代码如下
public String convert(String s, int numRows) {
int length = s.length();
if(length<=2||numRows<=1) return s;
int numInGroup = 2*numRows - 2;
int groupNums = length/numInGroup +1;
StringBuilder sb = new StringBuilder();
int row = 1;
while(row<= numRows){
if(row==1){
for (int num = 0; num < groupNums; num++) append(sb, s, num*numInGroup, length);
}else if(row == numRows){
for (int num = 0; num < groupNums; num++) append(sb, s, num*numInGroup+numRows-1, length);
}else{
for (int num = 0; num < groupNums; num++) {
append(sb, s, num*numInGroup+row - 1, length);
append(sb, s, num*numInGroup+numInGroup-row+1, length);
}
}
row++;
}
return sb.toString();
}
public void append(StringBuilder sb,String s,int index,int length){
if(index <length) sb.append(s.charAt(index));
}
时间复杂度是O(n)
用到的变量有点多，同学们可能会看的有点懵。这个破题方法的重点在于找出数据之间的规律,下面说说规律以及用到的变量。
找规律
1.数据分组
图一 “LEETCODEISHIRING”函数为3的Z字变形结果
将Z字变形结果拆分成如图一所示的四组(group)数据，为什么可以这样拆分呢？没懂?没关系，往下看！
当我们的输入数据s="LEET"和numRows=3时，得到结果如下图
图二 简化题目现在我们是不是只需要面对这一组数据即可。numRows=3可以拆，numRows=10也可以拆分。这个就不多讲啦，都是一样的。
好的，那么s="LEET"和numRows=3这个很简单,我们只需要按顺序获得 s.charAt(0),s.charAt(1),s.charAt(3),s.chatAt(2)拼接一下，就能得到答案啦
那么当numRows>3的时候呢，我们就需要引入变量来完善组的属性，以及数据一共可以分成多少组
2.变量及公式引入
numInGroup：组的最大数据个数; 公式为 2*numRows - 2
groupNums: 一共多少组; 公式为 字符串长度/numInGroup +1;
row: 当前行数
公式的解释
numInGroup: 组的每一行都是两个数据，除了第一行和最后一行。 所以一组的最大数据个数为 2*numRows - 2
groupNums:这个很好理解只要算出了numInGroup,就知道一共是几组数据了
到此为止主要的破题技巧就讲完了，建议大家使用 s="LEET"和numRows=3 去自己写一遍
while的代码，就是按行遍历，每行都跨越了所有的组，所以通过for循环遍历所有组
概念就是这些，回头再看代码应该就能明白啦
网友评论