凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 6. ZigZag Conversion

分类:algorithm| 发布时间:2016-06-27 00:28:00


题目

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".

题意

给出一个 nRows 的 zigzag 模式写的字符串,将其展开并将结果返回。

解法1

这道题的难点在于要理解什么是 zigzag pattern。 题目没有解释地很清楚,下面给出比较好理解的图:

可以通过这张图得到第一行和最后一行两个字符之间间隔了 2 * (nRows - 1) 个字符。 其他的行每两个字符相隔 2 * (nRows - 1) - 2 * i,2 * i( i 为 0-base 的行号)。 另外还需要注意的就是 nRows 为 1 时,直接返回给出的字符串就行了。

class Solution {
public:
    string convert(string s, int numRows) {
        const int size = s.size();
        if (numRows == 1) {
            return s;
        }

        int distance, distance2;
        string ret;
        for (int i = 0; i < numRows; ++i) {
            distance = 2 * (numRows - 1);
            distance2 = i ? distance - (2 * i) : 0;

            for (int j = i; j < size; j += distance) {
                ret.push_back(s[j]);
                if (distance2 && j + distance2 < size) {
                    ret.push_back(s[j + distance2]);
                }
            }
        }

        return ret;
    }
};