首页 > 代码库 > [LeetCode]ZigZag Conversion
[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)
P A H N A P L S I I G Y I RAnd 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"
.class Solution { public: string convert(string s, int nRows) { if(s.size() <= 1 || nRows == 1) { return s; } int totalCol = (s.size() + 2 * nRows - 1)/(2 * nRows - 2) * (nRows - 1); char **rct = new char* [nRows]; //std::vector< std::vector<char> > rct; for (int i = 0; i < nRows; i++) { rct[i] = new char[totalCol]; for (int j = 0; j < totalCol; j++) { rct[i][j] = ‘ ‘; } } //char rct[10][10]; int col = 0; for (int i = 0; i < s.size(); i++) { /*int col = i / (2 * nRows - 2);*/ if (i % (2 * nRows - 2) == 0 ) { int R = 0; while(i < s.size() && R < nRows) { //第col列先赋值 rct[R][col] = s[i]; R++; i = i++; //对第col++列赋值 if (R == nRows - 1) { while(R > 0 && i < s.size()) { rct[R][col] = s[i]; i = i++; R--; col++; } } //R又回到0,跳出 if (R == 0) { i--; break; } } } } std::string ans; for (int i = 0; i < nRows; i++) { for (int j = 0; j < totalCol; j++) { if (rct[i][j] != ‘ ‘) { ans += rct[i][j]; } } } for (int i = 0; i < nRows; i++) { delete[] rct[i]; rct[i] = NULL; } delete[] rct; rct = NULL; return ans; } };
网上看到的简洁代码:
题意的 "z" 字形指一列nRows个,然后斜着往右上一格一个回到第一行,然后再一列nRows个。比如nRows=5,如下:
1 | 9 | 17 | 25 | |||||||||||
2 | 8 | 10 | 16 | 18 | 24 | 26 | ||||||||
3 | 7 | 11 | 15 | 19 | 23 | 27 | … | |||||||
4 | 6 | 12 | 14 | 20 | 22 | 28 | 30 | |||||||
5 | 13 | 21 | 29 |
每行字母在原字符串中的间隔是有规律的,虽然两层for循环,但是s中每个字母只访问了一次,O(n)。
class Solution { public: string convert(string s, int nRows) { if(nRows == 1) return s; string ans; int a = (nRows << 1) - 2, b = 0; for(int i = 0; i < nRows; i ++, a -= 2, b += 2) { bool flag = false; for(int j = i; j < s.length(); j += flag ? (b ? b : a) : (a ? a : b), flag ^= 1) ans += s[j]; } return ans; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。