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 text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
思路：
我自己是先用vector把每一行的字母都存下来，再按行读取
string convert(string s, int nRows) { string ans = s; if(nRows == 1) return ans; //只有一行的特殊对待 没有向上和向下的区别 vector<vector<char>> v(nRows); int z = 0; bool add = true; for(int i = 0; i < s.length(); i++) { if(add) //当前行数在增加 { v[z++].push_back(s[i]); if(z == nRows) { add = false; z = nRows - 2; } } else //当前行数在下降 { v[z--].push_back(s[i]); if(z < 0) { add = true; z = 1; } } } //写入答案 int p = 0; for(int i = 0; i < nRows; i++) { for(int j = 0; j < v[i].size(); j++) { ans[p++] = v[i][j]; } } return ans; }
开始也想了数学的方式，但自己没想清楚。看看别人写的数学方法：
class Solution { public: string convert(string s, int nRows) { if(s.empty()||nRows<2) return s; vector<string> zig(nRows); bool down = true; for(int i = 0; i < s.size(); ++i) { int row = i%(nRows - 1); if(down) zig[row].push_back(s[i]); else zig[nRows - 1 - row].push_back(s[i]); if(row==nRows - 2) down = !down; } string res; for(auto& temp: zig) res += temp; return res; } };
原文：http://www.cnblogs.com/dplearning/p/4270944.html