前言
假装开学好好学习
正文
问题来源
本问题来自leetcode上的283题。
问题描述
将字符串 “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
分析：
想法：在二维数组中形成这样的Z形串，然后转化到字符串中 本人写的Go代码如下：
func convert(s string, numRows int) string {
if numRows == 1 {
return s
}
b := []byte(s)
sl := len(b)
array := make([][]byte, 0)
el := sl
//e := make([]byte, el)
i := 0
for ; i < numRows; i++ {
e := make([]byte, el)
for j:=0 ; j < el; j++ {
e[j] = 32
}
array = append(array, e)
}
i = 0
for ; i < sl; i++ {
x := i/2/(numRows-1)
y := 0
left := i - x*2*(numRows-1)
div := left - (numRows-1)
if div < 0 {
x = x * (numRows-1)
y = left
} else {
x = x * (numRows-1) + div
y = numRows - div - 1
}
array[y][x] = s[i]
}
buf := make([]byte, el)
index := 0
for i=0; i < numRows; i++ {
for j:=0; j < el; j++ {
if 32 != array[i][j] {
buf[index]=array[i][j]
index++
}
}
}
return string(buf)
}
直接找规律进行Z转化
func convert(s string, numRows int) string {
if ( len(s) == 0 || len(s) == 1 ||numRows == 1 || len(s) <= numRows){
return s
}
result := make([]byte,0, len(s))
for i := 0; i < numRows; i++{
result = append(result, s[i])
for j := i; j < len(s) ; {
if j += 2 * (numRows - i - 1);j < len(s)&& numRows - i - 1 != 0{
result = append(result, s[j])
}
j += 2 * i
if j < len(s) && i != 0 {
result = append(result, s[j])
}
}
}
return string(result[:])
}
空间换时间，C++
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;
}
总结：
本来可以很简单解决的，相反把问题弄复杂了
结语
不管怎么样好好加油。
