题目:
把一个字符串按照Z型排列后打印出来,例如 "PAYPALISHIRING" 重新排列后为3行,即
P A H N
A P L S I I G
Y I R
那么输出为"PAHNAPLSIIGYIR"
解法:
细节实现题,假如重新排列为5行,那么排列后的下标分布应该为
0 8 16 24
1 7 9 15 17 23
2 6 10 14 18 22
3 5 11 13 19 21
4 12 20
可以看出规律,输出为5行的时候,每两个完整列之间的下标差为8 = (2 × 5 - 2);
然后是从第二行到倒数第二行,每两个完整列之间都插入了一个下标,插入的下标与左边列之间的差依次递减2。
代码:
class Solution {
public:
string convert(string s, int nRows) {
if(s.size() <= || nRows <= )
return s; string result;
for(int i = ; i < nRows; ++i)
for(int j = , idx = i; idx < s.size(); ++j, idx = (*nRows - ) * j + i) //idx为计算出来的原串下标
{
result.append(, s[idx]); if(i == || i == nRows - ) //第一行和最后一行的完整列中间没有插入字符
continue; if(idx + *(nRows - i - ) < s.size()) //计算插入的字符,其下标与左边的差
result.append(, s[idx + *(nRows - i - )]);
} return result;
}
};