
题目:
The string "PAYPALISHIRING"
is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3)
should return "PAHNAPLSIIGYIR"
.
代码:
看了半天,都没怎看懂题目。查了一下,原来:
Zigzag:即循环对角线结构(
0 | 8 | 16 | |||||||||
1 | 7 | 9 | 15 | 17 | |||||||
2 | 6 | 10 | 14 | 18 | |||||||
3 | 5 | 11 | 13 | 19 | |||||||
4 | 12 | 20 |
)
这样子的话,就不算麻烦了,只要正确的字符串操作,把每个元素加在正确的位置就好。
于是,共有numRows行,所以定义一个保护numRows元素的数组,用来保存每一行的字符串。
观察规律,第一列从0写到numRows-1,之后从后往前,及numRows-2到0开始逐渐添加。输出并不需要考虑宽度,所以对字符串来说,之后往后加就好
//凑了半天,总算凑出来了
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
i = 0
j = 0
gap = numRows-2
temp= ['' for x in range(numRows)]
while i<len(s):
while(j<numRows):
if(i>=len(s)):break
temp[j] += str(s[i])
j += 1
i += 1
j=gap
while(j>0):
if(i>=len(s)):break
temp[j] += str(s[i])
j -= 1
i += 1
result = ''
for y in temp:result += y
return result
//网上查的,好像更直观
def convert2(self, s, nRows):
if nRows==1: return s
tmp=['' for i in range(nRows)]
index=-1; step=1
for i in range(len(s)):
index+=step
if index==nRows:
index-=2; step=-1
elif index==-1:
index=1; step=1
tmp[index]+=str(s[i])
return ''.join(tmp)
测试了多次,两个速度差不多,必定时间复杂度和空间复杂度都一样:
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAOkAAABLCAIAAAAagTdRAAAGDElEQVR4nO1c3dGjMAykrhREPVRDMynmu4cEkKWVLZnMHJrZfbpThPXjxXFgPy9/BFETy/9OgCAmQe4SVUHuElVB7hJVMeLue3stH7y292Hc1+XEuivXy6CcrwGMpxxQjnrZ5ag20JXlICUvECwzmLx7udOQ4wObf+OJmixsZ6Bw7RkjCjTMUxcaKhO2Lmbsc3dfm9n9/HNfr+j7+h3o84/L6QrXksHzNA4yooiDL4ejhQP9vbeXqPJIOJy81yUn+r4ur3XVtdkxbZMviNzitceNMBDyxHMULxN2HhpBk7vcFdmIe8iU01Zq+gKH7jbL3iN6qAh3w4EkrhaFk8dd8oJ4XAEVOU1W3tna40b4gakdz1GwTAFBTmBETe5x94yzr8vy2rY2Ne9borkpX9t+rPRt/70aRI7qThtxF33HxQJB73DynS7Z6Og7xc0TNfn4hjZ7mHDtQaMNhDydOUqVGUkLNnnMXUP99/Za5EDuutswrr9wYuv7os4WufxPJpcJ9IW89cPJO11Cca5VKrTuOk02qeZqz627JhDaFqo5SpTZK8duE1STR3uGpVmq111FVzHBuit/4A2+5dEG03H3e60HiQbSEx9PHnYJeMoF0i6U/j7SnVi4kxje4UnuxhYd8UmmzNM0vA9Rk4e/1cw3eO/njD9zgbbCKYIXdzo4+CpwAqH2xZPH+5xunqMFqddkHTNV+8y6Ox7Ty3K87oaIq/I4mjzzjEzeWUcE/fBJboLCnmC71l7rXS7CXGOEA5mVYip5Fd7xFCH7Yw6aDGdjUPuUcTAmnKNwmbDz4+kIPSMjiOeC3CWqgtwlqoLcJaqC3CWqgtwlqoLcJapiSgMZ94wbD6t6+28fM0pv9XJLP2m0gTwNpPwIqAuHyYfVktiTmMGEBjLumTIGlXhHNK2vk29Qe8rGNmehIwRyR5snHtO5PCgKJSYxoYEMe8aNX3S526yQihaCElAf5ilXvjbnBWu/9gm1ZM+TSGNSAxnxjBvNMCeAEs/T1zmyTDyu5qaROw5rb9bioNSz50mkMaGBjHrGje0wKIC8AGxiLvEGUAwOFt3v1UruOKh9Si3Z9STSyGsg455x4xdDJZ6jr/MVg1CmpHedbyR39PPUY8LLYUU9TyKNvAby/ET/33rGjR/ElXits/O7CRMXLMRwKJznPbVkx5NIY/IZGfj5cusZWVyJ18QDT8OQgtHYodC0dYN5/lItyUX3LvhugqgKcpeoCnKXqApyl6gKcpeoCnKXqApyl6gKngPplxlM3r3caYgjQtKeqMnoiXe49ozRebTezxO9eB+WeeO1AM+B/LutbEyqOoGAE45pm3xBvT2M1R43wkDIE89RvEzYeWgETeY5kC0mlI05VafHFVBRR9WpXi5nao8b4QemdjxHwTIFkGSq0WCZJvMcSKeAcPKdLtnonoAT5omabEWh2dqDRqA+BZ7OHKXKjKQFm8xzIAWmlI1Ol1AcLOD0S8dNNqnmas+tu0O9FJijRJm9cuw2QTWZ50AKm0owmHxU1SkXSLtQ+vtId2LhTmJ4hye5G1t0xCeZMk/T8D5ETeY5kIcTamks+QlV52hB6jVZx0zVPrPujsf0shyvuyHiqjyOJvMcSLAgTiWvwjueImR/zEGT4WwMap8yDsaEcxQuE3Z+PB2hZ2QE8VyQu0RVkLtEVZC7RFWQu0RVkLtEVZC7RFU8+hxIbMQKzMtbvfHSftB4M/mwsf9n+0QKTz4HMikOVKI79Vz8VDta493k32Eh34XO+28iiOefAwneMyNxoCE6lOd5xh8kfwzZ1ZT0SyVSePg5kNhoxYFAdAflecj4o+SDBXjaQiKN558DCdZdSaDvH22gnc254ZQ0s8YfJZ9YdHt2IoznnwNpBVZyv7use190Fxj4F8mH9VCyZVx7b+H550CmxIHuCN0fS3eTzxOX1P0BipwDKfa3SBzYJHEYoTzP0ezdST4h5OMjsl+C7yaIqiB3iaogd4mqIHeJqiB3iaogd4mqIHeJqiB3iaogd4mqIHeJqiB3iaogd4mqIHeJqiB3iaogd4mqIHeJqiB3iar4B2VahtoPv4pdAAAAAElFTkSuQmCC" alt="" />
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKQAAABDCAIAAACdljksAAAFOklEQVR4nO1bS5ajMAzkXByI83CR2XKZHIZZdAf0qZIFk0nntVSrPEeWZJdtsAtPfxplMO2NMmiyC6HJLoQmuxCa7EJosgtBk/1Y5+kL8/p4Fm7LdGDZjOlZIM2k7Vl+2oLqIrb6A6Yk3Z7F3ierjizFH0e5aNNRneSJfWYLUSCc0pVmWkiyt+Vw8Vjn75/botr+5evrx2nk8LSUJkdtXB16e6yzyOjZEPlbRzROWItI8tsyzcuCGiUiwjxZ9GQhDARTYl0HeslDkH2SIUeTqC4MDiuasR8qtn6GbIGTOJsHjMxbxMJFNIjSIE82XpOFrAHemOcghrfHSfbhYFumaV5X0aPfi4x1wkKKPjZTa0Q2W8qU9WOd53V7WmtT5TNokU8erUVn0/3DAuX5L2T7QCwl5jP8Y993T/bBjowku2w4sxmHtrfjjEFXPEvUqIlWC9IiFP1cgUhWaMa4PF8ws3eZLk3pQpISehmf1LK3bMatcYZCBg8Na84brJ3YPn2ssx7+NCXYImCp37nw4oKeHbaxryBbLN08JVAdzBAH84Lmlt/ovQiE5GPLjwLaYLmEoDaYB2iQEn6ghNH5pHFc55a66zMbvY/HMzvD9J7ZeskxJt4JFfi74FkbPAhVdRGHbHN0oHxKximxBP0IN0QoT+zzVmH4uoKrs14akN341WiyC6HJLoQmuxCa7EJosguhyS4Ee4KW2a5Ze7CDZdvCadnCQBmflyxBod6WhnvqCwAbehzoB8FmdqAs7Ts9PtFCXMrnWZj3mbXE1QfyWqwSEkAtdaTjvR2Y7ITciA4PqZpJfYrCvM+0Ja6eIButAsn+MOrw55M9mNZYZIzUTOZTd1LSZ94Sp8Q0Si8ywg83cH8gLXUg2r4fgOzxgCQiI1czE2pA3ueV6EFKz39dWkoEkpCaiioKtVQe6O1wZGceWZHIeDgxcuJIH8z7vBp9UMjXm9ECp2pQLTUI9G5YsrFGuS36oRWIjKAI+nSFeZ/XovNCr1E+S/2zYYBAS+WB3g4vcRKNjX7OCD4BcJa5zr/mM2M5KMQapdXHc4/deOv1AUzvfahSCk12ITTZhdBkF0KTXQhNdiE02YXQtzhBB6hbEcHuOe6QK4WBwOoOOfLNtOhbnMZH3+KUHOnEaMZ+qIT3slKyqmILGmknuEUsXESDOaEleV47lB90XZQSzyE84e1bnCZpsDbAhwXK81/I9oFYSsxn+Me+732L8/QfT1w0Y1yeL5jZu0yXpnQhSYm+xbmLASmA3wnixr6CbLF085RAdTBDHPoWJ8gTTxr0KdTVTzRG0ZMfdKF5M2J671uck+0ks3/As8oVQp+3CsPXFVyd9dKA7MavRpNdCE12ITTZhdBkF0KTXQhNdiHcvcWJduTx57hDSQ5XhwIrVPSyhXpbqo4HMy3PdwgJ9HO4d4tzoKk5peyaJKerSzaO2za+OlQzoSU8vcpe6yJg0T+B4hP3bnEKMIXATeS8JIePQ9nNQKdyODXTBKLnlyAQOKojrSDq8OeTfWFoA+Vh8md+efkWVCcCq6oeqpkmENUoXaDsdCfRB6Lt+3HrFucBpnskVYdx9UBgBWsnUTNpIKEfoED2zFlqKqpoED0tVPxv3LrFeRjSBsQfpaSrc4HVVudqZhToaCwMlF/gIi1VB/pR3LvFORqqow+YstWJwIqqB5/H0EB6EvtAo48BRtFBoB/FrVucWFODW6e8JId3XkBgHeue+mXJWkKNEiq5Vx678dbrA5je+1ClFJrsQmiyC6HJLoQmuxCa7EJosgvhLyYpRHTceeTqAAAAAElFTkSuQmCC" alt="" />