題目

將字符串 "PAYPALISHIRING"以Z字形排列成給定的行數(shù)：

P   A   H   N
A P L S I I G
Y   I   R

之后從左往右泉瞻，逐行讀取字符："PAHNAPLSIIGYIR"

實(shí)現(xiàn)一個(gè)將字符串進(jìn)行指定行數(shù)變換的函數(shù):

string convert(string s, int numRows);
示例 1:

輸入: s = "PAYPALISHIRING", numRows = 3
輸出: "PAHNAPLSIIGYIR"
示例 2:

輸入: s = "PAYPALISHIRING", numRows = 4
輸出: "PINALSIGYAHRPI"
解釋:

P     I    N
A   L S  I G
Y A   H R
P     I

分析

這道題乍一看有點(diǎn)難杈绸，其實(shí)很簡(jiǎn)單撩幽，通過率也是高達(dá)30%柑潦，單純總結(jié)規(guī)律就能解答~~

• 想法一：第一次的想法是每個(gè)V型為一組，然后根據(jù)組來計(jì)算每一行的個(gè)數(shù)進(jìn)而計(jì)算出每一行中每個(gè)字符的下標(biāo)夫凸。
  后來被我否定了秦叛，明明之中覺得復(fù)雜度偏高。
• 想法二：直接一行一行來算數(shù)組下標(biāo)答恶。
  通過分析我們不難發(fā)現(xiàn)下標(biāo)規(guī)律：
• 行數(shù)為四的時(shí)候：
  • 第一行：0 - 6 - 12 - 18 ... //步長(zhǎng)6 6 6
  • 第二行：1 - 5 - 7 - 11 - 13 ... //步長(zhǎng)4 2 4 2
  • 第三行：2 - 4 - 8 - 10 - 14 ... //步長(zhǎng)2 4 2 4
  • 第四行：3 - 9 - 15 - 21 ... //步長(zhǎng)6 6 6

規(guī)律顯而易見饺蚊，當(dāng)然讀者可以自己多試試其他的例子來驗(yàn)證。其實(shí)根據(jù)"Z"字的特點(diǎn)我們也能直接分析出這樣的規(guī)律悬嗓。接下來就是將規(guī)律函數(shù)化污呼。

1. 步長(zhǎng)：上述例子中 無論是6 還是4，2交替還是2包竹，4交替燕酷，都是和6相關(guān)的。那么6又是怎么和層數(shù)關(guān)聯(lián)呢周瞎？根據(jù)圖形"Z"來分析苗缩，每加1層就會(huì)增加2步長(zhǎng)，那么步長(zhǎng)即為總層數(shù)*2-2声诸，后文稱之為絕對(duì)步長(zhǎng)酱讶。
2. 根據(jù)步長(zhǎng)我們能很快計(jì)算第一層的所有下標(biāo)。那第二層 第n層呢彼乌。第二層其實(shí)就是步長(zhǎng)-2泻肯，2交替渊迁，第三層是步長(zhǎng)步長(zhǎng)-4,4交替。
   提煉公式：步長(zhǎng)- 2*(層數(shù)-1),2*(層數(shù)-1)交替灶挟。
   當(dāng)然宫纬，最后一層和第一層步長(zhǎng)一直都是絕對(duì)步長(zhǎng)。
   接下來就是編碼

    public String convert(String s, int numRows) {
        char[] c = new char[s.length()];
        int size = numRows * 2 - 2; //絕對(duì)步長(zhǎng)
        int index; //記算s下標(biāo)
        int count = 0; //記錄c下標(biāo)
        int add; //相對(duì)步長(zhǎng)
        if (numRows < 2) {
            return s;
        }
        for (int i = 0; i < numRows; i++) { //一層一層遍歷
            index = i;
            add = i * 2;
            while (index < c.length) { //超出字符串長(zhǎng)度計(jì)算下一層
                c[count] = s.charAt(index);
                add = size - add;
                index += add == 0 ? size : add;
                count++;
            }
        }
        return new String(c);
    }

運(yùn)行很輕松就通過啦~~

比較

還是老規(guī)矩膏萧，拷貝速度排行第一的算法進(jìn)行比較

    public String convert1(String s, int numRows) {
        if(numRows < 2) {
            return s;
        }
        StringBuilder result = new StringBuilder();
        int group = 2 * numRows - 2;
        for(int i = 1; i <= numRows; i ++) {
            int interval = 2 * numRows - 2 * i;
            if(i == numRows) {
                interval = 2 * numRows - 2;
            }
            int index = i;
            while(index <= s.length()) {
                result.append(s.charAt(index - 1));
                index += interval;
                interval = group - interval;
                if(interval == 0) {
                    interval = group;
                }
            }
        }
        return result.toString();
    }

單純從代碼上看，感覺應(yīng)該不是算法王者的代碼蝌衔，很多優(yōu)化點(diǎn)榛泛，最明顯的就是StringBuilder構(gòu)造時(shí)候應(yīng)該傳入s長(zhǎng)度，不然默認(rèn)容量是16噩斟，然后字符串過長(zhǎng)的時(shí)候會(huì)不斷出發(fā)擴(kuò)容方法曹锨，調(diào)用多次Arrays.copy，上一篇的王者好像也是調(diào)用了多測(cè)Arrays.copy... 寫道這里我有點(diǎn)懷疑自己從前的認(rèn)知剃允。沛简。。從邏輯上看和我的邏輯有很多相似之處~~
好我們來跑一下代碼看一下時(shí)間差：
字符串為隨機(jī)字符串斥废。

測(cè)試1

測(cè)試2

嗯 果然leedcode測(cè)試用例不夠極端哈哈哈哈椒楣。然后我們稍微改進(jìn)一下王者的代碼。只修改StringBuilder容量那部分牡肉。

改進(jìn)