LeetCode| ZigZag Conversion

题目

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: string convert(string text, int nRows); convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

解题思路

给定一个字符串，可以先按规律将字符串中的字符挨个放入一个二维字符数组，然后逐行读出。模拟过程如下： s=”abcdef” numRows = 3 逐行读出：aebdfc 但是这样处理起来比较繁琐，时间复杂度也不是很优，其实我们可以发现，对于一个字符串，在给定行数n的情况下 ，其每个字符对应行号为：1、2、3、……、n-2、n-1、n、n-1、n-2、……、3、2、1、2、3、……所以只需要遍历一次字符串，就可以得到zigzag每行对应字符串，然后再按行读出就行了,时间复杂度为O（n）。

AC代码

class Solution { public: string convert(string s, int numRows) { if(numRows == 1 || s == "") return s; string strs[numRows], ans = ""; //strs用于存放每行字符串 for(int i = 0, addr = 0, asc = 1; i < s.length(); ++i) { if(asc) strs[addr++] += s[i];//行序递增 else strs[addr--] += s[i];//行序递减 if(addr == numRows) addr -= 2, asc = 0;//达到上界 if(addr == -1) addr += 2, asc = 1;//达到下界 } for(int i = 0; i < numRows; ++i) ans += strs[i];//按行取出字符串 return ans; } };

经1158组数据测试，运行时间26ms。