Leetcode之6-Z字形变换(ZigZag Conversi

前言

个人网站

公众号: 北京程序猿, 网站 : https://yaml.vip

算法

题干

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

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

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

之后，你的输出需要从左往右逐行读取，比如："LCIRETOESIIGEDHN"。

示例

示例 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

解法

1. 字符串s从上到下从左至右进行Z字形变换, 在这个过程当中会重复操作某种图案进行Z字变换。示例1和示例2中, 图案形状见下方。OK, 那么问题来了, 图案节点个数step到底是多少? 图案纵向长度是numRows, 右斜方向长度是numRows-1, 但是纵向和右斜有一个节点重复, 那么step=numRows+(numRows-1)-1=2*numRows-2。第一行和最后一行, 节点x(比如示例1第一行的L节点)和下一节点y(比如示例1第一行的C节点)的索引差值是step, 我们可以单独处理。在处于图案中的中间行, 节点x(比如示例1第二行E节点)和下一节点y(比如示例1第二行T节点)的索引差值是(step-2乘以当前行数)。基于这个规律我们进行代码的编写。

示例1重复图案:
L
E T
E
示例2重复图案:
L
E   O
E C
T

2. 解法2之前没想到, 后来在网上偶然看到。其实这个解法应该比解法1更易于想到。去除其他边界case，Z字形变换后的字符串的行数肯定是numRows, 在迭代字符串s过程中, 我们需要考虑的唯一问题是如何控制字符向下还是向上从而保证字符保存在合适的行。具体可参考LeetCode 题解 | 6. Z字形变换。

解法1 Java代码

public String convert(String s, int numRows) {
    if (s == null || s.length() <= 0 
                  || numRows <= 1 
                  || s.length() <= numRows){
        return s;
    }
    final int step = 2 * numRows - 2;
    final int length = s.length();
    StringBuilder builder = new StringBuilder(length);
    for (int i = 0; i < length; i+=step) {
        builder.append(s.charAt(i));
    }
    for (int i = 1; i < numRows - 1; i++) {
        int startIndex = i;
        while (startIndex < length) {
            builder.append(s.charAt(startIndex));
            int neighbourIndex = startIndex + step - 2 * i;
            if (neighbourIndex < length) {
                builder.append(s.charAt(neighbourIndex));
            }
            startIndex += step;
        }
    }
    for(int i = numRows - 1; i < length; i+=step) {
        builder.append(s.charAt(i));
    }
    return builder.toString();
}

代码解析

1. 第2-6行代码主要是考虑极端case,有些case直接返回也能在特定场景下提升效率。
2. 第7行代码step变量表示重复图案的节点个数, 这个step值用于后续循环。
3. 第10-12行代码用于记录Z字形变换之后的第一行字母列表。
4. 第15-22行代码用于记录非第一行和最后一行的字母列表, 跳转间隔是step值。
5. 第17行代码neighbourIndex表示每次循环下右边节点的索引值。
6. 第24-26行代码用于记录Z字形变换之后的最后一行字母列表。

解法2 Java代码

public String convert(String s, int numRows) {
    if (s == null || s.equals("") 
                  || numRows <= 1 
                  || s.length() <= numRows){
        return s;
    }
    List<StringBuilder> rows = new ArrayList<>(16);
    for (int startRow = 0; startRow < numRows; startRow++) {
        rows.add(new StringBuilder());
    }
    boolean goDown = false;
    int curRow = 0;
    for (char val : s.toCharArray()) {
        rows.get(curRow).append(val);
        if (curRow == 0 || curRow == numRows - 1) {
            goDown = !goDown;
        }
        curRow += goDown ? 1 : -1;
    }
    StringBuilder result = new StringBuilder(s.length());
    for (StringBuilder temp : rows) {
        result.append(temp);
    }
    return result.toString();
}

代码解析

1. 第2-6行代码用于鲁棒性检查。
2. 第7-10行代码用于初始化每行用于存储字母列表的StringBuilder。
3. 第11行代码变量goDown表示Z字形变换是向下还是斜向上。
4. 第12行代码变量curRow表示当前行的索引值。
5. 第13-18行代码用于迭代字符串s, 将字符存储在对应的行StringBuilder中。
6. 第15-17行代码表示在第一行和最后一行进行方向的转换。
7. 第18行表示如何进行行号的控制, 如果方向向下, 行号自增;反之自减。

本文著作权归作者所有。

商业转载请联系作者获得授权，非商业转载请于文首标明作者姓名，保持文章完整性，并附上出处和文章链接！未按规范转载者，作者保留追究相应责任的权利！

作者：北京程序猿

链接：Leetcode之6-Z字形变换(ZigZag Conversion)