# Zigzag solution

• """
public String zigZag(String s,int numRows){
int len = s.length();
if(len<=numRows || numRows<=1){
return s;
}else{
int per = 2*numRows - 2;
int remainder = len % per;
int count = len / per;
Map<Integer,List<Integer>> map = new HashMap<>();
for(int i=0;i<numRows;i++){
List<Integer> list = new ArrayList<Integer>();
for(int j=0;j<count;){
if(i%numRows == 0){
}else if(i%numRows == numRows - 1){
list.add(per * j + (numRows - 1));
}else{
list.add(per * j + ( i % numRows));
list.add(per * j + (per - i % numRows));
}
j++;
}
map.put(i, list);
}
//处理最后一个
if(remainder > 0){
for(int i=0;i<numRows;i++){
List<Integer> list = map.get(i);
if(i%numRows == 0){
}else if(i%numRows == numRows-1){
if(remainder >= numRows){
list.add(per * count+ numRows - 1);
}
}else{
if(remainder >= i % numRows + 1){
list.add(per * count + i % numRows);
if(remainder > per - i % numRows){
list.add(per * count + per - i % numRows);
}
}
}
map.put(i, list);
}
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<numRows;i++){
List<Integer> indexes = map.get(i);
for(int j=0;j<indexes.size();j++){
sb.append(s.charAt(indexes.get(j)));
}
}
return sb.toString();
}
}
""""

• @dinghaijun said in Zigzag solution:

"""
public String zigZag(String s,int numRows){
int len = s.length();
if(len<=numRows || numRows<=1){
return s;
}else{
int per = 2*numRows - 2;
int remainder = len % per;
int count = len / per;
Map<Integer,List<Integer>> map = new HashMap<>();
for(int i=0;i<numRows;i++){
List<Integer> list = new ArrayList<Integer>();
for(int j=0;j<count;){
if(i%numRows == 0){
}else if(i%numRows == numRows - 1){
list.add(per * j + (numRows - 1));
}else{
list.add(per * j + ( i % numRows));
list.add(per * j + (per - i % numRows));
}
j++;
}
map.put(i, list);
}
//处理最后一个
if(remainder > 0){
for(int i=0;i<numRows;i++){
List<Integer> list = map.get(i);
if(i%numRows == 0){
}else if(i%numRows == numRows-1){
if(remainder >= numRows){
list.add(per * count+ numRows - 1);
}
}else{
if(remainder >= i % numRows + 1){
list.add(per * count + i % numRows);
if(remainder > per - i % numRows){
list.add(per * count + per - i % numRows);
}
}
}
map.put(i, list);
}
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<numRows;i++){
List<Integer> indexes = map.get(i);
for(int j=0;j<indexes.size();j++){
sb.append(s.charAt(indexes.get(j)));
}
}
return sb.toString();
}
}
""""

首选：我们考虑特殊情况，字符串长度小于n；就是说只够一列，输入什么，那么返回值就是什么，比如：intput:“abc",2,output:"abc";input:"abc",1,output:"abc"
非特殊情况：找规律，算出每一行的字符索引，保存起来，然后按照索引将每行的字符组装起来。

• 规律如下：0 6 12
1 5 7 11 13
2 4 8 10 14 16
3 9 15
如上面的显示，字符串长度为17，n=4;
将显示结果分为2部分，一部分能够完整显示的，如索引 [0-5],[6-11],不能完整显示的：索引[12-16]；完整显示部分包含一整竖列字符个数 n ,倾斜的字数 n - 2,n-2为去掉竖列公用的和下一个完整显示的竖列第一个，所以一整个完整显示的字符数为：2n -2; 能够完整显示的个数为：count = s.length() / (2n -2);
循环计算0-n行存储的索引，每个完整显示的数为：per = 2n - 2：
j=0 j=1 ... j= count -1
第i=0行： per * j per * j per * j
第i=1行： perj + i%n perj + i%n perj + i%n
,per
j + per-i%n ,perj + per-i%n ,perj + per-i%n
...
第i=n-1行：perj + n -1 perj + n-1 perj + n-1
最后计算不完整的，remainder = s.length() % per,remainder >0：
12
13
14 16
15
i=0 : 如果remainder>0， per * count
i=1 : 如果remainder >= i % n + 1, per
count + i%n
如果remainder > per - i % n, percount + per - i%n
...
i=n-1: 如果remainder >=n , per
count + n -1
最后的结果就是：
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;i++){
List<Integer> indexes = map.get(i);
for(int j=0;j<indexes.size();j++){
sb.append(s.charAt(indexes.get(j)));
}
}
return sb.toString();

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.