实际上是一个找规律的题(以下题解表达得很差,仅适合本人阅读)
解法思想对应官方题解中的行扫描——N 型排列后一行一行地将字符加入数组——但是比官方解法多了一个变量:官方解法中一个一个添加字符,这里是两个两个添加
以 Leetcode 示例为例,设字符串 s 为 PAYPALISHIRING,行数为 numRows(后文简称 n),见下图
首先把 N 型排列写出来,可以发现:排列看似是 N 型,实际上是斜 V 字型的循环(图中的蓝色字符),于是找到循环数,得出循环数公式: nextIndex = (n - 1) * 2
得到循环数,也就得到了图中绿色背景字符的规律:设每行首个字符的下标为 i,绿色背景字符的下标偏移量为 k,则 k = i + nextIndex
对于黄色背景的字符,可以发现:设每行首个字符的下标为 i,黄色背景字符的下标偏移量为 j,则 j = nextIndex - i * 2
最终将每行的字符按规律加入数组即可:每行的前两个字符下标分别为 i + j、i + k,之后分别累加循环数 nextIndex
C# 题解
public class Solution { public string Convert(string s, int numRows) { int n = s.Length, nextIndex = 2 * (numRows - 1); //长度和循环数 if (n == 1 || numRows == 1 || n <= numRows) return s; // 字符串长度小于等于行数时直接返回原串 StringBuilder sb = new StringBuilder(); // 使用 StringBuilder 防坑 for (int i = 0, cnt = 0; i < numRows; i++, cnt += 2) { // cnt 累加2,即 i * 2 sb.Append(s[i]); // 每行第一个字符 int step = nextIndex - cnt; // 黄色背景字符的下标偏移量 for (int j = i + step, k = i + nextIndex; j <= n - 1; j += nextIndex, k += nextIndex) { if (step != 0 && step != nextIndex) //第一行和最后一行不添加黄色背景字符 sb.Append(s[j]); if(k <= n - 1) // 循环退出条件是黄色背景字符,防止绿色背景字符下标溢出 sb.Append(s[k]); } } return sb.ToString(); } }