作者 ： XiaXinyu
日期 ：2021-09-26

题目

理解

将给定的字符串按指定行数进行Z字形(是竖过来的z字形)排列，然后将排列后字符串按行从左到右进行输出

题解1(模拟)

通过遍历字符串s，将字符串的每个字符写入相应行中，因为字符串长度和给定行数均已知，我们可以根据这两个变量得出排列后的z字形字符串行数len = min(s.length(), numRows)

然后我们模拟z字形字符串的形成过程，初始化rows列表数组存储每行字符串(rows的长度为len)，goingDown记录方向，根据这两个变量我们就可以在遍历过程中轻松将字符串中s的字符写入相应位置

在遍历过程中，如果遍历到上端或下端就改变方向

代码

class Solution{
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        List<StringBuilder> rows = new ArrayList<>();
        for(int i = 0;i < Math.min(s.length(),numRows);i ++)
            rows.add(new StringBuilder());
        int curRow = 0;   //对行数进行追踪
        boolean goingDown = false; //确定方向

        for(char c : s.toCharArray()){
            rows.get(curRow).append(c); //将字符写入指定行
            if(curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; //遍历到两端改变方向
            curRow += goingDown ? 1 : -1;
        }

        StringBuilder result = new StringBuilder();
        for(StringBuilder row : rows) result.append(row); //可直接将StringBuilder对象加入result中
        return result.toString();
    }
}

时间复杂度 ：O(n)遍历字符串

空间复杂度 ：O(n)存储字符串花费空间

题解2(找规律)

通过观察样例结果可以发现，z字形排序后的字符串是存在周期的，period = numRows * 2 - 2

通过周期，同样可以将字符串s中每个字符写入指定行

写入指定行这里分两种情况

• 1.当前字符下标为i，若i % period 小于 numRows 则写入第i行
• 2.若i % period 不小于 numRows 就写入period - mod行

通过模拟样例可以验证这种做法的正确性

代码

class Solution {
    public String convert(String s, int numRows) {

        if(numRows == 1)    return s;

        String[] ss = new String[numRows];
        Arrays.fill(ss,"");
        int period = numRows * 2 - 2;
        for(int i = 0;i < s.length();i ++){
            int mod = i % period;
            if(mod < numRows){
                ss[mod] += s.charAt(i);
            }
            else{
                ss[period - mod] += s.charAt(i);
            }
        }

        StringBuilder result = new StringBuilder();
        for(String substring : ss){
            result.append(substring);
        }

        return result.toString();

    }
}

时间复杂度 ：O(n)遍历字符串

空间复杂度 ：O(n)存储字符串花费空间