LeetCode 6. ZigZag Conversion & 字符串

时间:2021-12-20 07:22:38

ZigZag Conversion

看了三遍题目才懂,都有点怀疑自己是不是够聪明...

LeetCode 6. ZigZag Conversion & 字符串

就是排成这个样子啦,然后从左往右逐行读取返回。

这题看起来很简单,做起来,应该也很简单。

通过位置计算行数:

P     I    N
A L S I G
Y A H R
P I
0,0 1,1 2,2 3,3 4,2 5,1 6,0 (期望)

用简单的先思考:

P   A   H   N
A P L S I I G
Y I R
0,0 1,1 2,2 3,3 4,0 %4 (3+1)可以解决正常的
3,1(期望) 特殊的3(2行2排的P,用1- (%4-row) )

这里(3+1)以及1- (%4-row)中的1作为取余底数的延长

找某个键所在行数

# find k in line
def findLine(k,rows): # 延长,去掉斜路两头
prolong=rows-2 # 取模底
modulo=rows+prolong
print(modulo,prolong+1,k%modulo,(k%modulo-rows+1)%(prolong+1),(k%modulo) if (k%modulo)<rows else prolong-(k%modulo-rows))
return (k%modulo) if (k%modulo)<rows else prolong-(k%modulo-rows+1)%(prolong+1)
第1次提交
class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
zigzag='' # each line add 'c' to zigzag string.
for n in range(numRows):
for k,c in enumerate(s):
#print(k,c,end=" ")
if findLine(k,numRows) == n:
zigzag=zigzag+c return zigzag
# find k in line
def findLine(k,rows): # 延长,去掉斜路两头
prolong=rows-2 # 取模底
modulo=rows+prolong
#print(modulo,prolong+1,k%modulo,(k%modulo-rows+1)%(prolong+1),(k%modulo) if (k%modulo)<rows else prolong-(k%modulo-rows))
return (k%modulo) if (k%modulo)<rows else prolong-(k%modulo-rows) if __name__ == "__main__": data = [
{
"input":{
's':'PAYPALISHIRING',
'numRows':4
},
"output":"PINALSIGYAHRPI",
},{
"input":{
's':'PAYPALISHIRING',
'numRows':3
},
"output":"PAHNAPLSIIGYIR",
}, ];
for d in data:
print(d['input']['s'],d['input']['numRows'])
result=Solution().convert(d['input']['s'],d['input']['numRows'])
print(result)
if result==d['output']:
print("--- ok ---")
else:
print("--- error ---")

Runtime Error:

Runtime Error Message:
Line 27: ZeroDivisionError: integer division or modulo by zero
Last executed input:
"A"
1

粗心+1,findLine()函数里没有检验值的有效性。

第2次提交
# find k in line
def findLine(k,rows):
# 延长,去掉斜路两头
prolong=rows-2 # 取模底
modulo=rows+prolong # validity check
if prolong<0:
prolong=0
if modulo<=0:
modulo=1 #print(modulo,prolong+1,k%modulo,(k%modulo-rows+1)%(prolong+1),(k%modulo) if (k%modulo)<rows else prolong-(k%modulo-rows))
return (k%modulo) if (k%modulo)<rows else prolong-(k%modulo-rows)

Time Limit Exceeded:

"kvzeeubynglxfdedshtpobqsdhufkzgwuhaabdzrlkosnuxibrxssnkxuhcggkecshdvkcmymdqbxolbfjtzyfwtmbbungzfpcbbgpzusqxqejrlsmkqtglijpcxxbcmffnlvnfpddfjmyugkeyemkmyzqvwszkxfxlckqrpvzyjxupkyoonaclbsgzmhjmogxstpkilljwidoseeitemefhmgtvpfkxecquobhzkfkptetxpmdbskigqecflmdqqvmfwveiaqyuvrtkgxlyhwhyalfnzifpgrucoblprjloceykbkjlisjkdoxczdtfwqjlrwckhnzkrxuvjfgtzrdchdgiicneszrlvtxdiwncwjxhrfbqygvfjdorfdyzcrkylidvgqxebwmubplzxihjlvataasdsfdfngavyyabuowyfhzcpglcdoxeoqjivmnkuofsohtivpiayifpoquugryvjjfgvtqrjyjxhefdwqfwykmodiijzigjrmpohifqiqnpvuutkcpiodzrljdlslwlxnagxhwfylxvgtosvfdkjcdulihfudrtrtaoaywakvvqolkmtnycpdwdmeigjbbcubrxapxmkveaiombckftocwaifitgjwdnpapezbqwhqhvdizpotdspfcwpxfbtiqikfolieipxpmazmrphxjyenvulcxeknpwsfhckptjgflitczczjbeyyajaxqmkhiempgyfzhngsvcvxewghcgfcqhzitlpbpbrvaywjlfcjhzgnxoxauecmmeufpljfpacrazaneewndecbuzbrgffsjczznieckitkhwynawcgdfjzgmqmrygbaicpqiudqpnylnnoksupzdofphuifcjhknydvsgmivmvjbjttdksiyazhuimytvjhuocmuqwpcsyedtzjdsresrlozamsvxbrlegfucxzwxfcrelwyeaqvoewotrlssdeyjltnkumibozfzxe"
200

超时了,加一个时钟本地看看时间:

运行时间
PAYPALISHIRING 4
PINALSIGYAHRPI
--- ok --- -3.590000000000017e-05
PAYPALISHIRING 3
PAHNAPLSIIGYIR
--- ok --- -2.6699999999999294e-05
A 1
A
--- ok --- -8.399999999998686e-06
kvzeeubynglxfdedshtpobqsdhufkzgwuhaabdzrlkosnuxibrxssnkxuhcggkecshdvkcmymdqbxolbfjtzyfwtmbbungzfpcbbgpzusqxqejrlsmkqtglijpcxxbcmffnlvnfpddfjmyugkeyemkmyzqvwszkxfxlckqrpvzyjxupkyoonaclbsgzmhjmogxstpkilljwidoseeitemefhmgtvpfkxecquobhzkfkptetxpmdbskigqecflmdqqvmfwveiaqyuvrtkgxlyhwhyalfnzifpgrucoblprjloceykbkjlisjkdoxczdtfwqjlrwckhnzkrxuvjfgtzrdchdgiicneszrlvtxdiwncwjxhrfbqygvfjdorfdyzcrkylidvgqxebwmubplzxihjlvataasdsfdfngavyyabuowyfhzcpglcdoxeoqjivmnkuofsohtivpiayifpoquugryvjjfgvtqrjyjxhefdwqfwykmodiijzigjrmpohifqiqnpvuutkcpiodzrljdlslwlxnagxhwfylxvgtosvfdkjcdulihfudrtrtaoaywakvvqolkmtnycpdwdmeigjbbcubrxapxmkveaiombckftocwaifitgjwdnpapezbqwhqhvdizpotdspfcwpxfbtiqikfolieipxpmazmrphxjyenvulcxeknpwsfhckptjgflitczczjbeyyajaxqmkhiempgyfzhngsvcvxewghcgfcqhzitlpbpbrvaywjlfcjhzgnxoxauecmmeufpljfpacrazaneewndecbuzbrgffsjczznieckitkhwynawcgdfjzgmqmrygbaicpqiudqpnylnnoksupzdofphuifcjhknydvsgmivmvjbjttdksiyazhuimytvjhuocmuqwpcsyedtzjdsresrlozamsvxbrlegfucxzwxfcrelwyeaqvoewotrlssdeyjltnkumibozfzxe 200
kmavwupczbbfreepjaexllzuqzpabgxfnyviuendheegijmwlllmnxyvcdfkaeedrtucecaabdzaxusysozhddxbtfsnrprfggoodzfbdfhfqjnjssfgcjdvafchgvlzuyyjzfqywnkbayizfbaegruvcwhorkuxwbihjyptawfbkachphbnzlwdwctyzipinrdgzalxlhwktcqcovdcgslofdnrxgfuzecjxsohzieqggbnjwmrcieqxivxmsimvrsgncyndkvgkhusbxcogaudfnihrshcczozpgthfqggtyikfiguejvpdcvpmqsuiephxaindryhyvkiklkzfmncnpqnmhoxoykqakmcujsdwuauqrgypblryzxjyedoqvbolwjjfbfjzpftfchjdgzutzvcizcttfyxqicforljwdjfhtkygkmjjjnbsxtybihpdulekvnjfcsgkdhgzbwfmfkqsipyfwvcewpmbcynvbokkjglmebpjoxjzrdctupiltsliudqbjvkxoznsqcieieugyyjrjjargrxzlpmhhsfppumiorikzhmmqnizytffatglqmvlaipjiyqxhjhnpupwpiochvecxyuimxlulubxtoqcgkfwmkckpftpicfriqsnvoiyludtevyzbdnqrftfalxzpijpjdedwddvlcsfwsfrjflpemmwssyvldruqxtlgqnookdapzemgzaylximefhdsmcwvvkefhxmqyqbyglhrzixwlqkvqevsgbgwbtzfsdoeuzmspckpvaxxxfpzftdnwxekdxltjwfcpcjckkdgrqfuterklilpzifwvhhiyzbfaeyouwajudcqxqrovucttoperfekxtkwykacoofobtopamrnvyolatwiscgaaslmkedbhvvesfvkygeqmjzmoxlmelpthtkanjimxkmetruoenbmgsyuixoccbsdpbotidbzpwwjfkjdgzilmixlee
--- ok --- -0.07744500000000001

比其他的是慢了1000倍,0.77ms,目标:优化到1ms.

分析

问题就在于,外层的(计算层数的)for没必要循环的(随着层数增大,每一层都O(n),多少无用功),只要分numRows个列表,一个for就遍历完。

改完测一下时间

PAYPALISHIRING 4
PINALSIGYAHRPI
--- ok --- -2.4100000000000857e-05
PAYPALISHIRING 3
PAHNAPLSIIGYIR
--- ok --- -1.9699999999999232e-05
A 1
A
--- ok --- -1.1399999999999952e-05
kvzeeubynglxfdedshtpobqsdhufkzgwuhaabdzrlkosnuxibrxssnkxuhcggkecshdvkcmymdqbxolbfjtzyfwtmbbungzfpcbbgpzusqxqejrlsmkqtglijpcxxbcmffnlvnfpddfjmyugkeyemkmyzqvwszkxfxlckqrpvzyjxupkyoonaclbsgzmhjmogxstpkilljwidoseeitemefhmgtvpfkxecquobhzkfkptetxpmdbskigqecflmdqqvmfwveiaqyuvrtkgxlyhwhyalfnzifpgrucoblprjloceykbkjlisjkdoxczdtfwqjlrwckhnzkrxuvjfgtzrdchdgiicneszrlvtxdiwncwjxhrfbqygvfjdorfdyzcrkylidvgqxebwmubplzxihjlvataasdsfdfngavyyabuowyfhzcpglcdoxeoqjivmnkuofsohtivpiayifpoquugryvjjfgvtqrjyjxhefdwqfwykmodiijzigjrmpohifqiqnpvuutkcpiodzrljdlslwlxnagxhwfylxvgtosvfdkjcdulihfudrtrtaoaywakvvqolkmtnycpdwdmeigjbbcubrxapxmkveaiombckftocwaifitgjwdnpapezbqwhqhvdizpotdspfcwpxfbtiqikfolieipxpmazmrphxjyenvulcxeknpwsfhckptjgflitczczjbeyyajaxqmkhiempgyfzhngsvcvxewghcgfcqhzitlpbpbrvaywjlfcjhzgnxoxauecmmeufpljfpacrazaneewndecbuzbrgffsjczznieckitkhwynawcgdfjzgmqmrygbaicpqiudqpnylnnoksupzdofphuifcjhknydvsgmivmvjbjttdksiyazhuimytvjhuocmuqwpcsyedtzjdsresrlozamsvxbrlegfucxzwxfcrelwyeaqvoewotrlssdeyjltnkumibozfzxe 200
kmavwupczbbfreepjaexllzuqzpabgxfnyviuendheegijmwlllmnxyvcdfkaeedrtucecaabdzaxusysozhddxbtfsnrprfggoodzfbdfhfqjnjssfgcjdvafchgvlzuyyjzfqywnkbayizfbaegruvcwhorkuxwbihjyptawfbkachphbnzlwdwctyzipinrdgzalxlhwktcqcovdcgslofdnrxgfuzecjxsohzieqggbnjwmrcieqxivxmsimvrsgncyndkvgkhusbxcogaudfnihrshcczozpgthfqggtyikfiguejvpdcvpmqsuiephxaindryhyvkiklkzfmncnpqnmhoxoykqakmcujsdwuauqrgypblryzxjyedoqvbolwjjfbfjzpftfchjdgzutzvcizcttfyxqicforljwdjfhtkygkmjjjnbsxtybihpdulekvnjfcsgkdhgzbwfmfkqsipyfwvcewpmbcynvbokkjglmebpjoxjzrdctupiltsliudqbjvkxoznsqcieieugyyjrjjargrxzlpmhhsfppumiorikzhmmqnizytffatglqmvlaipjiyqxhjhnpupwpiochvecxyuimxlulubxtoqcgkfwmkckpftpicfriqsnvoiyludtevyzbdnqrftfalxzpijpjdedwddvlcsfwsfrjflpemmwssyvldruqxtlgqnookdapzemgzaylximefhdsmcwvvkefhxmqyqbyglhrzixwlqkvqevsgbgwbtzfsdoeuzmspckpvaxxxfpzftdnwxekdxltjwfcpcjckkdgrqfuterklilpzifwvhhiyzbfaeyouwajudcqxqrovucttoperfekxtkwykacoofobtopamrnvyolatwiscgaaslmkedbhvvesfvkygeqmjzmoxlmelpthtkanjimxkmetruoenbmgsyuixoccbsdpbotidbzpwwjfkjdgzilmixlee
--- ok --- -0.0005619000000000006

bingo! 0.56ms

提交看看,肯定AC

第3次提交 完整代码
import time

class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
# create list array save each line
listStr=[]
for n in range(numRows):
try:
listStr[n]
except:
listStr.append('') # each line add char to listStr[n].
for k,c in enumerate(s):
#print(k,c,end=" ")
n=findLine(k,numRows)
listStr[n]=listStr[n]+c # joint str
zigzag=''.join(listStr)
return zigzag
# find k in line
def findLine(k,rows):
# 延长,去掉斜路两头
prolong=rows-2 # 取模底
modulo=rows+prolong # validity check
if prolong<0:
prolong=0
if modulo<=0:
modulo=1 #print(modulo,prolong+1,k%modulo,(k%modulo-rows+1)%(prolong+1),(k%modulo) if (k%modulo)<rows else prolong-(k%modulo-rows))
x=k%modulo
return (x) if (x)<rows else prolong-(x-rows) if __name__ == "__main__": data = [
{
"input":{
's':'PAYPALISHIRING',
'numRows':4
},
"output":"PINALSIGYAHRPI",
},{
"input":{
's':'PAYPALISHIRING',
'numRows':3
},
"output":"PAHNAPLSIIGYIR",
},
{
"input":{
's':'A',
'numRows':1
},
"output":"A",
},
{
"input":{
's':'kvzeeubynglxfdedshtpobqsdhufkzgwuhaabdzrlkosnuxibrxssnkxuhcggkecshdvkcmymdqbxolbfjtzyfwtmbbungzfpcbbgpzusqxqejrlsmkqtglijpcxxbcmffnlvnfpddfjmyugkeyemkmyzqvwszkxfxlckqrpvzyjxupkyoonaclbsgzmhjmogxstpkilljwidoseeitemefhmgtvpfkxecquobhzkfkptetxpmdbskigqecflmdqqvmfwveiaqyuvrtkgxlyhwhyalfnzifpgrucoblprjloceykbkjlisjkdoxczdtfwqjlrwckhnzkrxuvjfgtzrdchdgiicneszrlvtxdiwncwjxhrfbqygvfjdorfdyzcrkylidvgqxebwmubplzxihjlvataasdsfdfngavyyabuowyfhzcpglcdoxeoqjivmnkuofsohtivpiayifpoquugryvjjfgvtqrjyjxhefdwqfwykmodiijzigjrmpohifqiqnpvuutkcpiodzrljdlslwlxnagxhwfylxvgtosvfdkjcdulihfudrtrtaoaywakvvqolkmtnycpdwdmeigjbbcubrxapxmkveaiombckftocwaifitgjwdnpapezbqwhqhvdizpotdspfcwpxfbtiqikfolieipxpmazmrphxjyenvulcxeknpwsfhckptjgflitczczjbeyyajaxqmkhiempgyfzhngsvcvxewghcgfcqhzitlpbpbrvaywjlfcjhzgnxoxauecmmeufpljfpacrazaneewndecbuzbrgffsjczznieckitkhwynawcgdfjzgmqmrygbaicpqiudqpnylnnoksupzdofphuifcjhknydvsgmivmvjbjttdksiyazhuimytvjhuocmuqwpcsyedtzjdsresrlozamsvxbrlegfucxzwxfcrelwyeaqvoewotrlssdeyjltnkumibozfzxe',
'numRows':200
},
"output":"kmavwupczbbfreepjaexllzuqzpabgxfnyviuendheegijmwlllmnxyvcdfkaeedrtucecaabdzaxusysozhddxbtfsnrprfggoodzfbdfhfqjnjssfgcjdvafchgvlzuyyjzfqywnkbayizfbaegruvcwhorkuxwbihjyptawfbkachphbnzlwdwctyzipinrdgzalxlhwktcqcovdcgslofdnrxgfuzecjxsohzieqggbnjwmrcieqxivxmsimvrsgncyndkvgkhusbxcogaudfnihrshcczozpgthfqggtyikfiguejvpdcvpmqsuiephxaindryhyvkiklkzfmncnpqnmhoxoykqakmcujsdwuauqrgypblryzxjyedoqvbolwjjfbfjzpftfchjdgzutzvcizcttfyxqicforljwdjfhtkygkmjjjnbsxtybihpdulekvnjfcsgkdhgzbwfmfkqsipyfwvcewpmbcynvbokkjglmebpjoxjzrdctupiltsliudqbjvkxoznsqcieieugyyjrjjargrxzlpmhhsfppumiorikzhmmqnizytffatglqmvlaipjiyqxhjhnpupwpiochvecxyuimxlulubxtoqcgkfwmkckpftpicfriqsnvoiyludtevyzbdnqrftfalxzpijpjdedwddvlcsfwsfrjflpemmwssyvldruqxtlgqnookdapzemgzaylximefhdsmcwvvkefhxmqyqbyglhrzixwlqkvqevsgbgwbtzfsdoeuzmspckpvaxxxfpzftdnwxekdxltjwfcpcjckkdgrqfuterklilpzifwvhhiyzbfaeyouwajudcqxqrovucttoperfekxtkwykacoofobtopamrnvyolatwiscgaaslmkedbhvvesfvkygeqmjzmoxlmelpthtkanjimxkmetruoenbmgsyuixoccbsdpbotidbzpwwjfkjdgzilmixlee",
}, ];
for d in data: print(d['input']['s'],d['input']['numRows']) # 计算运行时间
start = time.perf_counter()
result=Solution().convert(d['input']['s'],d['input']['numRows'])
end = time.perf_counter() print(result)
if result==d['output']:
print("--- ok ---",end="\t")
else:
print("--- error ---",end="\t") print(start-end)

总结:好多坑没有踩过就不会有经验,这就是为什么要多码多思考了,还需要一直提升一直充电。不总结,就不会有什么沉淀;不提升,就不会用更高级的方法去建模,去看待这个魔幻的世界。

LeetCode 6. ZigZag Conversion & 字符串的更多相关文章

  1. &lbrack;leetcode&rsqb;6&period; ZigZag Conversion字符串Z形排列

    The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like ...

  2. Leetcode 6 ZigZag Conversion 字符串处理

    题意:将字符串排成Z字形. PAHNAPLSIIGYIR 如果是5的话,是这样排的 P     I AP   YR H L G N  SI A    I 于是,少年少女们,自己去找规律吧 提示:每个Z ...

  3. Java &lbrack;leetcode 6&rsqb; ZigZag Conversion

    问题描述: The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows ...

  4. Leetcode 6&period; ZigZag Conversion(找规律,水题)

    6. ZigZag Conversion Medium The string "PAYPALISHIRING" is written in a zigzag pattern on ...

  5. &lbrack;LeetCode&rsqb; 6&period; ZigZag Conversion 之字型转换字符串

    The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like ...

  6. 蜗牛慢慢爬 LeetCode 6&period; ZigZag Conversion &lbrack;Difficulty&colon; Medium&rsqb;

    题目 The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows li ...

  7. LeetCode 6 ZigZag Conversion 模拟 难度&colon;0

    https://leetcode.com/problems/zigzag-conversion/ The string "PAYPALISHIRING" is written in ...

  8. leetcode 6&period; ZigZag Conversion

    https://leetcode.com/problems/zigzag-conversion/ 题目: 将字符串转化成zigzag模式. 例如 "abcdefghijkmlnpq&quot ...

  9. LeetCode 6 ZigZag Conversion(规律)

    题目来源:https://leetcode.com/problems/zigzag-conversion/ The string "PAYPALISHIRING" is writt ...

随机推荐

  1. velocity模板使用建议

    复杂页面前端模块化的方式: 方式一:iframe 方式二:velocity模板(#parse) 方式一,优点很多,也有缺点,例如页面之间传递参数等: 方式二,页面之间的调用,传参更容易,页面性能更好: ...

  2. LCD如何显示图像

    1.LCD显示主要相关概念 (1)像素(pixel) 整个图像是由一个个的像素组成的,像素就是一个显示点.像素就是组成图像的最基本元素,或者说显示中可以被控制的最小单位,整个图像就是由很多个像素组成的 ...

  3. java学习笔记 &lpar;5&rpar; —— Struts2 监听器配置

    1.创建MyListener.java 实现 PreResultLisener 接口 import com.opensymphony.xwork2.ActionInvocation; import c ...

  4. Matlab近期用到的函数(持续更新)

    最近任务用到matlab较多,第一版的代码大部分对于矩阵类的计算都是用for循环来完成的,主要是思维还没有适应matlab.看了同事的一份代码后,现在遇到需要循环的地方第一反应就是如何能够用矩阵的直接 ...

  5. AspNet&period;OData 协议概述

    1. 什么是OData? OData 全称 Open Data Protocol,字面理解为开放数据协议,是一个基于Http协议且API实现为Restful风格的协议标准,目前由微软支持大力推广,你可 ...

  6. keystone V3 与Microsoft Active Directory(AD)的集成

    一  环境准备 1. 安装或在现有的windows server2008,操作Microsoft Acitve Directory(下面简称AD).欲了解AD请看系列文章[深入浅出ActiveDire ...

  7. jQuery Ajax post多个值传参

    http://blog.csdn.net/wang8559422/article/details/42394839 data:'id='+data+'&val='+val   加&符 ...

  8. 编译器重复定义错误:error C2371&colon; &&num;39&semi;SIZE&&num;39&semi; &colon; redefinition&semi; different basic types

    我们常常会定义自己工程用的数据类型,可能会与Windows的基本数据类型冲突. vs会报重复定义错误:error C2371: 'SIZE' : redefinition; different bas ...

  9. UVA11922 Permutation Transformer

    思路 直接使用FHQ Treap维护即可 代码 #include <cstdio> #include <cstring> #include <algorithm> ...

  10. centos7安装redist 以及redis扩展

    wget http://download.redis.io/releases/redis-3.2.1.tar.gz   用wget下载 $ tar xzf redis-3.2.1.tar.gz   解 ...