力扣(LeetCode)6. Z 字形变换(C++)

数学构造

$Z$ 字形变换类似情报加密。找规律解密，就能得到构造的方法。

第 $0$ 行相邻的数，取 $n=4$ 如上图，观察第 $0$ 行和第 $3$ 行
相邻的数，组成等差数列，公差 $d=6=2n-2$
$2n-2$ 是说 ， 第 $1$ 列有 $n$ 个数 ， 第 $1$ 列到下一次变换的开头之间有 $n-2$ 个数 ， 总共 $2n-2$ 个数。

对于第 $1$ 行或者第 $2$ 行 $d=2n-2$ , 但是每行有两个等差数列，两个等差数列首项的关系是 $num2=d-num1$ 。

对于一般的 $n$ 行 $Z$ 字形变换，有
用 $ans$ 保存答案 ， 对于第 $i$ 行，其中 $i=0||i=n-1$

	for(int j = i;j<s.size();j+=d)
		ans += s[j];
1
2

对于 $i>0\&\&i<n-1$

	for(int j = i,k = d - j;j<s.size();j+=d,k+=d){
        ans+=s[j];
        if(k<s.size()) ans+=s[k];
    }
1
2
3
4

代码展示

class Solution {
public:
    string convert(string s, int n) {
        if(1==n) return s;
        string ans;
        int d = 2*n-2;//公差
        for(int i = 0;i<n;i++){
            if(0==i||n-1==i){
                for(int j = i;j<s.size();j+=d)
                    ans += s[j];
            }else{
                for(int j = i,k = d - j;j<s.size();j+=d,k+=d){
                    ans+=s[j];
                    if(k<s.size()) ans+=s[k];
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(m)$， $m$ 是 $s$ 的长度 。 构造 $Z$ 字形的过程只遍历每个字符一次，时间复杂度 $O(m)$ 。
2. 空间复杂度: $O(1)$，除答案占用的空间，没有使用额外的线性空间 。