Print By ZigZag

发表于 | 分类于

题目描述：

这题来源于LeetCode，具体可以看这里.

解题思路：

第一种解题思路是找到打印的规律；主要有两个地方：

  • 如果是第一行和最后一行，字符串的间隔和nrows有关；间隔为2(nrows - 1);
  • 如果是中间行，其间隔是交替出现规律的；规律并且和所处的行数j有关；对于第j行而言；其下标间隔为2(nrows - 1 - j)和2j交替出现的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    string convert(string s, int numRows) {
        if (s.size() <= numRows || numRows == 1) return s;
        int interval = 2 * numRows - 2;
        string res;
        for (int i = 0; i < numRows; i++){
            if (i == 0 || i == numRows - 1){
                int j = i;
                res = res + s[j];
                while((j + interval) < s.size()){
                    j += interval;
                    res = res + s[j];
                }//如果是第一行和最后一行的规律
            }else{
                int j = i;
                res = res + s[j];
                bool flag = true;
                while(j < s.size()){
                    if (flag){
                        if ((j + interval - 2 * i) < s.size()){
                            res = res + s[j + interval - 2 * i];
                            j = j + interval - 2 * i;
                            flag = false;
                        }else{
                            break;
                            
                        }
                        //第一种间隔2(nrows - 1 - i)
                    }else{
                        if (j + 2 * i < s.size()){
                            res += s[j + 2 * i];
                            j += 2 * i;
                            flag = true;
                        }else{
                            break;
                        }
                        //第二种规律是2i
                    }
                }
            }
        }
        return res;
    }
};

解题思路2：

第二种解题思路我们可以将每行存入数组，我们遍历字符串，利用标记变量决定存入数组的方式，存入的方式根据锯齿的走向决定向上还是向下；向上走到第0行后就向下；向下走到nrows - 1后就向上走。

代码如下：

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        string res[numRows];
        string result;
        int step = 0;
        int row = 0;
        for (int i = 0; i < s.size(); i++){
            res[row] = res[row] + s[i];//存入数组
            if (row == 0) step = 1;
            if (row == numRows - 1) step = -1; //决定走向
            row = row + step;//数组下标随走向决定
        }
        for (int i = 0; i < numRows; i++){
            result = result + res[i];//将数组连起来返回
        }
        return result;
    }
};