LeetCode_字符串_中等_6.N 字形变换

分手后的思念是犯贱 2023-10-06 18:11 25阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。  
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：  
![在这里插入图片描述][20210702095055530.png]  
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。  
请你实现这个将字符串进行指定行数变换的函数：  
string convert(string s, int numRows);

**示例 1：**  
输入：s = “PAYPALISHIRING”, numRows = 3  
输出：“PAHNAPLSIIGYIR”

**示例 2：**  
输入：s = “PAYPALISHIRING”, numRows = 4  
输出：“PINALSIGYAHRPI”  
解释：  
![在这里插入图片描述][20210702095109627.png]  
**示例 3：**  
输入：s = “A”, numRows = 1  
输出：“A”

**提示：**  
1<=s.length<=1000  
s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成  
1<=numRows<=1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zigzag-conversion

## 2.思路 ##

（1）找规律  
根据 N 字形变换，找出其中的规律所在，然后分不同的行来进行求解。

**① 对于第一行 (i = 0)**，以例 2 举例，观察题目中 N 字形变换可知，P 与 I、I 与 N 等等这些字符在原字符串中的下标距离均为 2 \* 4 - 2 = 6，即 numRows 的２倍再减去 2，记为 d，那么 N 字形变换后的排列的第一行的每相邻２个字符在原字符串中的下标距离为ｄ，这样就可先将第一行保存到 res 中；

**② 对于中间行 (1 ≤ i ≤ numRows - 2)**，分别从每一行第一个字符开始进行 numRows - 2 次 for 循环，通过观察可知：  
第 2 行中 (i = 1)，A 与 L、L 与 S、S 与 I、I 与 G 的下标距离分别为 4、2、4、2  
第 3 行中 (i = 2)，Y 与 A、A 与 H、H 与 R 的下标距离分别为 2、4、2、4  
再通过分析可得出结论，每一行中从第一个字符开始，相邻 2 个字符之间的下标距离分别为 (numRows - i) \* 2 - 2、2 \* i、(numRows - i) \* 2 - 2、2 \* i、(numRows - i) \* 2 - 2、2 \* i…，所以以此为依据再编写代码即可；

**③ 对于最后一行 (i = numRows - 1)**，对其的处理与第一行的类似，从下标为 numRows - 1 的字符（即字符 P）开始，每隔 d 个长度将对应的字符保存到 res 中，最后得到的 res 即为所求的结果，将其输出即可。

## 3.代码实现（Java） ##

//思路1————找规律
    class Solution {
        
        public String convert(String s, int numRows) {
        
            int length = s.length();
            if (length <= numRows || numRows == 1) {
        
                return s;
            }
            int d = numRows * 2 - 2;
            StringBuilder res = new StringBuilder();
            //将第一行的字符保存到 res 中
            for (int i = 0; i < length; i += d) {
        
                res.append(s.charAt(i));
            }
            //处理中间的字符
            for (int i = 1; i < numRows - 1; i++) {
        
                for (int j = i; j < length; ) {
        
                    res.append(s.charAt(j));
                    j += ((numRows - i) * 2 - 2);
                    if (j < length) {
        
                        res.append(s.charAt(j));
                        j += 2 * i;
                    }
                }
            }
            //将最后一行的字符保存到 res 中
            for (int i = numRows - 1; i < length; i += d) {
        
                res.append(s.charAt(i));
            }
            return res.toString();
        }
    }

[20210702095055530.png]: https://img-blog.csdnimg.cn/20210702095055530.png
[20210702095109627.png]: https://img-blog.csdnimg.cn/20210702095109627.png