漫画：腾讯面试题（一文读懂 Z 字形变换）

时间：2020-05-07 01:01:16

关键字：腾讯 BSP 字符串 RIO

手机看文章

扫描二维码
随时随地手机看文章

[导读]今天是小浩算法“365刷题计划”第81天。为大家分享一道让很多人头疼过的题目 - Z字形变化。 01 PART Z 字形变换额。。。不知道是不是我瞎，明明是N么（杠精勿扰，只是说说）第6题：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

今天是小浩算法“365刷题计划”第81天。为大家分享一道让很多人头疼过的题目 - Z字形变化。

PART

Z 字形变换

额。。。不知道是不是我瞎，明明是N么（杠精勿扰，只是说说）

第6题：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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

PART

题目分析

这是我比较推崇的一道“小学题目”，因为其没有任何复杂的思维逻辑，只需要按部就班，就可以顺利解答。难的是，按部就班的过程里，却极其容易出错。。

因为最终目的是变换字符串的顺序，并且题中也没有限制说不可用额外空间，所以我们秉承不重复造轮子的原则，想办法利用某种结构对原字符串做文章。

假若我们采用示例2的数据来进行分析，输入字符串 s 为 "LEETCODEISHIRING"， numRows 为 4 ，画成图大概长这样：

重点来了，我们的目标是按行打印，那总得有个东西来存储每行的数据吧？因为只需要存储每行的数据，那是不是用个数组就可以了。（当然，你硬说搞个map来存也没啥毛病，就是有点闲得蛋疼）

问题来了，那数组设置多大呢？自然是有多少行我们就设置多大呗，换句话说，numRows多大，我们的数组就设置多大。画成图大概就是下面这个样子：

存储的容器有了，原字符串也列出来是啥样了，现在嘎哈？自然就是把原字符串放到容器里咯。怎么放？根据 numRows 的大小来回进行放置即可（即从0到n-1，再从n-1到0）。啥意思：

（不需要我再继续画下去了吧）

上面的图长得不得了，但是观察我们能看出来，每 2n-2 即为一个周期。到了这里，应该没有人会质疑这是一道小学题目了吧。。。把所有的字符串放完之后，大概就是下面这个样子：

最后一步，咱们让这个数组排排坐，就可以开始吃果果：

如果看不清楚，不如这样：

根据分析，得出代码（好久没翻go的牌子了）：

 1//GO
 2func convert(s string, numRows int) string {
 3    if numRows == 1{
 4        return s
 5    }
 6    var b = []rune(s)
 7    var res = make([]string, numRows)
 8    var length = len(b)
 9    var period = numRows * 2 - 2
10    for i := 0 ;i < length; i ++ {
11        var mod = i % period
12        if mod < numRows {
13            res[mod] += string(b[i])
14        } else {
15            res[period - mod] += string(b[i])
16        }
17    }
18    return strings.Join(res, "")
19}

上面的代码要强调两点：
第一：用了一个rune，这个其实是go里的用法，用来处理unicode或utf-8字符而已，并没有什么特别的。

第二：12-15行的意思是，在周期内，正着走 numRows-1 下，剩余的反着走。（也就是上面那个长长的图）

为了照顾Java的小伙伴，再给出一个Java版本的：

 1//java
 2class Solution {
 3    public static String convert(String s, int numRows) {
 4        if (numRows == 1) return s;
 5        String[] arr = new String[numRows];
 6        Arrays.fill(arr, "");
 7        char[] chars = s.toCharArray();
 8        int len = chars.length;
 9        int period = numRows * 2 - 2;
10        for (int i = 0; i < len; i++) {
11            int mod = i % period;
12            if (mod < numRows) {
13                arr[mod] += chars[i];
14            } else {
15                arr[period - mod] += String.valueOf(chars[i]);
16            }
17        }
18        StringBuilder res = new StringBuilder();
19        for (String ch : arr) {
20            res.append(ch);
21        }
22        return res.toString();
23    }
24}

和Go语言的示例一样，代码的关键仍然是计算轨迹的过程（10-17），这里再提供另外一种计算轨迹的方式：

 1//java
 2class Solution {
 3    public String convert(String s, int numRows) {
 4        if (numRows == 1) return s;
 5        String[] arr = new String[numRows];
 6        Arrays.fill(arr, "");
 7        int i = 0, flag = -1;
 8        for (char c : s.toCharArray()) {
 9            arr[i] += c;
10            if (i == 0 || i == numRows - 1) flag = -flag;
11            i += flag;
12        }
13        StringBuilder res = new StringBuilder();
14        for (String ch : arr) {
15            res.append(ch);
16        }
17        return res.toString();
18    }
19}