机试打卡 -01 字母异位词(滑动窗口)

这篇具有很好参考价值的文章主要介绍了机试打卡 -01 字母异位词(滑动窗口)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

机试打卡 -01 字母异位词(滑动窗口)

机试打卡 -01 字母异位词(滑动窗口)

 机试打卡 -01 字母异位词(滑动窗口)


算法小白的代码如下↓

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的异位词。


机试打卡 -01 字母异位词(滑动窗口)

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

 

机试打卡 -01 字母异位词(滑动窗口)


官方题解还给出了另一种滑动窗口的方法(基于differ差量)

此处仅给出思路和算法,代码省略

机试打卡 -01 字母异位词(滑动窗口)文章来源地址https://www.toymoban.com/news/detail-459955.html

到了这里,关于机试打卡 -01 字母异位词(滑动窗口)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机试打卡 -06 异位词分组(哈希表)

      最容易想到的是利用 ord( ) 函数 ,按照字母 计数 的特征归类,代码如下: ①ord(\\\'a\\\')==97。 ②字典的key必须是可哈希的! 一个对象在其生命周期内,如果保持不变,就是hashable(可哈希的)。 hashable ≈ imutable      可哈希 ≈ 不可变 在Python中: list、set和dictionary 都是可改变的

    2024年02月06日
    浏览(34)
  • 255.【华为OD机试】最小矩阵宽度(滑动窗口算法-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年03月13日
    浏览(64)
  • 【算法题】49. 字母异位词分组

    给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs = [\\\"eat\\\", \\\"tea\\\", \\\"tan\\\", \\\"ate\\\", \\\"nat\\\", \\\"bat\\\"] 输出: [[\\\"bat\\\"],[\\\"nat\\\",\\\"tan\\\"],[\\\"ate\\\",\\\"eat\\\",\\\"tea\\\"]] 示例 2: 输入: strs = [\\\"\\\"] 输出:

    2024年01月22日
    浏览(37)
  • Java【手撕滑动窗口】LeetCode 438. “字符串中所有异位词“, 图文详解思路分析 + 代码

    各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议

    2024年02月10日
    浏览(43)
  • 算法刷题-哈希表-有效的字母异位词

    数组就是简单的哈希表,但是数组的大小可不是无限开辟的 力扣题目链接 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true 示例 2: 输入: s = “rat”, t = “car” 输出: false 说明: 你可以假设字符串只包

    2024年02月09日
    浏览(44)
  • Python算法题集_字母异位词分组

    本文为Python算法题集之一的代码示例 题目49:字母异位词分组 说明:给你一个字符串数组,请你将 字母异位词 组合在一起,可以按任意顺序返回结果列表 字母异位词 :是由重新排列原单词所有字母得到的新单词 使用同步数组 list 和检索集合 set 使用同步数组 list 和结果数

    2024年01月20日
    浏览(40)
  • Day 6 哈希表part01:242.有效的字母异位词 , 349. 两个数组的交集 , 202. 快乐数, 1. 两数之和

    哈希表理论基础  要了解哈希表的内部实现原理,哈希函数,哈希碰撞,以及常见哈希表的区别,数组,set 和map。   什么时候想到用哈希法,当我们遇到了 要快速判断一个元素是否出现集合里的时候 ,就要考虑 哈希法 。  这句话很重要,大家在做哈希表题目都要思考这

    2024年02月15日
    浏览(55)
  • 【LeetCode热题100】打卡第42天:滑动窗口最大值&搜索二维矩阵II

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月10日
    浏览(50)
  • 【算法挨揍日记】day07——904. 水果成篮、438. 找到字符串中所有字母异位词

    904. 水果成篮 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组  fruits  表示,其中  fruits[i]  是第  i  棵树上的水果  种类  。 你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果: 你只有  两个

    2024年02月07日
    浏览(41)
  • 算法训练第5天|哈希表理论基础 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

    哈希表是根据 关键码 的值而直接进行访问的数据结构。 一般哈希表都是用来快速判断一个元素是否出现集合里。 数组、集合set、映射map 力扣链接 题目描述: 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意: 若  s  和  t   中每个字符出现的

    2024年02月19日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包