?

算法小白的代碼如下↓

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)):

            # 最后一次循環(huán)
            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=[]

        # 遍歷子串的每一個(gè)字符
        for i in a:

            if i in used_lst:
                continue
            
            # 如果字符未出現(xiàn)在b中
            if i not in b:

                # 返回False
                return False
            
            # 若字符出現(xiàn)在b中
            else:
                if a.count(i) != b.count(i):
                    return False
                
                else:

                # str2=str1.replace(old_str,new_str,count)
                # count:替換的次數(shù),默認(rèn)是全部替換
                # 返回值：得到一個(gè)新的字符串，不會(huì)改變原來的字符串
                    b=b.replace(i,'')

                used_lst.append(i)
                
        return True

但是超時(shí)了……

雖然代碼沒有提交成功，但是需要注意幾個(gè)點(diǎn)：

①類中方法的參數(shù)self:在類的內(nèi)部，使用 def 關(guān)鍵字來定義一個(gè)方法，與一般函數(shù)定義不同，類方法必須包含參數(shù)self, 且為第一個(gè)參數(shù)，self代表的是類的實(shí)例。

• self：類的方法與普通的函數(shù)只有一個(gè)特別的區(qū)別——必須有一個(gè)額外的第一個(gè)參數(shù)名稱, 按照慣例它的名稱是self。
• 類的實(shí)例：是將類應(yīng)用在實(shí)例場景之中，比如有個(gè)類里的函數(shù)是f，假如這個(gè)f具有print某一時(shí)刻的天氣狀況的能力，那么如果我需要這個(gè)f來print一下今天12點(diǎn)的天氣，那么讓他打印今天12點(diǎn)的天氣這個(gè)動(dòng)作，就是類的實(shí)例化，讓類中的函數(shù)具有的能力變成真實(shí)的動(dòng)作。

②Python replace() 方法?把字符串中的 old（舊字符串） 替換成 new(新字符串)，如果指定第三個(gè)參數(shù)max，則替換不超過 max 次。

返回值：得到一個(gè)新的字符串，不會(huì)改變原來的字符串

str2=str1.replace(old_str,new_str,count)

為什么超時(shí)了，因?yàn)樵谧址瑒?dòng)比較的過程中，沒有充分利用“滑動(dòng)”的性質(zhì)，每一次滑動(dòng)都在重新比較，并沒有利用到“滑動(dòng)窗口”的特性。

核心思想：在字符串s中構(gòu)造一個(gè)長度與字符串p長度相同的滑動(dòng)窗口，并在滑動(dòng)中維護(hù)窗口中每種字母的數(shù)量。當(dāng)窗口中每種字母的數(shù)量與字符串p相同時(shí)，則說明當(dāng)前窗口為字符串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為滑動(dòng)窗口
        s_count = [0] * 26
        p_count = [0] * 26
        
        # 依題意，p_count統(tǒng)計(jì)p中各字母的數(shù)量
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1
        
        # 當(dāng)初始位置s_count==p_count，將索引0添加至列表
        if s_count == p_count:
            ans.append(0)
        
        # 滑動(dòng)窗口
        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

需要注意：
①滑動(dòng)窗口的長度為p_len。

②ASCII碼，全稱為 American Standard Code for Information Interchange，python中的 ord() 函數(shù)主要用來返回對(duì)應(yīng)字符的ASCII碼。

ord('a')==97

ord('A')==65

?

官方題解還給出了另一種滑動(dòng)窗口的方法（基于differ差量）

此處僅給出思路和算法，代碼省略

文章來源地址http://www.zghlxwxcb.cn/news/detail-459955.html

到了這里，關(guān)于機(jī)試打卡 -01 字母異位詞（滑動(dòng)窗口）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！