当前位置：首页 > article >正文

LeetCode6题：Z字形变换（原创）

article 2025/1/21 5:57:02

【题目描述】

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P   A   H   N
A P L S I I G
Y   I   R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I
示例 3：
输入：s = "A", numRows = 1
输出："A"
提示：
1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

题目链接：. - 力扣（LeetCode）

【解题代码】

package string;


public class Convert {

    public static void main(String[] args) {
        String s = "PAYPALISHIRING";
        int numRows = 3;
        String result = new Convert().convert(s, numRows);
        System.out.println("计算结果:" + result);
    }

    public String convert(String s, int numRows) {
        if (numRows == 1)
            return s;

        StringBuilder[] sbArray = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            sbArray[i] = new StringBuilder();
        }
        boolean down = true;
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            sbArray[index].append(s.charAt(i));
            index = down ? index + 1 : index - 1;
            if (index == numRows) {
                index = numRows - 2;
                down = false;
            }
            if (index == -1) {
                index = 1;
                down = true;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            sb.append(sbArray[i]);
        }
        return sb.toString();
    }

    public String convert1(String s, int numRows) {
        if (numRows == 1)
            return s;

        String[] strs = new String[numRows];
        for (int i = 0; i < numRows; i++) {
            strs[i] = "";
        }

        boolean down = true;
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            strs[index] += s.charAt(i);
            index = down ? index + 1 : index - 1;
            if (index == numRows) {
                index = numRows - 2;
                down = false;
            }
            if (index == -1) {
                index = 1;
                down = true;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            sb.append(strs[i]);
        }
        return sb.toString();
    }
}

【解题思路】

一开始拿到题目，感觉很懵，不知道这个“根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列”是啥意思，后来看了半天才理解题意：这个意思不该是“Z”字排列，而是“N”字排列，按照给定的行数，字符串从上到下然后从下到上不断地遍历，然后一行一行的输出。明白过来之后，慢慢的想出解题思路：一开始根据行数申请若干个字符串数组，然后依次遍历输入字符串并添加到相应行的字符串，先从第一行遍历到最后一行，再从最后一行遍历到第一行，周而复始，直到遍历结束，最后按照顺序输出所有行的字符串。按照这个思路很快完成代码编写，并提交成功：

执行用时分布是12MS，感觉性能差了一些，然后优化了一下代码，使用StringBuilder替代了字符串操作，再次提交代码，性能好了不少，执行用时分布降到了4MS

【解题步骤】

特殊情况处理，如果numRows为1，直接返回输入字符串s
```
if (numRows == 1)
    return s;
```

根据行数申请若干个字符串数组

StringBuilder[] sbArray = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) {
    sbArray[i] = new StringBuilder();
}

定义两个变量：字符行遍历方向down，以及当前遍历的行数索引index
```
boolean down = true;
int index = 0;
```

然后然后依次遍历输入字符串并添加到相应行的字符串，先从上往下先从第一行遍历到最后一行，再从最后一行遍历到第一行，周而复始，直到遍历结束

for (int i = 0; i < s.length(); i++) {
    sbArray[index].append(s.charAt(i));
    index = down ? index + 1 : index - 1;
    if (index == numRows) {
        index = numRows - 2;
        down = false;
    }
    if (index == -1) {
        index = 1;
        down = true;
    }
}

最后按照顺序输出所有行的字符串。

StringBuilder sb = new StringBuilder();
for (int i = 0; i < numRows; i++) {
    sb.append(sbArray[i]);
}
return sb.toString();

【思考总结】

首先得理解题意：“根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列”，这个意思不该是“Z”字排列，而是“N”字排列，按照给定的行数，字符串从上到下然后从下到上不断地遍历，然后一行一行的输出。
此题算法实现思路：一开始根据行数申请若干个字符串数组，然后依次遍历输入字符串并添加到相应行的字符串，先从第一行遍历到最后一行，再从最后一行遍历到第一行，周而复始，直到遍历结束，最后按照顺序输出所有行的字符串。
LeetCode解题之前，一定不要看题解，看了就“破功”了！

查看全文

http://www.kler.cn/a/370413.html