06/15 13:38

# 一、说明

将字符串 "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++)

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;
}

--------------------------------------

0
0 收藏

0 评论
0 收藏
0