6.N字形变换

发表于： 分类于：
字数： 750 阅读：≈ 2分钟

🎈 6.N字形变换

将一个给定字符串 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);

思路

基本思想

题目的意思就是将给定的字符串按照N字形排列，例如给定一个LEETCOD，最终排序之后变成下图所示：

image-20231104193657548

所以说最重要的就是模拟这个N字形，这个N字形的高已经给定，就是指定的行数，可以发现元素在排序时，元素行下标的变化范围始终在[0,numRows]中变化，并且先变大后变小，也就是先加一步，到了转折点再减一步

知道上面的步骤之后，可以发现一到了转折点加就会变成减，而这个转折点要么在第一行，要么在最后一行，所以可以设置一个步长，要么加一步要么减一步，最终的代码为：

1
2

if(index==0||index==numRows-1)
    flag=-flag;

每次往一行中添加一个字符，遍历完整字符串之后，每一行的字符也就遍历得到了，最终将每一行拼接返回即可：

image-20231104194303317

执行流程

  1. 初始化一个numRows行的字符串数组
  2. 从头开始遍历字符串，一旦遇到转折点，步长就会变成相反数，也就是加一步变成减一步，减一步变成加一步
  3. 遍历完成之后，将每一行的字符串拼接起来返回即可

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public String convert(String s, int numRows) {
        //只有一行，没必要转换，直接返回
        if(numRows<2)
            return s;
        String[] strs=new String[numRows];
        Arrays.fill(strs,"");
        int index=0,flag=-1;
        String res="";
        for(int i=0;i<s.length();++i){
            char c=s.charAt(i);
            strs[index]+=c;
            //到转折点开始变换方向
            if(index==0||index==numRows-1)
                flag=-flag;
            index+=flag;
        }
        for(int i=0;i<numRows;++i){
            res+=strs[i];
        }
        return res;
    }
}

总结

主要是清楚N字形成的过程中，相当于每次向一行中添加一个字符，每一行的行标变化有规律，要么加一步，要么减一步，变化的转折点在第一行和最后一行，所以以此建立一个下标，从而实现下标的来回变化