LeetCode 6. Z字形变换

1. 题目描述

将一个给定字符串s根据给定的行数numRows，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为"PAYPALISHIRING"行数为3时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"

解释：

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

示例 3：

输入：s = "A", numRows = 1
输出："A"

2. 解题思路

我们将Z形字符串沿垂直方向按照V形划分。

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

只需从上至下逐行，从左至右逐列遍历变换后的字符串，每次计算当前位置的字符在原字符串中的位置即可。

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) 
            return s;
        string r;
        int col_size = (2 * numRows - 2); // 按照每一个V形划分的列的size
        int col_amt = (s.size() + col_size - 1) / col_size;   // 一共有几列，向上取整
		int index;
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < col_amt; j++) {
                index = j * col_size + i;
                if (index < s.size())
                    r += s[index];
                // 既不是第一行，也不是最后一行，则还要处理斜线部分
                if (0 < i && i < numRows - 1) {
                    index = (j + 1) * col_size - i;
                    if (index < s.size())
                        r += s[index];
                }
            }
        }
        return r;

    }
};

算法正确性

• 单调性：每经过一次循环，原问题将缩减我们所划分的col_size大小的规模。

• 不变性：我们每次迭代只需计算出当前Z字型排列中的每一字符在原字符串中的位置，并将该字符拼接到结果串中即可。

算法复杂度

• 时间复杂度：每个字符只会被遍历一次，故该算法时间复杂度为。

• 空间复杂度：。