Leetcode 6 – Z 字形变换

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

解法思想对应官方题解中的行扫描——N 型排列后一行一行地将字符加入数组——但是比官方解法多了一个变量:官方解法中一个一个添加字符,这里是两个两个添加

以 Leetcode 示例为例,设字符串 s 为 PAYPALISHIRING,行数为 numRows(后文简称 n),见下图

Leetcode 6 - Z 字形变换

首先把 N 型排列写出来,可以发现:排列看似是 N 型,实际上是斜 V 字型的循环(图中的蓝色字符),于是找到循环数,得出循环数公式: nextIndex = (n – 1) * 2

得到循环数,也就得到了图中绿色背景字符的规律:设每行首个字符的下标为 i,绿色背景字符的下标偏移量为 k,则 k = i + nextIndex

对于黄色背景的字符,可以发现:设每行首个字符的下标为 i,黄色背景字符的下标偏移量为 j,则 j = nextIndexi * 2

最终将每行的字符按规律加入数组即可:每行的前两个字符下标分别为 i + ji + 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();
    }
}

Leetcode 6 - Z 字形变换

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据