leetcode题目6：Z 字形变换（java）

题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

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

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

示例

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

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

解题思路一

遍历字符串，将每一个字符放到合适的行里。遍历字符串的同时要改变行号。

代码

public String convert_v2(String s, int numRows) {
    if (s == null || s.length() <= 1 || numRows <= 1) {
        return s;
    }
    List<StringBuilder> lists = new ArrayList<>();
    for (int i = 0; i < Math.min(s.length(), numRows); i++) {
        lists.add(new StringBuilder());
    }

    int curRow = 0;
    boolean isDown = false;
    char[] charArr = s.toCharArray();
    for (char c : charArr) {
        lists.get(curRow).append(c);
        if (curRow == 0 || curRow == numRows - 1) {
            // 遍历到第一行或最后一行的时候, 需要改变方向
            isDown = !isDown;
        }
        curRow = curRow + (isDown ? 1 : -1);
    }

    StringBuilder result = new StringBuilder();
    for (StringBuilder sb : lists) {
        result.append(sb.toString());
    }

    return result.toString();
}

解题思路二

按照与逐行读取 Z 字形图案相同的顺序访问字符串。首先访问第0行的，然后再找出第1行的，以此类推。

代码

public String convert(String s, int numRows) {
    if (s == null || s.length() <= 1 || numRows <= 1) {
        return s;
    }
    StringBuilder result = new StringBuilder();
    for (int j = 0; j < numRows; j ++) {
        // 分别输出每一行
        int k = 0;
        int curIndex = (numRows *2 - 2) * k + j; // 找到第j行第k个字符的位置
        while (curIndex < s.length()) {
            result.append(s.charAt(curIndex));
            if (j !=0 && j != numRows - 1) {
                // 非首、尾行需要找到中间的字符
                int middleIndex = curIndex + (numRows - j - 1) * 2;
                if (middleIndex < s.length()) {
                    result.append(s.charAt(middleIndex));
                }
            }
            k++;
            curIndex = (numRows *2 - 2) * k + j;
        }
    }
    return result.toString();
}