問(wèn)題

將字符串 "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ù)的轉(zhuǎn)換的函數(shù):
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) 應(yīng)當(dāng)返回 "PAHNAPLSIIGYIR" 。

思路

這個(gè)問(wèn)題其實(shí)很簡(jiǎn)單，它只涉及到下標(biāo)，你只要觀察就能看出一個(gè)時(shí)間復(fù)雜度為O(n)的算法的。它是一個(gè)個(gè)重復(fù)的波形，而整個(gè)波形都是重復(fù)了從0開始到2×row-3這一段的波形，所以現(xiàn)在我暫時(shí)先只研究[0，2×row-3]這一段，[0，row-1]是豎直的，[row，2×row-3]是左下右上斜的。其中，第0行的下一個(gè)波形的下標(biāo)與本波形同一行的相鄰的下標(biāo)相減是2×row-2-0=2×row-2。第1行本身波形與本身波形相鄰的下標(biāo)相減是2×row-3-1=2×row-4，下一個(gè)波形與本波形的相鄰的下標(biāo)相減是2，這兩個(gè)差之和是2×row-2。再下一行就是2×row-6和4之和，也是2×row-2。所以問(wèn)題的解法就出現(xiàn)了，從0到row-1進(jìn)行遍歷，現(xiàn)在正在遍歷第i行，它先走了2×row-i×2的步長(zhǎng)得到了一個(gè)字符，再走一個(gè)i×2就到了同一行下一個(gè)字符，如此往復(fù)地走直到越界為止，這一行就沒(méi)了。雖然說(shuō)循環(huán)有2層但是實(shí)際上卻只進(jìn)行了n步，所以時(shí)間復(fù)雜度是O(n)。但是對(duì)于行數(shù)只有1和行數(shù)大于等于字符串字符個(gè)數(shù)的情況，輸出的字符串都是原來(lái)的字符串，不需要處理，直接輸出就好。于是就得到了算法的實(shí)現(xiàn)。

使用

package com.company;

public class Main {

    public static void main(String[] args) {
    // write your code here
        String inputString = "PAYPALISHIRING";
        String inputString0 = "ABCDE";
        System.out.println(Solution.zigzagString0(inputString,4));
    }
}

輸出

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


Process finished with exit code 0

實(shí)現(xiàn)

package com.company;

public class Solution {
    static public String zigzagString(String sourceString,int rows) {
        if (rows < 1 || sourceString == null) {
            System.out.println("輸入非法");
            return "";
        }
        StringBuilder resultBuilder = new StringBuilder();
        for (int counter = 0;counter < rows;counter++) {
            if (rows == 1 || rows >= sourceString.length()) {
                return sourceString;
            } else {
                int stepLength = 2 * rows - 2 - 2 * counter;
                int counter0 = counter;
                while (counter0 < sourceString.length()) {
                    resultBuilder.append(sourceString.charAt(counter0));
                    if (stepLength != 2 * rows - 2 && stepLength != 0) {
                        counter0 += stepLength;
                        stepLength = 2 * rows - 2 - stepLength;
                    }
                    else if (stepLength == 0) {
                        stepLength = 2 * rows - 2;
                        counter0 += stepLength;
                    } else {
                        counter0 += stepLength;
                    }
                }
            }
        }
        return resultBuilder.toString();
    }

    /**
     * 這么做沒(méi)什么不同，只不過(guò)是把字符串打印成Z字形。
     * @param sourceString
     * @param rows
     * @return
     */
    static public String zigzagString0(String sourceString,int rows) {
        if (rows < 1 || sourceString == null) {
            System.out.println("輸入非法");
            return "";
        }
        StringBuilder resultBuilder = new StringBuilder();
        for (int counter = 0;counter < rows;counter++) {
            if (rows == 1 || rows >= sourceString.length()) {
                return sourceString;
            } else {
                int stepLength = 2 * rows - 2 - 2 * counter;
                int counter0 = counter;
                for (int counter1 = counter;counter1 < sourceString.length();counter1++) {
                    if (counter1 == counter0) {
                        System.out.print(sourceString.charAt(counter1));
                        if (stepLength != 2 * rows - 2 && stepLength != 0) {
                            counter0 += stepLength;
                            stepLength = 2 * rows - 2 - stepLength;
                        }
                        else if (stepLength == 0) {
                            stepLength = 2 * rows - 2;
                            counter0 += stepLength;
                        } else {
                            counter0 += stepLength;
                        }
                    } else {
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }
        return resultBuilder.toString();
    }
}