一、说明
将字符串 `"PAYPALISHIRING"` 以Z字形排列成给定的行数：
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
二、解决方案参考
1. Swift 语言
class Solution {
func convert(s: String, _ numRows: Int) -> String {
if numRows == 1 {
return s
}
var ret: [Character] = []
var chars: [Character] = [Character](s.characters)
let cnt = chars.count
for i in 0..<numRows {
let len = 2 * numRows - 2
var index = i
while index < cnt {
ret.append(chars[index])
if i != 0 && i != numRows - 1 {
let tmpIndex = index + 2 * (numRows - i - 1)
if tmpIndex < cnt {
ret.append(chars[tmpIndex])
}
}
index += len
}
}
return String(ret)
}
}
2. JavaScript 语言
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var ans, max_column;
function dfs(x, y, s, n, numRows) {
ans[x][y] = s[n];
if (s.length === n) {
max_column = y;
return;
}
if (y % (numRows - 1) === 0 && x !== numRows - 1)
dfs(x + 1, y, s, n + 1, numRows);
else
dfs(x - 1, y + 1, s, n + 1, numRows);
}
var convert = function(s, numRows) {
if (numRows === 1)
return s;
ans = [];
for (var i = 0; i < numRows; i++)
ans[i] = [];
dfs(0, 0, s, 0, numRows);
var tmp = '';
for (var i = 0; i < numRows; i++)
for (var j = 0; j <= max_column; j++)
if (ans[i][j] !== undefined)
tmp += ans[i][j];
return tmp;
};
3. Python 语言
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows <= 1:
return s
n = len(s)
ans = []
step = 2 * numRows - 2
for i in range(numRows):
one = i
two = -i
while one < n or two < n:
if 0 <= two < n and one != two and i != numRows - 1:
ans.append(s[two])
if one < n:
ans.append(s[one])
one += step
two += step
return "".join(ans)
4. Java 语言
参考一：
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++)
rows.add(new StringBuilder());
int curRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}
}
参考二：
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder ret = new StringBuilder();
int n = s.length();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret.append(s.charAt(j + i));
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret.append(s.charAt(j + cycleLen - i));
}
}
return ret.toString();
}
}
5. C++ 语言
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string convert(string s, int nRows) {
//The cases no need to do anything
if (nRows<=1 || nRows>=s.size()) return s;
vector<string> r(nRows);
int row = 0;
int step = 1;
for(int i=0; i<s.size(); i ++) {
if (row == nRows-1) step = -1;
if (row == 0) step = 1;
//cout << row <<endl;
r[row] += s[i];
row += step;
}
string result;
for (int i=0; i<nRows; i++){
result += r[i];
}
return result;
}
int main(int argc, char**argv){
string s;
int r;
s = "PAYPALISHIRING";
r = 3;
cout << s << " : " << convert(s, 3) << endl;
}
6. C 语言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static char* convert(char* s, int numRows)
{
if (numRows <= 1) return s;
int len = strlen(s);
char *new_str = malloc(len + 1);
char *p = new_str;
int row = 0;
for (row = 0; row < numRows; row++) {
int interval1 = numRows + (numRows - 2) - row * 2;
int interval2 = 2 * row;
int flag = 0;
int i = row;
while (i < len) {
*p++ = s[i];
int delta = 0;
do {
delta = flag == 0 ? interval1 : interval2;
flag = !flag;
} while (delta == 0);
i += delta;
}
}
new_str[len] = '\0';
return new_str;
}
int main(int argc, char **argv)
{
if (argc < 3) {
printlf(stderr, "./test string num");
exit(-1);
}
printf("%s", convert(argv[1], atoi(argv[2])));
return 0;
}
--------------------------------------
版权声明：本文为【PythonJsGo】博主的原创文章，转载请附上原文出处链接及本声明。
博主主页：https://my.oschina.net/u/3375733
本篇文章同步在个人公众号：
