Z字形变换

发表于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

LeetCode题目，6. Z字形变换

先看题目描述

大意就是给定一个字符串，让我们将其按 Z 字形排列，并按行输出字符串

算法和思路

找出规律按行访问

基本就是找出了规律，然后逐行添加字符即可，对于给定的行数 numRows，我们令 m = 2 * numRows - 2

  • 对于第 0 行的字符，每次从 s 中的第 0 个字符开始，每次都会向后位移 m 位
  • 对于第 i 行 (i < numRows - 1) 的字符，令 offset 1 = (numRows - 1 - i) * 2，offset 2 = m - offset1，每次都会从 s 中的第 i 个字符开始，先向后位移 offset1位，再位移 offset2 位
  • 对于第 numRos - 1 行的字符，每次从 s 中的第 numRos - 1 个字符开始，每次都会向后位移 m 位

按行排序

设 numRows 行字符串分别为 $S_1，S_2，S_3，…，S_n$，则容易发现：按顺序遍历字符串 s 时，每个字符 c 在 Z 字形中对应的行索引先从 $S_1$增大至 $S_n$，再从 $S_n$ 减小至 $S_1$，如此反复

按顺序遍历字符串 s:

  • res[i].append(c)：把每个字符 c 填入对应行 $S_i$
  • i += flag：更新当前字符 c 对应的行索引
  • flag = -flag，在达到 Z 字形转折点时，执行 反向

算法源码

找出规律按行访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        int len = s.length();
        StringBuilder res = new StringBuilder();
        int m = 2 * numRows - 2;
        int index = 0;
        while (index < len) {
            res.append(s.charAt(index));
            index += m;
        }
        for (int i = 1; i < numRows - 1; i++) {
            index = i;
            int offset1 = (numRows - 1 - i) * 2;
            int offset2 = m - offset1;
            int con = 0;
            while (index < len) {
                res.append(s.charAt(index));
                if (con % 2 == 0) index += offset1;
                else index += offset2;
                con++;
            }
        }
        index = numRows - 1;
        while (index < len) {
            res.append(s.charAt(index));
            index += m;
        }
        return res.toString();
    }
}

按行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

class Solution {
    public String convert(String s, int numRows) {
        if (numRows <= 1) return s;
        StringBuilder res = new StringBuilder();
        List<StringBuilder> strs = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            strs.add(new StringBuilder());
        }
        int row = 0;
        int flag = -1;
        for (char c: s.toCharArray()) {
            strs.get(row).append(c);
            if (row == 0 || row == numRows - 1) flag = -flag;
            row += flag;
        }
        for (StringBuilder str: strs) {
            res.append(str);
        }
        return res.toString();
    }
}