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

作者: adminmane | 来源:发表于2020-05-25 16:08 被阅读0次

Z 字形变换

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

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

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

L   C   I   RE T O E S I I GE   D   H   N

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

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

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

输出: "LCIRETOESIIGEDHN"

示例 2：

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

输出: "LDREOEIIECIHNTSG"

L     D     RE   O E   I IE C   I H   NT     S     G

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

02

题目分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根据分析，得出代码（好久没翻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 - 210    for i := 0 ;i < length; i ++ {11        var mod = i % period12        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}

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

上面的代码要强调两点：第一：用了一个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}

通过使用一个标志位，来使轨迹回移。（本质其实是一样的）