中等难度-哈希表

来源于leetcode题库49,347,438,560,739

49.字母异位词分组

题目描述
- 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例

输入: ["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))
            # 如果找不到则返回默认值[]，即把字符串排序后作为键
            # 把能排序成键的字符串作为值存起来
            dict[key] = dict.get(key, []) + [item]
        return list(dict.values())

347.前k个高频元素

题目描述：
- 给定一个非空的整数数组，返回其中出现频率前 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:
            #如果不存在，则将其存入字典中，此时该值的出现频率为1
            if i not in dit:     
                dit[i] = 1
            #如果已经存在，则其出现频率加1
            else:                
                dit[i] =  dit[i]+1
        #由于字典无法排序，因此需要先将字典转换为列表，列表中的每一个元素为 键-值 构成的元祖
        temp = []         
         #使用字典的items函数,获取 键-值对元祖列表            
        for item in dit.items():  
            #这里需要对出现频率进行排序，因此将每一个元祖元素进行转置，
            #即出现次数在前，字符在后
            temp.append(item[::-1])    
        #对列表进行排序，对于每一个元素都是元祖的列表来说，
        #其排序是按照元祖的第一个元素进行的
        temp.sort(reverse=True)       
        #使用列表推导式求前k个高频元素，因为转置过，所以元素在后，为temp[i][1]
        return [temp[i][1] for i in range(k)]

438. 找到字符串中所有字母异位词

题目描述
- 给定一个字符串 s 和一个非空字符串 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字母个数
        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，即左右指针之间的字母数量比p少，不可能是异位词
            if right < len(p) - 1:
                s_count[ord(s[right]) - 97] += 1
                continue
            # 窗口加一个， 减一个，维护长度为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的子数组

题目描述：
- 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例：

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

题解：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        d = {} # 哈希表   '前缀和:出现次数'
        # acc为前缀和，count为出现次数
        acc = count = 0
        for num in nums:
            # 前缀和
            acc += num
            # 如果为k，则count+1
            if acc == k:
                count += 1
            # 如果acc-k在哈希表中，则将acc-k对应的次数加上去
            if acc - k in d:
                count += d[acc-k]
            # 如果前缀和acc已经在哈希表中了那次数+1
            if acc in d:
                d[acc] += 1
            # 否则将其加入到哈希表中
            else:
                d[acc] = 1
        return count

739.每日温度

题目描述
- 请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例：

给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

题解

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        l = len(T)
        stack = []  
        # 所以这里初始化一个全是0的list，因为题目中说没有匹配的就返回0，
        res = [0] * l   

        for idx, t in enumerate(T):
            # 当stack为空时，运行stack.append(idx)，则stack=[0]
            # 然后仅当遍历元素 t 小于stack顶端的值时append进去，
            # 这会导致stack中idx代表的元素是单调递减的！！！！
            # 如果此时遍历到一个 t，大于stack顶端的值，那这个t就是离stack
            # 顶端值最近的那个大值。
            while stack and t > T[stack[-1]]:  
                # 然后pop出来，还是要注意stack.pop出来的是idx，这样res这
                # 一串0里对应位置的0就会被替换成应有的值。                           
                # 再进入while循环判断t和stack.pop后的新的顶端值哪个大。
                # 如此反复。
                res[stack.pop()] = idx-stack[-1] #下标之差就是等待的天数
            stack.append(idx)
        return res