
代码思路分析:Z 字形变换
1. 边界情况处理
if (r == 1 || r >= n) return s;
r == 1
:只有一行,直接返回原字符串(无需变换)。r >= n
:行数大于等于字符串长度,每行只有一个字符,直接返回原字符串。
2. 计算周期和列数
int t = r * 2 - 2;
int c = (n + t - 1) / t * (r - 1);
- 周期
t
:
- 一个完整的 Z 字形周期包括:向下走
r
行(占 r-1
列) + 向右上走 r-2
行(占 r-1
列)。 - 公式:
t = r + (r - 2) = 2r - 2
。
- 总列数
c
:
- 周期数 =
ceil(n / t)
,用整数运算表示为 (n + t - 1) / t
。 - 每周期占
r-1
列,因此总列数 c = 周期数 × (r - 1)
。
3. 初始化二维矩阵
vector<string> nums(r, string(c, 0));
- 创建一个
r
行 c
列的矩阵,用 0
初始化(后续用 char
填充时,0
表示空字符)。
4. 填充矩阵(Z 字形遍历)
for (int i = 0, x = 0, y = 0; i < n; i++) {nums[x][y] = s[i]; if (i % t < r - 1) { x++;} else { x--;y++;}
}
- 坐标
(x, y)
:
- 移动逻辑:
- 向下移动:当
i % t < r - 1
时,x++
(行增加)。 - 向右上移动:否则,
x--
(行减少),y++
(列增加)。
5. 按行拼接结果
string ans;
for (auto &row : nums) { for (char ch : row) { if (ch) ans += ch; }
}
return ans;
- 按行优先顺序遍历矩阵,跳过空字符(
0
),拼接非空字符。
class Solution {
public:string convert(string s, int numRows) {int n=s.size(),r=numRows;if(r==1||r>=n)return s;int t=r*2-2;int c=(n+t-1)/t*(r-1);vector<string> nums(r,string(c,0));for(int i=0,x=0,y=0;i<n;i++){nums[x][y]=s[i];if(i%t<r-1){x++;}else{x--;y++;}}string ans;for(auto x:nums){for(char ch:x){if(ch){ans+=ch;}}}return ans;}
};