# 引言
题目链接：https://leetcode.com/problems/zigzag-conversion/description/
# 题目大意
给出一个字符串，和一个指定行数，将字符串纵向按照 z 字形排列 (指定行数为 z 字形大小)
- Example
s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
# 题解
# 一句话题解
一个规律题，按照 Z 字形排列图，逐行扫描，推断每一行下一个出现字母的索引的位置即可。
具体规律见图
复杂度 O(n)
# AC 代码
c++ 版本
class Solution | |
{ | |
public: | |
string convert(string s, int numRows) | |
{ | |
int len = s.length(); | |
if (len <= 1 || len <= numRows || numRows <= 1) | |
{ | |
return s; | |
} | |
char rStr[len + 1]; | |
memset(rStr, '\0', sizeof(rStr)); | |
for (int i = 0, j = 0; i < numRows; ++i) | |
{ | |
int k = i; | |
// 逐行扫描 | |
if (0 == i || numRows - 1 == i) | |
{ | |
while (k < len) | |
{ | |
rStr[j++] = s[k]; | |
k += (numRows - 1) * 2; | |
} | |
} | |
else | |
{ | |
while (k < len) | |
{ | |
rStr[j++] = s[k]; | |
int h = k + (numRows - i - 1) * 2; | |
if (h < len) | |
{ | |
rStr[j++] = s[h]; | |
} | |
k += (numRows - 1) * 2; | |
} | |
} | |
} | |
return string(rStr); | |
} | |
}; |
go 版本
func convert(s string, numRows int) string { | |
lens := len(s) | |
if lens <= 1 || lens <= numRows || numRows <= 1 { | |
return s | |
} | |
rStr := make([]byte, lens) | |
index := 0 | |
for i := 0; i < numRows; i = i + 1 { | |
k := i | |
if 0 == i || numRows - 1 == i { | |
for k < lens { | |
rStr[index] = s[k] | |
index = index + 1 | |
k = k + (numRows - 1) * 2 | |
} | |
} else { | |
for k < lens { | |
rStr[index] = s[k] | |
index = index + 1 | |
h := k + (numRows - i - 1) * 2 | |
if h < lens { | |
rStr[index] = s[h] | |
index = index + 1 | |
} | |
k = k + (numRows - 1) * 2 | |
} | |
} | |
} | |
return string(rStr) | |
} |
