【LeetCode】6.ZigZag Conversion N型排列问题

本文主要是介绍【LeetCode】6.ZigZag Conversion N型排列问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility).

And then read line by line: "PAHNAPLSIIGYIR".

Write the code that will take a string and make this conversion given a number of rows:

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

理解：

给定一个字符串，将其按照N型排列后，输出按照每一行读取的结果。

分析：

题目中给定的例子并不能很好地解释题目的意思，仍以上面的例子为例，若给定nRows=4，按照N型排列后应该是下面的形状：

返回的结果应该是：PINALSIGYAHRPI 。

若将字符换成它在字符串中的下标，就可以找出一定规律，扫描一遍字符串，便可以得出结果。下标表示如下：

（nRows=3）（nRows=4）

我的做法是可以将字符串按照下面的方式分组，N型排列后的字符串总是按照组的形状重复，除了最后一组可能不是一个完整的组。显然，每一组字符的个数为(nRows+nRows-2) :

（nRows=3）（nRows=4）

第i个字符在它所在组中的顺序可以用 i%(nRows+nRows-2) 表示。可以用一个大小为nRows的字符数组string strs[nRows]来存储每一行的字符，strs[j]即存储排列后第j行的字符，那么这个问题就转化为根据下标将字符放到相应行的string中，最后按顺序将nRows个string连接起来返回最终结果。字符下标与它所在的行有下面这样的规律：

（1）若 i%(nRows+nRows-2)<nRows，s[i]在i%(nRows+nRows-2)行；

（2）若 i%(nRows+nRows-2)>nRows，s[i]在s[i-1]的上一行。

根据这个规律，便可以得到正确结果。需要注意的是(nRows+nRows-2)<=0的情况。

代码：

class Solution {
public:string convert(string s, int numRows) {int n=2*numRows-2;if(n<=0)return s;string strs[numRows];for(int i=0;i<numRows;i++)strs[i]="";int lastRow;for(int i=0;i<s.length();i++){int temp=i%n;if(temp<numRows){strs[temp]+=s[i];lastRow=temp;}else{strs[--lastRow]+=s[i];}}string result="";for(int i=0;i<numRows;i++){result+=strs[i];}return result;}
};