Type：medium
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)
P? A? H? N
A P L S I I G
Y? I? R
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 s, int numRows);
Example 1:
Input:s = "PAYPALISHIRING", numRows = 3Output:"PAHNAPLSIIGYIR"
Example 2:
Input:s = "PAYPALISHIRING", numRows =?4Output:"PINALSIGYAHRPI"Explanation:P? ? I? ? NA? L S? I GY A? H RP? ? I
本題題意為輸入一個數(shù)字和字符串胀莹，將字符串按照zigzag方式寫成numRows行的新字符串，并按照從上至下從左到右的順序輸出該新字符串。
本題使用暴力做法克饶，記錄每個字符出現(xiàn)的位置魂莫，直接輸出维苔。
因此尋找位置表達方式：
P? ? ? ?? A? ?? ? ?H? ? ? ? ?N
A? ??P? ?L? S? ? I? ? ?I? ? G
Y?? ? ? ? ?I? ? ? ? ?R
如圖所示蹲嚣，設行數(shù)為n车摄，可以將標記的2n-2個字符視為一次循環(huán)，size = 2n - 2奏寨。
設遍歷時行數(shù)為i起意，則在輸出第i行時，首先令j = i病瞳，輸出s[j]揽咕，接下來判斷i是否為第0行或最后一行，若是的話直接輸出s[j+size]套菜，將j+size賦為新的j值以此類推亲善；若不是第0行或最后一行，則要首先輸出s[j+size-2i]逗柴，接下來再輸出s[j+size]即可蛹头，然后同上，再次循環(huán)嚎于。將按順序讀取的所有的字符存在新的字符串中掘而，并輸出這個新的字符串。
本題難點在于在此環(huán)境中于购，c++語言無法直接push_back袍睡。因此直接開string ret，不能開大小肋僧，ret可以用ret += s[j]來賦值斑胜。
附代碼：
class Solution {
public:
? ? string convert(string s, int numRows) {
? ? ? ? int n = s.length();
? ? ? ? if(numRows == 1) return s;
? ? ? ? int size = 2 * numRows - 2;
? ? ? ? string ret;
? ? ? ? for(int i=0; i<numRows; i++){
? ? ? ? ? ? for(int j=i; j<n; j+=size){
? ? ? ? ? ? ? ? ret += s[j];
? ? ? ? ? ? ? ? if(i != 0 && i != numRows-1){
? ? ? ? ? ? ? ? ? ? int temp = j + size - 2 * i;
? ? ? ? ? ? ? ? ? ? if(temp < n) ret += s[temp];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return ret;
? ? }
};
