找规律 - ZigZag解码[E]

优质
小牛编辑
132浏览
2023-12-01

006.ZigZag Conversion[E]

题目

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)

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

思路1——用字符串数组

我能说我一开始完全没看懂吗?我是根据Custom Testcase自己慢慢测试摸索出来的。
其实,应该是这样的
2行:
A C E B D F

3行:
A E I B D F H J C G _ K

所以有个简单的思路:

  • 每行弄个string。
  • 对原始字符串进行扫描,从上往下,从下往上,依次加入每行的string
  • 最后把所有的string拼接起来
    1. class Solution {
    2. public:
    3. string convert(string s, int numRows) {
    4. string str[numRows],tmp;
    5. if(numRows == 1)
    6. return s;
    7. int flag;
    8. for(int i = 0,j = 0;i < s.length(); i++)
    9. {
    10. if(j == 0)
    11. flag = 1;
    12. if(j == numRows-1)
    13. flag = -1;
    14. str[j] += s[i];
    15. j += flag;
    16. }
    17. for(int i = 0; i < numRows;i++){
    18. tmp += str[i];
    19. }
    20. return tmp;
    21. }
    22. };

思路2——观察规律

2行:
A C E B D F

3行:

A E I B D F H J C G _ K

4行:

A G
B F H
C E I K D _ J

观察规律后,以每行的元素作为轴,可以发现,下面的字母都是对称排列的
换成对应的index后,规律更明显

0 4 8 1 3 5 7 9 2 6 _ 10

第2层的元素就是以第一行的元素为轴,+1,-1
第三层的元素就是以第一行的元素为轴,+2,-2
……
但是最后一层的元素,由于其特殊性,我们可以只考虑+k

Ps.所有过界的元素都不考虑

轴也有规律:除了首尾两层,其他都是2个,所以第一层每隔2n-2出现一次。

  1. class Solution {
  2. public:
  3. string convert(string s, int numRows)
  4. {
  5. string tmp;
  6. if(numRows == 1)
  7. return s;
  8. int inc = 2*numRows-2; //每次轴增加的步长
  9. int len = s.length();
  10. for(int i = 0; i < numRows;i++)
  11. {
  12. for(int j = 0;j < s.length()+numRows; j += inc)
  13. {
  14. if(j - i > 0 && j - i < s.length()
  15. && i != 0 && i != numRows -1) //首,尾只考虑+不考虑-
  16. tmp+= s[j-i];
  17. if(j + i < s.length())
  18. tmp += s[j+i];
  19. }
  20. }
  21. return tmp;
  22. }
  23. };