首页 > 代码库 > leetcode | ZigZag Conversion

leetcode | ZigZag Conversion

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)

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 text, int nRows);
convert(“PAYPALISHIRING“, 3) should return “PAHNAPLSIIGYIR“.


将字符串按之字形排列,然后按行输出。
本题的关键点在于找出每一行两个元素之间的间隔,通过绘图找规律


技术分享

如上图所看到的。4行,第一行和最后一行两个元素之间的下标之差是k = 2*numRows-2; 其它的i行是。第一次间隔2*i,第二次则是k-2*i,然后交替进行,直到索引超出数组。

class Solution {
public:
    string convert(string s, int numRows) {
    int size = s.size();
    if (size == 0 || numRows <= 1)
        return s;
    string result;
    int k = 2 * (numRows - 1); // 最大间隔
    int t = 0; //标记奇偶
    for (int i = 0; i < numRows; i++) {
        t = 0;
        for (int j = i; j < size;) {
            result.push_back(s[j]);
            if (i == 0 || i == numRows - 1)
                j += k;
            else if (t%2 == 0) // 第偶数次
                j += (k - 2 * i);
            else if (t%2 == 1) // 第奇数次
                j += (2 * i);
            t++;
        }
    }
    return result;

}
};
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

leetcode | ZigZag Conversion