leetcode字符串(python)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode字符串(python)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4249字，纯文字阅读大概需要7分钟。
内容图文
这道题主要用到思路是：滑动窗口
什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？我们只要把队列的左边的元素移出就行了，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
max_len = 0 #当取最大时，一定会设置两个变量，当前值和当前最大值
cur_len = 0
lookup = set() #建立集合，如果集合内已有该元素，元素个数不变（并集）add添加，删除用remove
s_len = len(s)
for i in range(s_len):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len: max_len = cur_len
lookup.add(s[i])
return max_len
这位大佬写的很棒，尤其是动态规划法，但针对这题最好的方法还是中心扩散法。
我分别用暴力法，动态规划和中心扩散法，代码如下：
#暴力法 这篇文章是为中级读者而写的。它介绍了回文，动态规划以及字符串处理。请确保你理解什么是回文。回文是一个正读和反读都相同的字符串，例如，“aba” 是回文
# class Solution:
# def longestPalindrome(self, s: str) -> str:
# if s==s[::-1]:
# return s
# max_len = 1
# res = s[0]
# for i in range(len(s) - 1):
# for j in range(i + 1, len(s)):
# if j - i + 1 > max_len and s[i:j+1] == s[i:j+1][::-1]:
# max_len = j - i + 1
# res = s[i:j + 1]
# return res
#时间复杂度：O(n^2),往往利用python的切片可以很好的缩减复杂度
#动态规划方法
# class Solution:
# def longestPalindrome(self, s: str) -> str:
# #特例
# size = len(s)
# if len(s) < 2:
# return s
# start = 0
# max_len = 1
# #定义状态
# dp = [[False for _ in range(size)] for _ in range(size)]
# #初始化
# for i in range(size):
# dp[i][i] = True
# #状态转移
# for j in range(1, size):
# for i in range(0, j):
# if s[i] == s[j]:
# if j - i < 3: #aba，cdc都是true
# dp[i][j] = True
# else:
# dp[i][j] = dp[i+1][j-1]
# else:
# dp[i][j] = False
# if dp[i][j] == True:
# cur_len = j - i + 1
# if cur_len > max_len:
# start = i
# max_len = cur_len
# # print(max_len)
# return s[start:start + max_len]
#中心扩散法 时间复杂度为o(n2),空间复杂度为o(n1)
class Solution:
def longestPalindrome(self, s: str) -> str:
def center_spread(s, size, left, right):
i = left
j = right
while i >= 0 and j < size and s[i] == s[j]:
i -= 1
j += 1
return s[i+1: j], j - i - 1
max_len = 1
size = len(s)
if size < 2:
return s
res = s[0] #注意这个位置要放在判断之后，如果放在之前会报错，eg当s=''时，不存在s[0]
for i in range(size):
odd_str, odd_len = center_spread(s, size, i, i)
even_str, even_len = center_spread(s, size, i, i+1)
cur_max_str = odd_str if odd_len > even_len else even_str
if len(cur_max_str) > max_len:
max_len = len(cur_max_str)
res = cur_max_str
return res
#参考链接https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
掌握方法：https://leetcode-cn.com/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/
思路：
#按着z的方向，每次都是第一行到最后一行，然后从最后一行到第一行，再转向，因此我们定义转向flag，res存每行的字符，最后在用join连接起来。
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows < 2:
return s
res = ['' for _ in range(numRows)]
i, flag = 0, -1
for c in s:
res[i] += c
if i == 0 or i == numRows - 1:flag = -flag
i += flag
return ''.join(res)
ailinmiao 发布了13 篇原创文章 · 获赞 1 · 访问量 380 私信 关注
内容总结
以上是互联网集市为您收集整理的leetcode字符串(python)全部内容，希望文章能够帮你解决leetcode字符串(python)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。