LEETCODE 6. ZigZag Conversion 解题思路分析

题目大意：

Z 字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=6

解题思路分析：

题目给出了行数，然后我们在规定的行数内蛇形打印字符串，那么字符串上的每个字符应该按顺序显示在第1, 2, 3…n-1, n, n-1 …2, 1, 2…行上。我们建立一个数组arr[]，数组长度为行数，arr[i]代表第i行上的所有字符。我们从字符串的第0位开始向后循环，另外我们需要定义一个变量代表当前行数，初始为0，每循环一个字符，将当前字符加到arr数组相应的行中，同时行数加一，当行数到达最大行数时，接下来的循环中行数减一，直到行数为0时，再变回加一操作。直到字符串结束。

实现代码：

public String convert(String s, int numRows) {
    // 如果行数为1，直接返回s
    if(numRows==1) return s;
    // 数组，sb[i]代表第i行上的所有字符
    StringBuilder[] sb = new StringBuilder[numRows];
    // 当前行数
    int row=0;
    // 行数变化规则，1为加一行，-1为减一行
    int diff=1;
    // 循环字符串每个字符
    for(int i=0;i<s.length();i++){
        // 如果数组中当前行的对象为空，初始化StringBuilder
        if(sb[row]==null) sb[row]=new StringBuilder();
        // 将当前字符加入到当前行中
        sb[row].append(s.charAt(i));
        // 如果行数到达最大行或者是最小行时，改变行数变化规则。
        if(row==numRows-1 || row==0&&i!=0){
            diff*=-1;
        } 
        // 行数加一（或减一）
        row+=diff;
    }
    // 返回结果
    StringBuilder res=new StringBuilder();
    // 将数组中每一行的字符串连接起来即是结果
    for(int i=0;i<numRows;i++){
        if(sb[i]==null) continue;
        res.append(sb[i]);
    }
    return res.toString();
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 77.44% of Java online submissions for ZigZag Conversion.

Memory Usage: 41.4 MB, less than 22.34% of Java online submissions for ZigZag Conversion.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-6-zigzag-conversion-解题思路分析/