漫畫：騰訊面試題（一文讀懂 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）。啥意思：

（不需要我再繼續(xù)畫下去了吧）

上面的圖長得不得了，但是觀察我們能看出來，每 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}