算法小白的代码如下↓
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
# 输出列表
answer_list=[]
# p的长度
p_len=len(p)
# 索引遍历s的子串
for i in range(len(s)):
# 最后一次循环
if i+p_len>len(s):
break
# 切分s子串
s_split=s[i:i+p_len]
# 定义类方法,若s的子串与p为异位词
if self.is_yiweici(s_split,p):
# 则向输出列表中添加索引
answer_list.append(i)
return answer_list
# 类方法,判断s的子串与p是否为异位词
def is_yiweici(self,a,b):
if a==b:
return True
used_lst=[]
# 遍历子串的每一个字符
for i in a:
if i in used_lst:
continue
# 如果字符未出现在b中
if i not in b:
# 返回False
return False
# 若字符出现在b中
else:
if a.count(i) != b.count(i):
return False
else:
# str2=str1.replace(old_str,new_str,count)
# count:替换的次数,默认是全部替换
# 返回值:得到一个新的字符串,不会改变原来的字符串
b=b.replace(i,'')
used_lst.append(i)
return True
但是超时了……
虽然代码没有提交成功,但是需要注意几个点:
①类中方法的参数self:
在类的内部,使用 def 关键字来定义一个方法,与一般函数定义不同,类方法必须包含参数self
, 且为第一个参数,self
代表的是类的实例。
- self:类的方法与普通的函数只有一个特别的区别——必须有一个额外的第一个参数名称, 按照惯例它的名称是self。
-
类的实例:是将类应用在实例场景之中,比如有个类里的函数是
f
,假如这个f
具有print某一时刻的天气状况的能力,那么如果我需要这个f
来print一下今天12点的天气,那么让他打印今天12点的天气这个动作,就是类的实例化,让类中的函数具有的能力变成真实的动作。
②Python replace() 方法 把字符串中的 old(旧字符串) 替换成 new(新字符串),如果指定第三个参数max,则替换不超过 max 次。
返回值:得到一个新的字符串,不会改变原来的字符串
str2=str1.replace(old_str,new_str,count)
为什么超时了,因为在字符串滑动比较的过程中,没有充分利用“滑动”的性质,每一次滑动都在重新比较,并没有利用到“滑动窗口”的特性。
核心思想:在字符串s中构造一个长度与字符串p长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量。当窗口中每种字母的数量与字符串p相同时,则说明当前窗口为字符串p的异位词。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# 记录s和p的长度
s_len, p_len = len(s), len(p)
# 特殊情况,若s的长度小于p的长度,直接返回空列表
if s_len < p_len:
return []
ans = []
# s_count为滑动窗口
s_count = [0] * 26
p_count = [0] * 26
# 依题意,p_count统计p中各字母的数量
for i in range(p_len):
s_count[ord(s[i]) - 97] += 1
p_count[ord(p[i]) - 97] += 1
# 当初始位置s_count==p_count,将索引0添加至列表
if s_count == p_count:
ans.append(0)
# 滑动窗口
for i in range(s_len - p_len):
s_count[ord(s[i]) - 97] -= 1
s_count[ord(s[i + p_len]) - 97] += 1
if s_count == p_count:
ans.append(i + 1)
return ans
需要注意:
①滑动窗口的长度为p_len。
②ASCII码,全称为 American Standard Code for Information Interchange,python中的 ord() 函数主要用来返回对应字符的ASCII码。
ord('a')==97
ord('A')==65
官方题解还给出了另一种滑动窗口的方法(基于differ差量)
此处仅给出思路和算法,代码省略文章来源:https://www.toymoban.com/news/detail-459955.html
文章来源地址https://www.toymoban.com/news/detail-459955.html
到了这里,关于机试打卡 -01 字母异位词(滑动窗口)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!