LeetCode题解——ZigZag Conversion

题目：

把一个字符串按照Z型排列后打印出来，例如 "PAYPALISHIRING" 重新排列后为3行，即

P   A   H   N

A P L S I I G

Y   I   R

那么输出为"PAHNAPLSIIGYIR"

解法：

细节实现题，假如重新排列为5行，那么排列后的下标分布应该为

0　　　　　　　　 8　　　　　　　　　 16　　　　　　　　24

1　　　　　　7　　9 　　　　　　 15　 17　　　　　　23　

2　　　　6　　　　10　　　　14　　　　18　　　　22

3　　5　　　　　　11　　13　　　　　　19　　21

4　　　　　　　　 12　　　　　　　　　 20

可以看出规律，输出为5行的时候，每两个完整列之间的下标差为8 = (2 × 5 - 2)；

然后是从第二行到倒数第二行，每两个完整列之间都插入了一个下标，插入的下标与左边列之间的差依次递减2。

代码：

 class Solution {

 public:

     string convert(string s, int nRows) {

         if(s.size() <=  || nRows <= )

             return s;

         string result;

         for(int i = ; i < nRows; ++i)

             for(int j = , idx = i; idx < s.size(); ++j, idx = (*nRows - ) * j + i)  //idx为计算出来的原串下标

             {

                 result.append(, s[idx]);

                 if(i ==  || i == nRows - )   //第一行和最后一行的完整列中间没有插入字符

                     continue;

                 if(idx + *(nRows - i - ) < s.size())     //计算插入的字符，其下标与左边的差

                     result.append(, s[idx + *(nRows - i - )]);

             }

         return result;

     }

 };

巴特西

LeetCode题解——ZigZag Conversion

最新文章

热门文章