ZigZag-转换问题

下载 ZigZagConversion.zip (8 KB)

这篇文章是 Eric Z 的 Graph is everywhere 的替代方案。也许你也会参考它，因为他提供了一个非常不同的解决方案概念。

问题

ZigZag 转换问题 是一个巧妙的程序员谜题

假设字符串 "PAYPALISHIRING" 被写在一个给定的行数上的锯齿形图案中，例如这样（3 行）

P   A   H   N
 A P L S I I G
  Y   I   R

以水平线读取的结果是："PAHNAPLSIIGYIR"
现在编写一个函数来实现这种转换。

解决方案概念

正如我的原文所说，传统上这是通过搜索同一行上字母的索引中的模式来解决的。作为一个传统主义者，我做的正是这样 ;-)

比较具有不同行数的锯齿形图案，并为锯齿形图案中的每个字母记录下到达水平线上下一个字母的步长

(3 Rows)
P   A   H   N
 A P L S I I G
  Y   I   R
steps: 4,2,4,2,...

(4 Rows)
P     I     N
 A   L S   I G
  Y A   H R
   P     I
steps: 6,4,2,6,4,2,...

这两个示例实际上足以识别模式：它是小序列的循环重复。
循环大小等于行数 - 1。

代码

static string ZigZagConvert(string input, int nRows) {
    var cycle = (nRows - 1).Times().From(nRows * 2 - 2).Step(-2); // nRows:3=>{4,2}, 4=>{6,4,2} ...
    var infinite = int.MaxValue.TimesRepeat(cycle).SelectMany(ccl => ccl);
    var map = infinite.Take(input.Length).ToArray();
    var result = new List<int>();
    for (var line = 0; line < nRows; line++) {
        for (var index = line; index < input.Length; index += map[index]) result.Add(index);
    }
    return new string(result.Select(i => input[i]).ToArray());
}

让我尝试解释那些几行代码中不重要的部分

• var cycle = (nRows - 1).Times().From(nRows * 2 - 2).Step(-2);
  定义了前面提到的那个小序列
  请注意我花哨的 int.Times() - 扩展 - 通常该行将表示为
  var cycle = Enumerable.Range(1, nRows - 1).Select(i => (nRows - i) * 2);
   
• var infinite = int.MaxValue.TimesRepeat(cycle).SelectMany(ccl => ccl);
  循环序列的（附近）无限重复，并展平层次结构（通过 .SelectMany() 实现）
  再次使用了我的 int 扩展 - 你可以将其视为
  var infinite = Enumerable.Repeat(cycle, int.MaxValue).SelectMany(ccl => ccl);
   
• var map = infinite.Take(input.Length).ToArray();
  创建一个数组，将每个输入字母索引映射到步长，以找到水平线上下一个字母的位置。
   
•  (跳过两行不重要的代码)
   
• for (var index = line; index < input.Length; index += map[index]) result.Add(index);
  这行代码循环水平线上的字母，从一个字母到下一个字母 - 非常类似于图遍历
  输入字母索引定义节点，而映射数组定义边。

使用代码

static void Main() {
    for (var i = 2; i < 6; i++) Console.WriteLine(ZigZagConvert("PAYPALISHIRING", i));
    Console.ReadKey();
}

输出四个变体的锯齿形转换后的 "PAYPALISHIRING"

P Y A I H R N
 A P L S I I G

PYAIHRNAPLSIIG

P   A   H   N
 A P L S I I G
  Y   I   R

PAHNAPLSIIGYIR

P     I     N
 A   L S   I G
  Y A   H R
   P     I

PINALSIGYAHRPI

P       H
 A     S I
  Y   I   R
   P L     I G
    A       N

PHASIYIRPLIGAN

关注点

像很多时候一样，仅仅查看几个输入/输出示例就能得到一个方便的解决方案。

扩展函数，尤其是 Linq 的内容，可以带来非常简洁的代码，并且非常直观易懂。

顺便说一下，我对一些 int.Times() 扩展进行了一个小小的介绍（包含在附件的源文件中）。我经常需要序列，并且我更喜欢将它们作为扩展提供，以避免使用静态 Enumerable.Range() 的一些迂回方式。