题目：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
L C I R E T O E S I I G E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows); 示例 1: 输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN" 示例 2: 输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG" 解释: L D R E O E I I E C I H N T S G
C++
1.数学规律
这道题只是需要相应的字符串，不要求输出，明显难度降低了，因为这个图像是有规律的，发现每一满列对于行元素到下一满列对应行的元素距离是固定的，为k= (numRows-1)*2，我们便可以以此为基础，逐行添加字符。
时间复杂度实际是遍历一趟字符串s为O（n），空间复杂度O（n）
class Solution { public: string convert(string s, int numRows) { string ans; if(numRows<2)return s; int n=s.size(); for(int i=0;i<numRows&&i<n;i++){ int k=i; while(k<n){ ans+=s[k]; k+=(numRows-1)*2; if(i!=0&&i!=numRows-1){ if(k-i*2<n) ans+=s[k-i*2]; } } } return ans; } };
2.hash法
由于解1已经达到了我感觉的时空最简，我没有想出第二种方法，后看题解后，题解还有一种方法是按Z字型遍历s,将字符保存在对应行中；实际上这是一种hash思想，可以用vector还是实现，但是空间开销要比解法1大，时间复杂度不变
class Solution { public: string convert(string s, int numRows) { if(numRows<2)return s; int n=s.size(); vector<string> hash(min(numRows,n)); int k,f; k=0; for(int i=0;i<n;i++){ if(k==0)f=1; if(k==numRows-1)f=-1; hash[k]+=s[i]; k+=f; } string ans; for(string c:hash)ans+=c; return ans; } };
Python
1.数学规律
class Solution: def convert(self, s: str, numRows: int) -> str: if numRows==1: return s ans="" n=len(s) for i in range(numRows): k=i while k<n: ans+=s[k] k+=2*(numRows-1) if i!=0 and i!=numRows-1 and k-2*i <n: ans+=s[k-2*i] return ans
2.hash
class Solution: def convert(self, s: str, numRows: int) -> str: if numRows==1: return s hashrow=["" for _ in range(numRows)] k=0 flag=1 for c in s: if k==0: flag=1 if k==numRows-1: flag=-1 hashrow[k]+=c k+=flag return "".join(hashrow)
java
class Solution { public String convert(String s, int numRows) { if(numRows ==1) return s; StringBuilder ans=new StringBuilder(); int n=s.length(); for (int i=0;i<numRows;i++){ int k=i; while(k<n){ ans.append(s.charAt(k)); k+=2*(numRows-1); if(i!=0&&i!=numRows-1&&k-2*i<n) ans.append(s.charAt(k-2*i)); } } return ans.toString(); } }
class Solution { public String convert(String s, int numRows) { int n=s.length(); if(numRows==1 ||numRows>n) return s; StringBuilder[] row=new StringBuilder[numRows+1]; for(int i=0;i<=numRows;i++) row[i]=new StringBuilder(); int k=0,flag=1; for(int i=0;i<n;i++){ if(k==0)flag=1; if(k==numRows-1)flag=-1; row[k].append(s.charAt(i)); k+=flag; } for(int i=0;i<numRows;i++) row[numRows].append(row[i]); return row[numRows].toString(); } }
