【算法day7】 Z 字形变动 （O2算法思路整理）

Z 字形变动，算法思路整理
https://leetcode.cn/problems/zigzag-conversion/
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右举行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
请你实现这个将字符串举行指定行数变动的函数：

• 不擅长打印图形，我将把所有矩阵和一维坐标的映射关系都学习一遍
  

1. class Solution {
2. public:
3.     string convert(string s, int numRows) {
4.         int s_len = s.size();
5.         if (s_len <= numRows || s_len <= 1||numRows==1) {
6.             return s;
7.         }
8.         int T = numRows + numRows - 2;
9.         int T_length = 1 + numRows - 2;
10.         
11.         int T_num = s.size() / T + 1;
12.         int numCols = T_num * T_length;
13.         vector<vector<char>> ch(numRows, vector<char>(numCols));
15.         int index_s = 0;
16.         for (int i = 0; i < numCols; i++) {
17.             for (int j = 0; j < numRows; j++) {
18.                 if (index_s == s_len)
19.                     break;
20.                 if (index_s % T < numRows) {
21.                     ch[j][i] = s[index_s];
22.                     index_s++;
23.                 } else {
24.                     // 向着右上移动,右上移动时的（x,y）坐标Y正好随着周期变化
25.                     int row_id = numRows - i % T_length - 1;
26.                     ch[row_id][i] = s[index_s];
27.                     index_s++;
28.                     break;
29.                 }
30.             }
31.         }
32.         string ans;
33.         for (auto c_line : ch) {
34.             for (auto c : c_line) {
35.                 if (c)
36.                     ans += c;
37.             }
38.         }
39.         return ans;
40.     }
41. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。