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 NA P L S I I GY 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"
.
刚开始并不明白zigzag是什么意思,题目给的是三行的特例,并没有说清楚。去discuss区看了看,发现是要走Z字型。具体链接:https://oj.leetcode.com/discuss/14105/what-does-zigzag-means
这样问题就很清楚了,也很简单。网上很多人是用了nRow个string buffer,其实只要控制好下标,一个buffer足够。稍微麻烦点的就是控制下标了。不过细心点不会很难。代码如下:
string convert(string s, int nRows) { string t; string res; int r, i, j; if (nRows == 1) return s; for (r = 1; r <= nRows; r++) { for (i = r - 1; i < s.size(); i += 2 * nRows - 2) { t += s[i]; j = min(nRows, (int)s.size()) - r; if (j != 0 && j != nRows - 1 && i + j * 2 < s.size()) { t += s[i + j * 2]; } } if (t.size()) { res.append(t); t.clear(); } } return res; }
运行时间也很不错,接近最前面了。不过这不能说明任何问题……
做这个题主要就是要在纸上画,理清下标的关系,充分打草稿之后再写,正确率就很高。再次说明写程序不能直接上手写,虽然很爽,但是效率很低。
理清思路,选择数据结构,确定数学模型之后再写,会有效的多。