- 来源于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。
- 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
示例
示例 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
