题目描述是从上到下,从左到右Z字形排列。
找规律.这种形式一般都是mod x 余数有规律。然后写的时候围绕x构造,而非判断,代码会简单一些。
设行数为r
先观察r=5的情况
发现第0行的字符原始index mod 8 ==0
第1行 mod 8 ==1 或7(-1)
…
第4行 mod 8 == 4 (-4)
也就是mod 2r-2
余0,±1,±2…±r-1
然后直接写就行。
简单写法在于,不判断index,而是直接构造,0+mod,0+mod-1;1+mod,1+mod-1,1+2*mod,1+2*mod-1;…
时间 O(n)
class Solution {
public:
string convert(string s, int numRows) { if (numRows == 1) return s; string ret;
int len = s.length();
int mod = 2 * numRows - 2; for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < len; j += mod) {
ret += s[j + i];
if (i != 0 && i != numRows - 1 && j + mod - i < len)
ret += s[j + mod - i];
}
}
return ret;
}
};
然后看了看题解,还有一种办法是分别构造每行,然后加起来。巧妙之处是设置了up和down,一个个字符判断。但是空间复杂度高一点,然后时间级别虽然一样但是会多一点。
使用当前行和当前方向这两个变量对合适的行进行跟踪。
只有当我们向上移动到最上面的行或向下移动到最下面的行时,当前方向才会发生改变。
class Solution {
public:
string convert(string s, int numRows) { if (numRows == 1) return s; vector<string> rows(min(numRows, int(s.size())));
int curRow = 0;
bool goingDown = false; for (char c : s) {
rows[curRow] += c;
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
} string ret;
for (string row : rows) ret += row;
return ret;
}
};