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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。