算法描述:
- 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 = 3
- Output: "PAHNAPLSIIGYIR"
- Example 2:
- Input: s = "PAYPALISHIRING", numRows = 4
- Output: "PINALSIGYAHRPI"
- Explanation:
- P I N
- A L S I G
- Y A H R
- P I
解题思路:
对于这个题目, 网上查了很久, 终于找到一个比较好的解题思路.
以 Example2 为例, 从 P 到 I 的距离为 2*numRows -2 = 6. 也就是说每六个元素为一个循环, 因此可以为 6 取模作为元素所在行的索引. 其中, 对于索引值小于 numRows 的直接用索引值作为行号, 而大于等于的值则采用补数作为索引值.
- string convert(string s, int numRows) {
- if(numRows <=1) return s;
- string results;
- vector<string> str(numRows,"");
- for(int i =0; i < s.size(); i++){
- int index = i % (2*numRows -2);
- index = index < numRows? index : 2*numRows -2 - index;
- str[index] += s[i];
- }
- for(int i=0; i < numRows; i++) results += str[i];
- return results;
- }
- 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 = 3
- Output: "PAHNAPLSIIGYIR"
- Example 2:
- Input: s = "PAYPALISHIRING", numRows = 4
- Output: "PINALSIGYAHRPI"
- Explanation:
- P I N
- A L S I G
- Y A H R
- P I
来源: http://www.bubuko.com/infodetail-2935739.html