漫畫：騰訊面試題（一文讀懂 Z 字形變換）
今天是小浩算法“365刷題計(jì)劃”第81天。為大家分享一道讓很多人頭疼過的題目 - Z字形變化。
額。。。不知道是不是我瞎，明明是N么（杠精勿擾，只是說說）
第6題：將一個(gè)給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進(jìn)行 Z 字形排列。比如輸入字符串為 "LEETCODEISHIRING" 行數(shù)為 3 時(shí)，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個(gè)新的字符串，比如："LCIRETOESIIGEDHN"。
請(qǐng)你實(shí)現(xiàn)這個(gè)將字符串進(jìn)行指定行數(shù)變換的函數(shù)：
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
這是我比較推崇的一道“小學(xué)題目”，因?yàn)槠錄]有任何復(fù)雜的思維邏輯，只需要按部就班，就可以順利解答。難的是，按部就班的過程里，卻極其容易出錯(cuò)。。
因?yàn)樽罱K目的是變換字符串的順序，并且題中也沒有限制說不可用額外空間，所以我們秉承不重復(fù)造輪子的原則，想辦法利用某種結(jié)構(gòu)對(duì)原字符串做文章。
假若我們采用示例2的數(shù)據(jù)來進(jìn)行分析，輸入字符串 s 為 "LEETCODEISHIRING"， numRows 為 4 ，畫成圖大概長(zhǎng)這樣：
重點(diǎn)來了，我們的目標(biāo)是按行打印，那總得有個(gè)東西來存儲(chǔ)每行的數(shù)據(jù)吧？因?yàn)橹恍枰鎯?chǔ)每行的數(shù)據(jù)，那是不是用個(gè)數(shù)組就可以了。（當(dāng)然，你硬說搞個(gè)map來存也沒啥毛病，就是有點(diǎn)閑得蛋疼）
問題來了，那數(shù)組設(shè)置多大呢？自然是有多少行我們就設(shè)置多大唄，換句話說，numRows多大，我們的數(shù)組就設(shè)置多大。畫成圖大概就是下面這個(gè)樣子：
存儲(chǔ)的容器有了，原字符串也列出來是啥樣了，現(xiàn)在嘎哈？自然就是把原字符串放到容器里咯。怎么放？根據(jù) numRows 的大小來回進(jìn)行放置即可（即從0到n-1，再?gòu)膎-1到0）。啥意思：
（不需要我再繼續(xù)畫下去了吧）
上面的圖長(zhǎng)得不得了，但是觀察我們能看出來，每 2n-2 即為一個(gè)周期。到了這里，應(yīng)該沒有人會(huì)質(zhì)疑這是一道小學(xué)題目了吧。。。把所有的字符串放完之后，大概就是下面這個(gè)樣子：
最后一步，咱們讓這個(gè)數(shù)組排排坐，就可以開始吃果果：
如果看不清楚，不如這樣：
根據(jù)分析，得出代碼（好久沒翻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}
上面的代碼要強(qiáng)調(diào)兩點(diǎn)：
第一：用了一個(gè)rune，這個(gè)其實(shí)是go里的用法，用來處理unicode或utf-8字符而已，并沒有什么特別的。
第二：12-15行的意思是，在周期內(nèi)，正著走 numRows-1 下，剩余的反著走。（也就是上面那個(gè)長(zhǎng)長(zhǎng)的圖）
為了照顧Java的小伙伴，再給出一個(gè)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語(yǔ)言的示例一樣，代碼的關(guān)鍵仍然是計(jì)算軌跡的過程（10-17），這里再提供另外一種計(jì)算軌跡的方式：
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}
通過使用一個(gè)標(biāo)志位，來使軌跡回移。（本質(zhì)其實(shí)是一樣的）
鄭重申明（讀我的文章必看）：
本系列所有教程都不會(huì)用到復(fù)雜的語(yǔ)言特性，大家無須擔(dān)心沒有學(xué)過相關(guān)語(yǔ)法，算法思想才是最重要的！
作為學(xué)術(shù)文章，雖然風(fēng)格可以風(fēng)趣，但嚴(yán)謹(jǐn)，我是認(rèn)真的。本文所有代碼均在leetcode進(jìn)行過測(cè)試運(yùn)行。
這道題目的意義在于考察coding的能力，本身的思維過程并不復(fù)雜。有的同學(xué)一看這種題目，就想通過二維數(shù)組來進(jìn)行計(jì)算，殊不知已經(jīng)落入了題目的陷阱（不信你試試，二維數(shù)組出錯(cuò)率一定遠(yuǎn)勝一維數(shù)組）。當(dāng)然，本題也是可以不借助額外空間來進(jìn)行實(shí)現(xiàn)的，核心的邏輯完全相同，建議大家下去自己動(dòng)手練習(xí)一下。
今天的題目到這里就結(jié)束了，如果想看其他面試題相關(guān)內(nèi)容的，可以看：
漫畫：知乎面試題（旋轉(zhuǎn)數(shù)組最小值Ⅰ - 基礎(chǔ)版）
漫畫：知乎面試題（旋轉(zhuǎn)數(shù)組最小值Ⅱ - 進(jìn)階版）
漫畫：美團(tuán)面試題（TOPK：求第K個(gè)最大的元素）
漫畫：騰訊面試題（面試官問我會(huì)不會(huì)修供暖器，我說沒問題）
如果你問我對(duì)學(xué)習(xí)算法有什么建議，這篇文章是必看的：
漫畫：嘔心泣血算法指導(dǎo)篇（真正的干貨，怒懟那些說算法沒用的人）
小浩算法，每日一題
關(guān)注領(lǐng)取《圖解算法》高清版
進(jìn)群的小伙伴請(qǐng)加右側(cè)私人微信（備注：進(jìn)群）
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
