LeetCode06-Z字形变换
6. Z 字形变换：
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
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
示例 3：
输入：s = "A", numRows = 1
输出："A"
提示：
- 1 <= s.length <= 1000
- s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
- 1 <= numRows <= 1000
解题思路1：
二维数组，硬模拟。
class Solution {
public:
string convert(string s, int numRows) {
if(numRows==1)
return s; //1行直接返回，也无法进行填充模拟
char a[1005][1005];
memset(a,'*',sizeof(a)); //单字节char可以初始化为任意值,多字节int,long等类型只能初始化为0、1,具体百度
//全部初始化为*,硬模拟填充字符
int i=0,j=0; //i表示行,j表示列
int flag=0; //flag=0表示向下走，flag=1表示向右上走
int k=0,len=s.length();
while(k<len){
if(flag==0){
a[i][j] = s[k];
if(i!=numRows-1){ //向下走
i++;
}else{ //向右上走
i--,j++;
flag=1;
}
}else{
a[i][j] = s[k];
if(i!=0){ //向右上走
i--,j++;
}else{ //向下走
i++;
flag=0;
}
}
k++;
}
string ans ="";
for(int m=0;m<=numRows;m++){
for(int n=0;n<=j;n++){
if(a[m][n]!='*')
ans+=a[m][n];
}
}
return ans;
}
};
解题思路2：
数学推导，每次最大间隔为2*numRows-2
class Solution {
public:
string convert(string s, int numRows) {
string ans="";
if(numRows==1)
ans=s;
else if(numRows==2)
{
int len=s.size();
for(int i=0;i<len;i+=2)
ans+=s[i];
for(int i=1;i<len;i+=2)
ans+=s[i];
}
else if(s.size()<=numRows)
ans=s;
else
{
int len=s.size();
int dist=2*numRows-2; //最大间隔
int tmp=dist;
int now;
for(int i=0;i<numRows;i++)
{
now=dist-tmp;
for(int j=i;j<len;j+=now)
{
ans+=s[j];
if(i==0||i==numRows-1)
now=dist;
else
now=dist-now;
}
tmp-=2;
}
}
return ans;
}
};