Z字型变换

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

1
2
3

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

1

string convert(string s, int numRows);

示例 1：

1
2

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

1
2
3
4
5
6
7

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

1
2

输入：s = "A", numRows = 1
输出："A"

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、',' 和 '.' 组成
  • 1 <= numRows <= 1000

解法1：

写出每一个字母的坐标，然后找出规律

比如(P点是原点，向下是x轴，向右是y轴)

1
2
3
4
5
6
7

s = "PAYPALISHIRING", numRows = 3
//P0,0 A1,0 Y2,0 P1,1 
//A0,2 L1,2 I2,2 S1,3
      
//        P   A   H   N
//        A P L S I I G
//        Y   I   R

注意到，每4次出现循环，将字母填入坐标系中。

最后按顺序遍历坐标系，即可获得变换后的顺序。

 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

public static String convert(String s, int numRows) {
        if(numRows==1){
            return s;
        }
        int n_temp=s.length();
        char bb[][]=new char[numRows][n_temp];
        String ans="";
        int cir=0;
        int x=0,y=0;
        int flag=0;
        for(int i0=0;i0<n_temp;i0++){
            cir=i0%(2*numRows-2);
            if(cir>=numRows|cir==0&i0>0){
                y++;
            }

            if(cir>=numRows) x--;
            else x=cir;
            bb[x][y]=s.charAt(i0);
        }
        for(int i=0;i<bb.length;i++){

            for(int j=0;j<bb[i].length;j++){
//char的默认值是0
if(bb[i][j]!=0)  ans=ans+bb[i][j];
            }
        }
        return ans;
        }

这样时间和空间效率都不高。给出每一个字母的索引就能得到位置。反过来通过位置找到字母行不行呢？

解法2：

比如变换后的第一个字母是P（拿以上的例子），索引是0；第二个字母是A，对应的原来的索引是4；然后8，12，16……取0，4，8，12，16个字母即可获得第一行。

第二行同样的方法，A(1),P(3),L(5),S(7),I(9)

第三行：Y(2),I(6),R(10)

对于示例 2：

1
2
3
4
5
6
7

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

第一行：0，6，12

第二行：1，5，7，11，13（其实是0，6，12的前一个和后一个）

第三行：2，4，8，10（其实是3，9的前一个和后一个）

第四行：3，9

思路好像没问题？

但是看了下其他人的解法，我还是弱爆了。

解法3：

简单易懂空间小，膜！

注意flag的巧妙用法。

https://leetcode-cn.com/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/