从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行中的所有字符，然后….

其规律如下：

1. 第0行的字符位于k(2numRows-2)的位置。

2. 最后一行(numRows-1)的字符位于k(2numRows-2)+numRows-1的位置。

3. 第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();
    }

结尾

确实是有点菜，这道题虽然知道思路，但是把代码写处理还是做了挺久的。之后也参考了别人的做法，那个简化版的代码就是参考别人的。

其实我想说，不要觉得自己知道思路就可以了，一定要把代码打一遍。

关注公我的众号：苦逼的码农，获取更多原创文章，后台回复礼包送你一份特别的资源大礼包。同时也感谢把文章介绍给更多需要的人

老铁们赶紧点赞关注一波，thanks