• 來源于leetcode題庫49,347,438,560,739

49.字母異位詞分組

• 題目描述
  • 給定一個(gè)字符串?dāng)?shù)組，將字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字符串。
• 示例

輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

• 題解

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict = {}
        for item in strs:
            # 字典的鍵必須是不可變類型，所以用tuple
            key = tuple(sorted(item))
            # 如果找不到則返回默認(rèn)值[]，即把字符串排序后作為鍵
            # 把能排序成鍵的字符串作為值存起來
            dict[key] = dict.get(key, []) + [item]
        return list(dict.values())

347.前k個(gè)高頻元素

• 題目描述：
  • 給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。
• 示例：

示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]

• 題解：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dit={}                            
        for i in nums:
            #如果不存在，則將其存入字典中，此時(shí)該值的出現(xiàn)頻率為1
            if i not in dit:     
                dit[i] = 1
            #如果已經(jīng)存在，則其出現(xiàn)頻率加1
            else:                
                dit[i] =  dit[i]+1
        #由于字典無法排序，因此需要先將字典轉(zhuǎn)換為列表，列表中的每一個(gè)元素為 鍵-值 構(gòu)成的元祖
        temp = []         
         #使用字典的items函數(shù),獲取 鍵-值對元祖列表            
        for item in dit.items():  
            #這里需要對出現(xiàn)頻率進(jìn)行排序，因此將每一個(gè)元祖元素進(jìn)行轉(zhuǎn)置，
            #即出現(xiàn)次數(shù)在前，字符在后
            temp.append(item[::-1])    
        #對列表進(jìn)行排序，對于每一個(gè)元素都是元祖的列表來說，
        #其排序是按照元祖的第一個(gè)元素進(jìn)行的
        temp.sort(reverse=True)       
        #使用列表推導(dǎo)式求前k個(gè)高頻元素，因?yàn)檗D(zhuǎn)置過，所以元素在后，為temp[i][1]
        return [temp[i][1] for i in range(k)]  
   

438. 找到字符串中所有字母異位詞

• 題目描述

  • 給定一個(gè)字符串 s 和一個(gè)非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。
    字符串只包含小寫英文字母，并且字符串 s 和 p 的長度都不超過 20100。

• 示例

示例 1:
輸入:
s: "cbaebabacd" p: "abc"
輸出:
[0, 6]
解釋:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞。
示例 2:
輸入:
s: "abab" p: "ab"
輸出:
[0, 1, 2]
解釋:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母異位詞。

起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母異位詞。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母異位詞。

• 題解：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
         # 記錄p, s字母個(gè)數(shù)
        p_count = [0] * 26
        s_count = [0] * 26
        res = []
        # 非空字符串p的所有字母
        for a in p:
            p_count[ord(a) - 97] += 1
        # 左指針
        left = 0
        for right in range(len(s)):
            # 如果右指針小于p的長度-1，即左右指針之間的字母數(shù)量比p少，不可能是異位詞
            if right < len(p) - 1:
                s_count[ord(s[right]) - 97] += 1
                continue
            # 窗口加一個(gè)， 減一個(gè)，維護(hù)長度為len(p)的長度
            s_count[ord(s[right]) - 97] += 1
            if p_count == s_count:
                res.append(left)
            # 左指針位置+1
            s_count[ord(s[left]) - 97] -= 1
            left += 1
        return res

560.和為k的子數(shù)組

• 題目描述：
  • 給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，你需要找到該數(shù)組中和為 k 的連續(xù)的子數(shù)組的個(gè)數(shù)。
• 示例：

輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。

• 題解：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        d = {} # 哈希表   '前綴和:出現(xiàn)次數(shù)'
        # acc為前綴和，count為出現(xiàn)次數(shù)
        acc = count = 0
        for num in nums:
            # 前綴和
            acc += num
            # 如果為k，則count+1
            if acc == k:
                count += 1
            # 如果acc-k在哈希表中，則將acc-k對應(yīng)的次數(shù)加上去
            if acc - k in d:
                count += d[acc-k]
            # 如果前綴和acc已經(jīng)在哈希表中了那次數(shù)+1
            if acc in d:
                d[acc] += 1
            # 否則將其加入到哈希表中
            else:
                d[acc] = 1
        return count

739.每日溫度

• 題目描述
  • 請根據(jù)每日 氣溫 列表，重新生成一個(gè)列表。對應(yīng)位置的輸出為：要想觀測到更高的氣溫，至少需要等待的天數(shù)。如果氣溫在這之后都不會(huì)升高，請?jiān)谠撐恢糜?0 來代替。
• 示例：

給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。

• 題解

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        l = len(T)
        stack = []  
        # 所以這里初始化一個(gè)全是0的list，因?yàn)轭}目中說沒有匹配的就返回0，
        res = [0] * l   

        for idx, t in enumerate(T):
            # 當(dāng)stack為空時(shí)，運(yùn)行stack.append(idx)，則stack=[0]
            # 然后僅當(dāng)遍歷元素 t 小于stack頂端的值時(shí)append進(jìn)去，
            # 這會(huì)導(dǎo)致stack中idx代表的元素是單調(diào)遞減的?。。。?            # 如果此時(shí)遍歷到一個(gè) t，大于stack頂端的值，那這個(gè)t就是離stack
            # 頂端值最近的那個(gè)大值。
            while stack and t > T[stack[-1]]:  
                # 然后pop出來，還是要注意stack.pop出來的是idx，這樣res這
                # 一串0里對應(yīng)位置的0就會(huì)被替換成應(yīng)有的值。                           
                # 再進(jìn)入while循環(huán)判斷t和stack.pop后的新的頂端值哪個(gè)大。
                # 如此反復(fù)。
                res[stack.pop()] = idx-stack[-1] #下標(biāo)之差就是等待的天數(shù)
            stack.append(idx)
        return res