从0打卡leetcode之day7--Z字形变换
前言
好久没打卡了，虽然自己有看题，不过最近在忙其他事，没什么时间写出来。马上就要开学了，开学了可能反而会更有时间来刷题吧。可以在上课的时间段来写，，哈哈。毕竟很少听课。
题目描述
将给定的字符串 例如”PAYPALISHIRING” 以Z字形排列成给定的行数
P A H N
A P L S I I G
Y I R之后从左往右，逐行读取字符：”PAHNAPLSIIGYIR”
实现一个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);示例1
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"实例2
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
解释:
P I N
A L S I G
Y A H R
P I解题
好吧，我刚开始看的时候居然没有理解它要我干嘛，看给的那些例子的字符排序好像不像是Z字形啊，琢磨了一会才知道是把Z旋转90度之后的那种排序，如图
方法1
对于这道题想必最直接的做法就是根据题目给的行数numRows，然后我们创建numRows个数组来进行遍历保存了，然后再把他们拼接起来。
不过这里有个需要注意的地方，就是假如总字符个数为3，然后行数为5，这时候字符个数小于行数，那我们创建数组的时候创建3个就可以了，而不需要创建5个。代码如下
public String convert(String s, int numRows) {
//如果只有一行的话，直接返回
if (s==null || s.length() <= 1 || numRows == 1)
return s;
//需要创建的数组个数
int nums = Math.min(numRows, s.length());
//用StringBuilder来充当数组方便一点
StringBuilder[] rows = new StringBuilder[nums];
for(int i = 0; i < nums; i++){
rows[i] = new StringBuilder();
}
//表示是向下移动还是向上移动
boolean flag = false;
//当前遍历的行数
int curRow = 0;
for(int i = 0; i < s.length(); i++){
rows[curRow].append(s.charAt(i));
//第一行或者最后一行
if(curRow == 0 || curRow == numRows - 1)
flag = !flag;
curRow += flag ? 1 : -1;
}
//全部拼接起来
for(int i = 1; i < nums; i++){
rows[0].append(rows[i].toString());
}
return rows[0].toString();
}代码中有一个技巧，就是使用一个变量flag来记录在这个Z字形中，字符是向上移动还是向下移动，时间复杂度是O(n)。
方法2
方法2我是通过在一行之中，找出相邻两个字符之间距离的规律。也就是说，通过规律先找出第0行中的所有字符，然后找出第1行中的所有字符，然后….
其规律如下：
- 第0行的字符位于k(2numRows-2)的位置。
- 最后一行(numRows-1)的字符位于k(2numRows-2)+numRows-1的位置。
- 第0行和最后一行之间第i行的字符位于k(2numRows−2)+i 以及 (k+1)(2*numRows-2)- i处。
代码如下：
public String convert1(String s, int numRows) {
if (s==null || s.length() <= 1 || numRows == 1)
return s;
//每次都会用到2*numRows-2，所以用一个变量保存起来
int temp = 2*numRows - 2;
StringBuilder str = new StringBuilder();
for(int i = 0; i < numRows; i++){
//第0行
if(i == 0){
for(int k = 0; k * temp < s.length(); k++){
str.append(s.charAt(k*temp));
}
}
//第numRows-1行
else if(i == numRows -1){
for(int k = 0; k*temp+numRows-1 < s.length();k++){
str.append(s.charAt(k*temp+numRows-1));
}
}
//其他行
else{
for(int k = 0; k*temp+i < s.length(); k++){
str.append(s.charAt(k*temp+i));
if((k+1)*temp -i < s.length()){
str.append(s.charAt((k+1)*temp - i));
}
}
}
}
return str.toString();
}这种方法时间复杂度也是O(n)。
代码简化版：
public String convert2(String s, int numRows) {
if (s==null || s.length() <= 1 || numRows == 1)
return s;
int temp = 2*numRows - 2;
StringBuilder str = new StringBuilder();
for(int i = 0; i < numRows; i++){
//此时的k相当于上面的k*temp
for(int k = 0; k + i < s.length(); k += temp){
//本来弄了很多注释，后来全删了，感觉还是不要弄注释了吧
//假如不理解的话可以找几个字符串自己模拟想象下
str.append(s.charAt(k+i));
//如果是中间行则需要再加上一个字符
if(i != 0 && i != numRows-1 && k + temp - i < s.length()){
str.append(s.charAt(k+temp-i));
}
}
}
return str.toString();
}结尾
确实是有点菜，这道题虽然知道思路，但是把代码写处理还是做了挺久的。之后也参考了别人的做法，那个简化版的代码就是参考别人的。
其实我想说，不要觉得自己知道思路就可以了，一定要把代码打一遍。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-08-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录