Leetcode 6 – Z 字形变换

实际上是一个找规律的题（以下题解表达得很差，仅适合本人阅读）

解法思想对应官方题解中的行扫描——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();
    }
}