题目
给定一个字符串, 按照N字型排列成n行, 然后按正常顺序读取出来.
Example:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
思路1
空间复杂度O(n*n)
按照最直接的思路, 将字符串按照规则填入到一个二维数组里, 主要是计算每个字符串在数组的位置.效率较低.
string convert(string s, int numRows) {
int row = 0, col = 0;
int singleCol = numRows - 2 < 0 ? 0 : numRows - 2;
int rowLoop = numRows + singleCol;
vector<string> rows(numRows, "");
for (int i=0; i<s.size(); i++) {
if (i % rowLoop < numRows) {
if (i > 0 && i % rowLoop == 0) {
col++;
}
row = i % rowLoop;
} else {
col++;
row = rowLoop - i % rowLoop;
}
rows[row] += s[i];
}
string result;
for (string row : rows) {
result += row;
}
return result;
}
思路2
根据数学公式, 访问每一行, 计算出每一行的字符在原字符串的位置.
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ret;
int n = s.size();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret += s[j + i];
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret += s[j + cycleLen - i];
}
}
return ret;
}
总结
- 二维数组快速初始化<code>vector<vector<char> > vec(3, vector<char>(4, ' '));</code>
