问题链接

题目解析

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

解题思路

理解题意，什么叫之字形图案。举个例子，对于字符串"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"、"G~L"为一组，可以发现每一组有（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;    }};

模拟解法

当然了，本题可以开一个二维数组进行模拟，参考链接：。

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

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();}

---

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

---