yxc题解

分析

算法
(找规律) O(n)
这种按某种形状打印字符的题目，一般通过手画小图找规律来做。
我们先画行数是4的情况：

0     6       12
1   5 7    11 ..
2 4   8 10
3     9

从中我们发现，对于行数是 n 的情况：

对于第一行和最后一行，是公差为 2(n−1) 的等差数列，首项是 0 和 n−1；
对于第 i 行(0<i<n−1)，是两个公差为 2(n−1) 的等差数列交替排列，首项分别是 i 和 2n−i−2；
所以我们可以从上到下，依次打印每行的字符。

时间复杂度分析：每个字符遍历一遍，所以时间复杂度是O(n).

class Solution {
public:
    string convert(string s, int n) {
         string res;
         if (n == 1) return s;
         for (int i = 0; i <= n - 1; i ++) {
             if (i == 0 || i == n - 1) {
                for (int j = i; j < s.size(); j += 2 * n - 2) res += s[j]; // j从i开始，不是从0开始
             } else { // 下面j从i开始，不是从0开始
                 for (int j = i, k = 2 * n - 2 - j; j < s.size() || k < s.size(); j += 2 * n - 2, k += 2 * n - 2) {
                     if (j < s.size()) res += s[j];
                     if (k < s.size()) res += s[k];
                 }
             }
         }
         return res;
    }
};