6. Z 字形变换

题目

image-20240915213511577

题解

在进入思考状态后，这个对应的公式转换是可以被求出来的，只是因为代码实践上的差异，自己第一次写的时候没能得出正确答案。

常规的解法还是很简单的使用相应的举着进行模拟即可，只是没有什么挑战可言，并且在时间和空间复杂度上也不是很让人满意。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {  
public:  
    string convert(string s, int numRows) {  
        if (numRows == 1 || numRows >= s.length()) {  
            // 如果numRows为1或者大于字符串长度，则无需转换  
            return s;  
        }  
  
        string result = "";  
        int cycleLen = 2 * numRows - 2; // 一个完整Z字形周期的长度  
  
        // 处理第一行和最后一行  
        for (int i = 0; i < numRows; ++i) {  
            // 第一个字符的索引  
            int index = i;  
            // 当index小于字符串长度时，继续添加字符  
            while (index < s.length()) {  
                result += s[index];  
                // 对于非第一行和最后一行，需要添加下降过程中的字符  
                if (i != 0 && i != numRows - 1 && index + cycleLen - 2 * i < s.length()) {  
                    result += s[index + cycleLen - 2 * i];   //要减去 2* i的操作是因为index有相应的i进位，这个时候加上完整Z字形周期长度就超过了本Z字形长度周期
                }  
                // 移到下一个周期  
                index += cycleLen;  
            }  
        }  
  
        return result;  
    }  
};

错误代码

可以看出，下面的代码是已经得出的转化公式，只是在跑while循环的时候对循环终止条件把握不好。

在最开始还过多考虑了给定s可以组成的特定结果的个数，不够组成的部分还有多少这样的问题

在正确的代码中，使用 index < s.length()，成功消除了这部分的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
string StringTopic::convert(string s, int numRows)
{
	//Z字变换
	int n = s.length(), num = 2 * numRows - 2;
	int count = n / num; //主要是看能完成的组成多少个给定结构
	int left = count % num;//如果有剩下的，就单独组一个

	string res;

	//逐级添加给定内容
	for (int i = 0; i <= numRows; ++i)
	{
		//准备对补充一行的字符串
		int idx = i;
		while (idx <= num * i +i || idx < num * (i+1) - i)
		{
			int val1 = num * i + 1, val2 = num * (i + 1) - i;
			res += s[val1];
            
            //循环条件把握不好
			if (i != 0 || i != numRows)
			{
				res += s[val2];
			}

			idx += num;
		}
	}

	return res;
}