1.会议室 II
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。
示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
示例 2：
输入：intervals = [[7,10],[2,4]]
输出：1
合并区间的反向版本，也没太大什么好说的，我自己的办法是用排序的
class Solution:def minMeetingRooms(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x:x[0])res=[]for i in range(len(intervals)):changed=Falsefor m in range(len(res)):if intervals[i][0]>=res[m][1]:res[m][1]=intervals[i][1]changed=Trueif changed==False:res.append(intervals[i])return len(res)
方法二：堆，第一次听这个说法，上次听堆还是在C++中，用new来去使用堆，也就是说程序员手动配置的，需要使用delete进行内存释放，不然会造成内存泄漏，不知道今天的堆是否能给人一些不一样的想法呢。
import heapq
class Solution:def minMeetingRooms(self,intervals:List[List[int]])->int:if not intervals:return 0intervals.sort(key=lambda x:x[0])heap=[]heapq.heappuch(heap,intervals[0][1])for i in range(1,len(intervals)):if intervals[i][0]>=heap[0]:heapq.heappop(heap)heapq.heappush(heap,intervals[i][1])return len(heap)
我最开始一看，这玩意不就是列表吗，有什么区别，但是后来我发现有点不对劲，这个堆好像还真有说法，他是默认最小堆的，也就是说堆的最上面就是最小值，那不就完了，如果当前会议的开始，比堆顶的最小值还小，那就得开新值了，所以就直接压堆就好了，那如果比对顶的最小值要大，那整挺好，直接pop一个，然后压一个进去，这个逻辑挺好的，
2.堆的使用
import heapq
heap=[]
heapq.heappush(heap,6)
heapq.heappush(heap,7)
heapq.heappush(heap,5)
heapq.heappop(heap)
print(heap)#[6,7] #最小堆heap=[]
heapq.heappush(heap,-6)
heapq.heappush(heap,-7)
heapq.heappush(heap,-5)
heapq.heappop(heap)
print(heap)#[-6,-5]取负值就是最大堆
heap说到底还是列表，所以你只要一直用heapq.heappush和heapq.heappop就不会出问题。
3.找到字符串中所有字母异位词
给定两个字符串 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” 的异位词。
from collections import Counter
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:num=Counter(p)n=len(p)res=[]for i in range(0,len(s)-n+1):if not Counter(s[i:i+n])-num:res.append(i)return res
这个时间复杂度是O(m*n)
那么接下来这个是优化后的：
from collections import Counter
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:res = []p_count = Counter(p)s_count = Counter()n, m = len(p), len(s)for i in range(m):s_count[s[i]] += 1if i >= n:if s_count[s[i - n]] == 1:del s_count[s[i - n]]else:s_count[s[i - n]] -= 1if s_count == p_count:res.append(i - n + 1) return res
4.字典遍历的操作
my_dict = Counter(s)# 将字典转换为列表套元组
tuple_list = list(my_dict.items())
print(tuple_list) #[('a', 1), ('b', 1), ('d', 1)]
res=[]
for i,j in my_dict.items():res.append([i,j])
print(res) #[['a', 1], ['b', 1], ['d', 1]]
5.用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
class Solution:def findMinArrowShots(self, points: list[list[int]]) -> int:# 每只箭尽可能多的穿过，先从多的points.sort(key=lambda x:x[0])res=[points[0]]for i in range(1,len(points)):changed=Falsefor j in range(len(res)): if points[i][0]<=res[j][1]:res[j][0]=max(points[i][0],res[j][0])res[j][1]=min(points[i][1],res[j][1])changed=Truebreakif changed==False:res.append(points[i])return len(res)
合并区间，没啥好说的，但是时间用的特别久 ，不是特别好。
class Solution:def findMinArrowShots(self, points: list[list[int]]) -> int:if not points:return 0# 按气球的右边界排序points.sort(key=lambda x: x[1])res = 1 # 至少需要一支箭end = points[0][1] # 第一支箭的右边界for i in range(1, len(points)):# 如果当前气球的左边界在当前箭的右边界之后，需要一支新的箭if points[i][0] > end:res += 1end = points[i][1] # 更新新的箭的右边界return res贪心算法，就是说，以最大值排序之后，第一个值的右边界，只要能包括最多的气球，那就继续遍历，如果出现第一个左边界大于右边界的，那就更新一个右边界，最后别忘了补一个。不好想。
6.丑数
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
说明：丑数是只包含质因数 2、3 和/或 5 的正整数；1 是丑数。
示例 1：
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
class Solution:def nthUglyNumber(self, n: int) -> int:dp = [1] * n# 初始化三个指针i2 = i3 = i5 = 1# 初始化下一丑数next2, next3, next5 = 2, 3, 5for i in range(1, n):# 选择最小的丑数dp[i] = min(next2, next3, next5)# 更新下一个丑数的值if dp[i] == next2:next2 = dp[i2] * 2i2 += 1if dp[i] == next3:next3 = dp[i3] * 3i3 += 1if dp[i] == next5:next5 = dp[i5] * 5i5 += 1return dp[-1]很好的一个动态规划的题，不过之前的动态规划都是前项动态规划，这个是后项动态规划，把未来的存起来。
