6. ZigZag Conversion

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)

image.png

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"

Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

image.png

題目大意：

??給定一個字符串s與數(shù)字numRows，將s進(jìn)行之字形的numRows排列后，將它們逐行重組并輸出苍糠。

解題思路：

??沒什么算法受楼，就是看圖找規(guī)律涣旨。

image.png

??可以看出字符串按之字形排列的時候會有一個周期晚缩，當(dāng)numRows=3時愈案，4個字符為一個周期银萍；當(dāng)numRows=4時，6個字符為一個周期肥隆；當(dāng)numRows=5時既荚，8個字符為一個周期，可以歸納出周期cycle=2*numRows-2栋艳。
??其實(shí)也可以由圖像觀察得出恰聘，把每一個周期中間的字符歸到一列可以看出其實(shí)就是兩列字符再去掉第一行和第二行而已，推斷不難。
??找出周期概念就簡單了晴叨，逐行輸出凿宾，頭尾兩行就是首字符加上周期即可，中間每行再另作觀察兼蕊。
??觀察得出每行的[n, n+1]（n>=1)個周期之間的字符與n+1個周期的第一個字符(下標(biāo)為j)總是相差j-2*(當(dāng)前行在中間行數(shù)的序號)初厚，輸出即可，有點(diǎn)拗口孙技，可以寫下當(dāng)numRows=5時的字符排列觀察一下产禾。

解題代碼：

class Solution {
public:
    string convert(string s, int numRows)
    {
        if (numRows < 2) return s;
        string res;
        int cycle = 2 * numRows - 2, flag = 0, count = 0, second, size = s.size();
        for (int i = 0; i < numRows;++i)
        {
            for (int j = i; j < size; j = j + cycle)
            {
                res = res + s[j];
                second = j + cycle - 2 * i;
                if (i != 0 && i != numRows - 1 && second < size)
                    res = res + s[second];
            }
        }
        return res;
    }
};

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者