每天一个小算法：蛇形矩阵

题目描述

给定一个字符串，和一个整数n，将它排列成一个n行的蛇形返回。
示例

1. P   A   H   N
2. A P L S I I G
3. Y   I   R
4. And then read line by line: "PAHNAPLSIIGYIR"
6. Write the code that will take a string and make this conversion given a number of rows:
8. string convert(string s, int numRows);
9. Example 1:
11. Input: s = "PAYPALISHIRING", numRows = 3
12. Output: "PAHNAPLSIIGYIR"
13. Example 2:
15. Input: s = "PAYPALISHIRING", numRows = 4
16. Output: "PINALSIGYAHRPI"
17. Explanation:
19. P     I    N
20. A   L S  I G
21. Y A   H R
22. P     I

复制代码

给定字符串和蛇形排列占据的行数，要求返回重新排列后的串
题目解析

这道题是一道模拟题，题目的要求就是答案，我们只需要读懂题意就很容易实现。
我们最终要输出的是以蛇形摆放之后的字符串再按行串联在一起之后的结果，也就是说每一个字母摆放的列并不重要，重要的是摆放的行号。我们可以很容易想到通过数组维护每一行当中摆放的字母，最后将每一行的结果串联即可。所以问题就只剩下了，我们如何知道每一个字母应该摆放在哪一行？
其实这也是有规律的，我们通过观察样例可以发现，我们每一个字母摆放的行号先是从0递增到n-1，再从n-1递减到0。我们就模拟这个过程，一个字符一个字符的放置即可。
比如字符串是“PAYPALISHIRING ”，rowNum=4。我们可以创建四个空串：
“”
“”
“”
“”
然后我们按照蛇形一个字母一个字母地放进这些空串当中：
当放了第一个字母p之后，变成：
“p”
“”
“”
“”
接着放第二个：
“p”
“a”
“”
“”
接着第三个：
“p”
“a”
“y”
“”
当我们把所有字母都放完了之后，可以得到这样的四个串：
“PIN”
“ALSIG”
“YAHR”
“PI”
然后把这四串拼接在一起就行了。
代码实现

1. class Solution:
2.     def convert(self, s: str, numRows: int) -> str:
3.         # 记录每一行摆放的字母
4.         rows = ['' for _ in range(numRows)]
5.         # 记录当前行号
6.         cur_row = 0
7.         # 记录当前摆放顺序是否从上往下， False代表从下往上
8.         forward = True
9.         # numRows = 1直接返回
10.         if numRows == 1:
11.             return s
12.         
13.         for i, c in enumerate(s):
14.             rows[cur_row] += c
15.             # 根据顺序变更行号
16.             if forward:
17.                 cur_row += 1
18.             else:
19.                 cur_row -= 1
20.             # 根据行号和当前顺序判断需不需要转向
21.             if cur_row == numRows - 1 and forward:
22.                 forward = False
23.             
24.             if cur_row == 0 and not forward:
25.                 forward = True
26.             
27.         ret = ''
28.         for sc in rows:
29.             ret += sc
30.         return ret

复制代码

      

---

            
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。   
        如有问题，可以通过邮件985843242@qq.com联系。欢迎共同交流讨论。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！