LeetCode 刷题笔记——day 5

6. Z 字形变换

难度：中等

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

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

1
2
3

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

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

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

1	string convert(string s, int numRows);

示例 1：

1 2	输入：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：

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

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

我的答案

思路：
首先，因为在行数大于等于字符串长度或者行数为 1 的时候，输出字符串本身即可，所以在第一步就直接判断两种情况并返回，节省程序运行时间，然后把 Z 字形字符串以第一行为界分为几个小区间，在每个小区间内遍历字符并分配到所在行数，最终把所有行字符串相加即可。

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

        vector<string> str(numRows);
        int n = (numRows - 1) * 2;
        for(int i = 0; i < s.size(); i += n) {
            int m = 0;
            for(int j = 0; i + j < s.size() && j < n; j++) {
                if(j <= n / 2) {
                    m = j;
                } else {
                    m--;
                    if(m == 0) {
                        break;
                    }
                }
                str[m] += s[i + j];
            }
        } 

        string s0 = "";
        for(int i = 0; i < numRows; i++) {
            s0 += str[i];
        }
        return s0;
    }
};

执行用时: 8 ms
内存消耗: 10.5 MB

官方答案

老实说，我觉得我的解法还行，不过还是看看官方题解。官方题解里依然给出了两种方法：

按行排序

思路
通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。
算法
我们可以使用 $\text{min}( \text{numRows}, \text{len}(s))$ 个列表来表示 Z 字形图案中的非空行。
从左到右迭代 $s$ ，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。
只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。
作者：LeetCode

这里用 C++ 复现了一遍官方解法：

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

        vector<string> str(numRows);
        int i = 0;
        bool m = false;

        for(char c : s) {
            str[i] += c;
            if(i == 0 || i == numRows - 1) m = !m;
            i += m ? 1 : -1;
        }

        string s0;
        for(string st : str) s0 += st;
        return s0;
    }
};

执行用时: 12 ms
内存消耗: 10.4 MB

官方题解中第一步只判断输出了行数为 1 的情况，增加 numRows >= s.size() 判断，也算是难得给官方升级一下。

同样练习练习用 Java 来实现一遍：

class Solution {
    public String convert(String s, int numRows) {
        if (numRows >= s.length() || numRows == 1) return s;

        List<StringBuilder> strs = new ArrayList<>();
        for(int i = 0; i < numRows; i++) strs.add(new StringBuilder());

        int n = 0;
        boolean m = false;

        for(char c : s.toCharArray()) {
            strs.get(n).append(c);
            if(n == 0 || n == numRows - 1) m = !m;
            n += m ? 1 : -1;
        }

        StringBuilder str = new StringBuilder();
        for(StringBuilder sb : strs) str.append(sb);
        return str.toString();
    }
}

执行用时: 5 ms
内存消耗: 39 MB

官方给出的第二种解法是：

按行访问

思路
按照与逐行读取 Z 字形图案相同的顺序访问字符串。
算法
首先访问 行 0 中的所有字符，接着访问 行 1 ，然后 行 2 ，依此类推…
对于所有整数 $k$ ，
行 0 中的字符位于索引 $k \; (2 \cdot \text{numRows} - 2)$ 处;
行 $\text{numRows}-1$ 中的字符位于索引 $k \; (2 \cdot \text{numRows} - 2) + \text{numRows} - 1$ 处;
内部的 行 i 中的字符位于索引 $k \; (2 \cdot \text{numRows}-2)+i$ 以及 $(k+1)(2 \cdot \text{numRows}-2)- i$ 处;
作者：LeetCode

这里用 C++ 复现了一遍官方代码：

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

        string str;
        int n = s.size();
        int m = 2 * numRows - 2;

        for(int i = 0; i < numRows; i++) {
            for(int j = 0; j + i < n; j += m) {
                str += s[j + i];
                if(i != 0 && i != numRows -1 && j + m - i < n) str += s[j + m - i];
            }
        }

        return str;
    }
};

执行用时: 4 ms
内存消耗: 8 MB

不得不说，效率提升很多啊。

继续练习一遍 Java 实现：

class Solution {
    public String convert(String s, int numRows) {
        if (numRows >= s.length() || numRows == 1) return s;

        StringBuilder sb = new StringBuilder();
        int n = s.length();
        int m = 2 * numRows - 2;

        for(int i = 0; i < numRows; i++) {
            for(int j = 0; j + i < n; j += m) {
                sb.append(s.charAt(j + i));
                if(i != 0 && i != numRows - 1 && j + m - i < n) sb.append(s.charAt(j + m - i));
            }
        }

        return sb.toString();
    }
}

执行用时: 2 ms
内存消耗: 38.8 MB