6 ZigZag Conversion 之子形转换字符串

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

Difficulty:Medium

首先来解释下ZigZag,先看下图,就是把字符串按照如下的方式串起来

当nRows=3, result=0481357926

当nRows=4, result=0615724839

nRows = 3

nRows = 4

解法1

比较直观的解法,用一个字符串数组string[]存储区每一行,最后拼接一下.用一个delta表示前进方向的正向还是反向.即从上到下还是从下到上

class Solution {
public:
    string convert(string s, int numRows) {
        int len = s.size();
        if (len==0||numRows<=1) return s;
        string res[numRows] = {""};
        //这里需要注意下,不同编译器会报错
        // res[numRows] = {""};
        int row = 0,delta = 1;
        for (int i = 0; i < len; i++) {
            res[row] += s[i];
            row += delta;
            if (row >= numRows) {
                row = numRows - 2;
                delta = -1;
            }
            if (row < 0) {
                row = 1;
                delta = 1;
            }
        }
        string result = "";
        for (int i = 0; i < numRows; i++) {
            result += res[i];
        }
        return result;
    }
};

解法2

传说的观察法,比如给定一个字符串0123456789ABCDEF

当 n = 2时,

当 n = 3时,

当 n = 4时,

从图中可以看出,每行相邻的黑色元素的索引之差为2*n-2

每个红色元素的索引为j + 2*n-2 - 2*i,j为列数,i为行数.

所以可以写出:

string convert2(string s, int numRows) {
        int len = s.size();
        if (len==0||numRows<=1) return s;
        string res = "";
        int size = 2 * numRows - 2;
        for (int i = 0; i < numRows; i++) {
            for (int j = i; j < len; j += size) {
                res += s[j];
                //找到两个黑色元素中间的红色元素
                int tmp = j + size - 2 * i;
                if (i > 0 && i < numRows && tmp < len)
                    res += s[tmp];
            }
        }
        return res;
    }

 
comments powered by Disqus