LeetCode 6. ZigZag Conversion

问题链接

题目解析

将一个字符串按之字形图案重新排列，返回新字符串。

解题思路

理解题意，什么叫之字形图案。举个例子，对于字符串"ABCDEFGHIJKLMN"：

numRows = 1：如下，输出不变，为"ABCDEFGHIJKLMN"；

ABCDEFGHIJKLMN

numRows = 2：如下，输出应为"ACEGIKMBDFHJLN"；

A C E G I K M
B D F H J L N

numRows = 3：如下，输出应为"AEIMBDFHJLNCGK"；

A - E - I - M
B D F H J L N
C - G - K - ?

numRows = 4：如下，输出应为"AGMBFHLNCEIKDJ"；

A - - G - - M
B - F H - L N
C E - I K - ?
D - - J - - ?

大概就是这个样子，“一竖一提一竖一提...”（“|/”）结构，很明显这是一道找规律的题。假设“一竖一提”作为一组，如Row=4时，"A_F"、"GL"为一组，可以发现每一组有（2*numRows-2）个元素。

本题中我们对输出结果按行进行一一赋值，对于“一竖”上的元素，相邻两组索引相差恰好为（2*numRows-2）；对于“一提”上的元素，假设已知其左边相邻字母索引为x，那么可以求得其索引为：(x-i + (2*numRows-2) - i)，其中 (i) 为函数，i ∈[0, numRows)。

注意“一提”与上下两行无关，以及随时检查时候超出原字符串总长度。

参考代码

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        int Col = 2*numRows - 2;
        string res = "";
        
        for (int i = 0; i < numRows; i++) {
            for (int j = i; j < s.size(); j+=Col) {
                res += s[j];//“一竖”
                int next = j-i + Col - i;
                if (i != 0 && i != numRows-1 && next < s.size())//“一提”
                    res += s[next];
            }
        }
        return res;
    }
};

模拟解法

当然了，本题可以开一个二维数组进行模拟，参考链接：https://leetcode.com/problems/zigzag-conversion/discuss/3403/Easy-to-understand-Java-solution。

原理简单，从上到下，再从下到上，其实就是对“一竖”、“一提”赋值，最后再整合到一个字符串中。参考代码如下：

public String convert(String s, int nRows) {
    char[] c = s.toCharArray();
    int len = c.length;
    StringBuffer[] sb = new StringBuffer[nRows];
    for (int i = 0; i < sb.length; i++) sb[i] = new StringBuffer();
    
    int i = 0;
    while (i < len) {
        for (int idx = 0; idx < nRows && i < len; idx++) // vertically down
            sb[idx].append(c[i++]);
        for (int idx = nRows-2; idx >= 1 && i < len; idx--) // obliquely up
            sb[idx].append(c[i++]);
    }
    for (int idx = 1; idx < sb.length; idx++)
        sb[0].append(sb[idx]);
    return sb[0].toString();
}

LeetCode All in One题解汇总（持续更新中...）

本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.