C#版[击败100.00%的提交] - Leetcode 6. Z字形变换 - 题解

版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章，欲转载请先私信获博主允许，转载时请附上网址
http://blog.csdn.net/lzuacm。

C#版 - Leetcode 6. Z字形变换 - 题解

Leetcode 6. ZigZag Conversion
在线提交: https://leetcode-cn.com/problems/zigzag-conversion/

题目描述

将字符串 “PAYPALISHIRING”以Z字形(Zigzag pattern)排列成给定的行数：

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

之后从左往右，逐行读取字符：“PAHNAPLSIIGYIR”

实现一个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);

示例 1:

输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"

示例 2:

输入: s = “PAYPALISHIRING”, numRows = 4
输出: “PINALSIGYAHRPI”

解释:
P I N
A L S I G
Y A H R
P I

● Difficulty:

Medium

Total Accepted: 216.3K
Total Submissions: 779.4K
相关话题字符串

分析:
<”PAYPALISHIRING”, 3> 的返回结果中的各字符在原字符串中的位置(下标index)具体如下:

s[0],s[4],s[8],s[12] 　　　　　　　　　// 第1行，间隔为4 =
s[1],s[3],s[5],s[7],s[9],s[11],s[13] 　　　// 第2行，间隔为2/2
s[2],s[6],s[10] 　　　　　　　　　　 // 第3行，间隔为4

numRows=4时，所返回的字符串中各字符原来的index的规律为：
第1行，间隔为6 =

当numRows=5时，所返回的字符串中各字符原来的index规律为：

第1行，间隔为8 =

根据重排的图，有一种较直观的思路：
用一个字符串str来存储每一行中字符拼接成的字符串，最后将每行得到的字符串拼接到一起即为所求结果。另外，用bool值down表示方向 - 先下后上将其记为true，否则记为false。

using System;
using System.Text;

namespace Leetcode6_Zigzag
{
    public class Solution
    {
        public string Convert(string s, int numRows)
        {
            StringBuilder sb = new StringBuilder();
            // base case
            if (s.Length == 0 || numRows <= 1)
                return s;

            // handle first row
            for (int i = 0; i < s.Length; i += (numRows - 1) * 2)
                sb.Append(s[i]);

            // handle middle rows
            for (int j = 1; j < numRows - 1; j++)
            {
                bool down = true;
                for (int i = j; i < s.Length;)  // Since the step has two possible values, so not add increase logic here.
                {
                    sb.Append(s[i]); // Add first element of current row, then add others
                    if (down) // going down
                        i += (numRows - 1 - j) * 2;
                    else // going up
                        i += 2*j;

                    down = !down; // switch direction
                }
            }

            // handle last row
            for (int i = numRows - 1; i < s.Length; i += (numRows - 1) * 2)
                sb.Append(s[i]);

            return sb.ToString();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
                Solution sol = new Solution();
                String str = "PAYPALISHIRING";
                int numRows = 4;

                var res = sol.Convert(str, numRows);
                Console.WriteLine(res);
        }
    }
}

不过此方法的需要另外考虑方向，并对首末两行进行特殊处理(运行时间: 112 ms)，我们可以考虑找更优的解法。

如果要找到更通用的下标 Index 的规律，可用下图来表示，分析知从蓝色格子走到绿色格子，需要

观察可知，假设目前在第 k行，则该行的字符在原字符串中的数字下标依次为：

因此，通用的规律如下：

当numRows=1或原字符串长度为0时，直接返回原字符串s即可，因为此时无需展开。
第k行的第一个字符在原字符串中的index就是k。
第1行和最后1行的间隔相等，都是整个过程中最大的，取名为maxGap，其值为2
中间的行相邻两个index的间隔数有2个，互相交替，但其和为maxGap(也可将maxGap看作每一行的周期)，分别取名为gap1和gap2。对于第k行，gap1 = maxGap-

已AC的代码:

using System;

namespace LeetCode_6ZigZagConversion
{
    public class Solution
    {
        public string Convert(string s, int numRows)
        {
            char[] res = new char[s.Length];
            // string res = new string(' ', s.Length);
            if (s.Length == 0 || numRows <= 1)
                return s;

            int pos = 0;
            for (int i = 0; i < numRows; i++)
            {
                int gap1 = 2 * (numRows - 1 - i);
                int gap2 = 2 * i;

                int index = i;
                while (pos < s.Length)
                {
                    if (gap1 > 0)
                    {
                        if (index >= s.Length)
                            break;
                        res[pos++] = s[index];  // Add char row by row
                        index += gap1;
                    }

                    if (gap2 > 0)
                    {
                        if (index >= s.Length)
                            break;
                        res[pos++] = s[index];
                        index += gap2;
                    }
                }
            }

            return new string(res);
        }
    }

    // Testing below
    class Program
    {        
        static void Main(string[] args)
        {
            Solution sol = new Solution();
            string res = sol.Convert("PAYPALISHIRING", 3);
            Console.WriteLine(res);
        }
    }
}