C#版[击败100.00%的提交] - Leetcode 6. Z字形变换 - 题解
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 = 2⋅(3−1)2⋅(3−1)2 \cdot (3-1)
- 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 = 2⋅(4−1)2⋅(4−1)2 \cdot (4-1) 第2行，间隔为4/2交替 第3行，间隔为2/4交替 第4行，间隔为6
当numRows=5时，所返回的字符串中各字符原来的index规律为：
第1行，间隔为8 = 2⋅(5−1)2⋅(5−1)2 \cdot (5-1) 第2行，间隔为6/2交替 第3行，间隔为4/4 第4行，间隔为2/6交替 第5行，间隔为8 如果觉得不够直观，可以看看另一个例子<”THISPROBLEMISAWESOME”, 4>(位置重排)：
根据重排的图，有一种较直观的思路： 用一个字符串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 的规律，可用下图来表示 ，分析知从蓝色格子走到绿色格子，需要 2⋅[(n−1)−(2)]2⋅[(n−1)−(2)]2\cdot[(n-1)-(2)]步，而从绿色格子到红色格子需要的步数是 2⋅(2)2⋅(2)2 \cdot (2)：
观察可知，假设目前在第 k行，则该行的字符在原字符串中的数字下标依次为：
- kkk
- k+2⋅(n−1−k)k+2⋅(n−1−k)k + 2\cdot(n-1-k)
- k+2⋅(n−1−k)+2⋅kk+2⋅(n−1−k)+2⋅kk + 2\cdot(n-1-k) + 2\cdot k
- k+2⋅(n−1−k)+2⋅k+2⋅(n−1−k)k+2⋅(n−1−k)+2⋅k+2⋅(n−1−k)k + 2\cdot (n-1-k) + 2\cdot k + 2\cdot(n-1-k)
- k+2⋅(n−1−k)+2⋅k+2⋅(n−1−k)+2⋅kk+2⋅(n−1−k)+2⋅k+2⋅(n−1−k)+2⋅kk + 2\cdot (n-1-k) + 2\cdot k + 2\cdot (n-1-k) + 2\cdot k
- …
因此，通用的规律如下：
- 当numRows=1或原字符串长度为0时，直接返回原字符串s即可，因为此时无需展开。
- 第k行的第一个字符在原字符串中的index就是k。
- 第1行和最后1行的间隔相等，都是整个过程中最大的，取名为maxGap，其值为2⋅⋅\cdot numRow-2。
- 中间的行相邻两个index的间隔数有2个，互相交替，但其和为maxGap(也可将maxGap看作每一行的周期)，分别取名为gap1和gap2。对于第k行，gap1 = maxGap-2⋅k2⋅k2\cdot k = 2 ⋅⋅\cdot (numRows - 1 - k)，gap2 = maxGap-gap1 = 2⋅k2⋅k2\cdot k。
已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);
}
}
}此方法不需记录方向，只需保证gap1在自减和gap2在自增的过程中均>0即可，且不需对首尾两行进行特殊处理。
Rank: 运行时间: 102 ms. You are here! Your runtime beats 100.00% of csharp submissions.
腾讯云开发者
