当前位置：首页 > news >正文

OJ Z字形变换

news 2025/6/26 9:57:19

题目：

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P   A   H   N
A P L S I I G
Y   I   R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

示例：

根据以上的示意图和PAYPALISHIRING" 行数为 3 时，可以发现，不论行数是多少，第一行和最后一行的情况一定是一样的，所以可以对第一行和最后一行的规律进行总结，可以发现，我们所标记的下标，和行数n是有一定关系的。

以第一行和最后一行为例：

因为设定了行数为n行，那么就一定右n-1 个下标进行竖直排列，例如图上n=4，那么就有下标 0，1，2，3进行竖直排列。

而对于第一行和最后一行，它们的规律是：当前的下标 + 2* 总行数 -2 = 等于下一个位置的下标

同时对于其他行来说，如果不算入斜线部分（如上图的4，5和10，11），那么其他的下标和下标之间的跨越规律也和上图一致

所以我们可以专门对斜线部分进行规律的查找，查找斜线部分和斜线部分之间的规律，也就是如上图中，5和7之间的规律关系或者是4和8之间的规律关系

而经过查找我们也可以发现，斜线和斜线之间的关系页是下标数+2*总行数-2

而应为斜线的关系，所以每一行的斜线初始的位置是不一样的，所以需要找到行数和斜线初始位置下标的关系

代码编程

class Solution {
public:string convert(string s, int numRows) {int n = numRows;//行数string res;if (n == 1) {return s;}for (int i = 0; i < n; i++) //每一行下标的起始位置就是总行数0~n-1 为首的下标，以这些下标作为起始位置{if (i == 0 || i == n - 1) { // 第一行和最后一行for (int j = i; j < s.size(); j += 2 * n - 2) {res += s[j];}} else{ // 斜线部分for (int j = i, k = 2 * n - 2 - i; j < s.size() || k < s.size();j += 2 * n - 2, k += 2 * n - 2) //这里的k是初始的每一行的斜线部分起点位置{if (j < s.size())res += s[j];if (k < s.size())res += s[k];}}}return res;}
};