6. Z 字形变换
题目
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);示例 1:输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
知识点
- list的sort的使用，同时根据多个数据排序key=lambda x:(x[3],x[2])
解题
- 在字符串中的位置为s，在二维空间中的位置为（i-横坐标，j-纵坐标），左上角为（0，0）。对numRow=4，行走的坐标依次为
(0, 0)-(0,1)-(0, 2)-(0, 3)-(1, 2)-(2, 1)-(3, 0)-(3, 1)-(3, 2)-(3, 3)-(4, 2)-(5, 1)-(6, 0) - 规律为<u> i不变，j加至numRow，i+1, j-1, j减至0，重复</u>。这样就从s到（i，j）做了映射，dict("L"=(0,0),"E"=(0,1))..
- 读取的时候，直观想法是是从j=0的开始，i一直增加，如果有数就输出。但我觉得不是去判断是不是空格，而是把上面的dict的key，value交换（或者一上来就直接建立坐标到字母的映射），然后按照key进行排序（先排j，j相等的情况下对i排序），然后依次输出
- 简化一下，其实并不需要一个map（如果使用map，结构应该为dict(i=1,j=2,s='L')，然后放到list里面），只需要一个tuple的list就可以了
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
all_words = []
i = 0
j = 0
ss = 0
if numRow <=1:
return s
while ss < len(s):
while ss < len(s) and j < numRows - 1:
all_words.append((i, j, s[ss]))
j += 1
ss += 1
while ss < len(s) and j > 0:
all_words.append((i, j, s[ss]))
j -= 1
i += 1
ss += 1
all_words.sort(key=lambda x: (x[1], x[0]))
return "".join([w[2] for w in all_words])
