ZigZag Conversion（ZigZag轉(zhuǎn)換）

1、題目描述：

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P ?? ?A ???H ? ? ?N
A ?P ? L? S? I? ?I ? G
Y ??? I ??? R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);
Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

? ?給出一個指定字符串和numRows，把字符串按倒Z的形式排列，行數(shù)為numRows，按行排列返回字符串。

2、解決方法1：按行分類(Java實(shí)現(xiàn))

? ?仔細(xì)觀察這個Z型的圖形，它是由nomRows行子串構(gòu)成。所以可以遍歷整個字符串把字符依次添加到指定行字符串上，方向?yàn)橄认潞笊稀?/p>

public String convert(String s, int numRows) {

        //numRows為1，直接返回s
        if (numRows==1){
            return s;
        }

        //構(gòu)建Math.min(numRows, s.length())個字符串(字符串的長度小于numRows，集合長度取s.length)，
        // 放在集合中。也可以使用字符串?dāng)?shù)組實(shí)現(xiàn)。
        //使用StringBuilder可以使字符串拼接更快。
        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++) {
            StringBuilder stringBuilder = new StringBuilder();
            rows.add(stringBuilder);
        }

        int curRow = 0;             //當(dāng)前行
        boolean dir = false;        //當(dāng)前方向     true向下 false向上  

        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);

            //第一行或最后一行時，換方向
            if (curRow ==0 || curRow ==numRows -1 ){
                dir  = ! dir;
            }
            
            //換行
            curRow += dir ? 1 : -1;
        }

        //拼接字符串集合
        StringBuilder str = new StringBuilder();
        for (StringBuilder sb : rows) {
            str.append(sb);
        }

        return str.toString();
    }

運(yùn)行耗時：53ms

運(yùn)行耗時

時間復(fù)雜度：O(n) 遍歷字符串的長度為len(s)。
空間復(fù)雜度：O(n) 存儲了len(s)的字符。

解決方法2：按行訪問(C語言實(shí)現(xiàn))

原理：找到每一行中的字符在字符串中的出現(xiàn)位置。

image.png

? ?仔細(xì)觀察第一行中P和A中間距中間相隔3個子串，實(shí)際下標(biāo)相差4。在圖上看的話其實(shí)是相差一列加一條對角線，所以第一行的字符位置可以表示為k*(2 * numRows - 2) ，k為字符在一行字符串中所處的位置。最后一行的字符位置可以用第一行加numRows-1表示，所以可以表示為k*(2 * numRows - 2) - numRows -1。中間的字符包含兩個部分，分別是 k*(numRows -2) + i 和 （k+1)*(numRows -2) - i。

char *convert_2(char *s, int numRows) {

    if (numRows == 1) {
        return s;
    }

    int length = strlen(s);
    int cycleLen = 2 * numRows - 2;

    //長度比原字符串多1，有個'\0'
    char *ret = (char *) malloc(sizeof(char) * (length + 1));
    int index = 0;

    for (int i = 0; i < numRows; ++i) {
        for (int j = 0; j + i < length; j += cycleLen) {
            //第一行、最后一行和中間行的列部分
            ret[index++] = s[j + i];
            //中間行字符串的對角線部分
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < length) {
                ret[index++] = s[j + cycleLen - i];
            }
        }
    }
    ret[index] = '\0';
    return ret;
}

運(yùn)行耗時：12ms

運(yùn)行耗時

時間復(fù)雜度：O(n) 把所有字符的下標(biāo)遍歷了一遍。
空間復(fù)雜度：O(n) 分配指針len(s)+1個空間。