
代碼思路分析: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;}
};