数据结构-线程池与任务队列刷题

leetcode 933. 最近的请求次数

解题重点：
1.题目理解比较困难
2.按照范围，依次把队列中的数删除（直到在范围内）

class RecentCounter: 
	def __init__(self): 
		self.requests = [] 
	def ping(self, t: int) -> int: 
		limit_down = max(0, t - 3000) 
		self.requests.append(t) 
		while self.requests[0] < limit_down:
			 self.requests.pop(0) 
		return len(self.requests)
1
2
3
4
5
6
7
8
9

面试题 17.09. 第 k 个数

解题重点：
1.理解素因子的关系，第K个数一定由前k-1个数与3、5、7中的某个数相乘所得
2.记录我们使用过的前K-1个数
3.当我们的3、5、7在使用前k-1个数时，满足条件的值对应的3、5、7都要被记录

class Solution: 
	def getKthMagicNumber(self, k: int) -> int: 
		k_list = [1] 
		P3,P5,P7 = 0,0,0 
		for i in range(1,k): 
			data3 = k_list[P3] * 3 #3--素因子 
			data5 = k_list[P5] * 5 #5--素因子 
			data7 = k_list[P7] * 7 #7--素因子
			k_list.append(min(min(data3,data5),data7))
			if k_list[i] == data3:P3 += 1 
			if k_list[i] == data5:P5 += 1 
			if k_list[i] == data7:P7 += 1 
		return k_list[k - 1]
1
2
3
4
5
6
7
8
9
10
11
12
13

859. 亲密字符串

解题重点：
1.判断是否长度相等
2.判断不相同的次数，如果是0次或者2次则有机会成为亲密字符串

class Solution: 
	def buddyStrings(self, a: str, b: str) -> bool: 
		if len(a) != len(b):
			return False 
			same_num = [] 
			for i in range(len(a)): 
				if a[i] != b[i]: 
					same_num.append(i) 
			if len(same_num) == 2: 
					if a[same_num[0]] == b[same_num[1]] and a[same_num[1]] == b[same_num[0]] 
						return True 
			if len(same_num) == 0: 
				return len(a) > len(set(a)) 
			return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14

860. 柠檬水找零

解题重点：
1.分情况讨论就行
2.注意20元时的找零方法，优先10+5

class Solution: 
	def lemonadeChange(self, bills: List[int]) -> bool: 
		five = 0 
		ten = 0 
		twenty = 0 
		for bill in bills: 
			if bill == 5: 
				five += 1 
			elif bill == 10: 
				if five > 0: 
					five -= 1 
					ten += 1 
				else:
					return False 
			else:
				if ten > 0 and five > 0:#找10快+5快 
					ten -= 1 
					five -= 1 
					twenty += 1 
				elif five >= 3:#3个5快 
					five -= 3 
					twenty += 1 
				else:
					return False 
		return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

leetcode 969. 煎饼排序

解题重点：
1.理解煎饼反转的一个操作
2.每次循环中反转两次，每次先将当前最大的放到第一位，第二次将当前最大的 翻转到当前的最后一位，重复这个操作。
3.给的数据特殊，能够通过length判断最大值

class Solution:
	def pancakeSort(self, arr: List[int]) -> List[int]: 
		max_val = len(arr)#因为生成的数据特性 
		k_list = [] 
		while max_val > 1: 
			max_idx = arr.index(max_val) 
			if max_idx != max_val - 1: 
				arr[:max_idx + 1] = arr[:max_idx + 1][::-1]#到此为第一次反转 
				k_list.append(max_idx + 1)#记录第一次反转 
				arr[:max_val] = arr[:max_val][::-1]#到此为第二次反转
				k_list.append(max_val)#记录第二次反转 
			max_val -= 1#生成数据的特性 
		return k_list 
		# arr = [1,2,3,4] 
		# print(arr[::-1]) ==>123
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

621. 任务调度器

class Solution:
	def leastInterval(self, tasks: List[str], n: int) -> int: 
		count_list = [0 for _ in range(26)] 
		for task in tasks: 
			count_list[ord(task) - ord('A')] += 1 
		List.sort(count_list) 
		max_count = 0 
		for i in range(len(count_list)): 
			if count_list[25] == count_list[len(count_list) - 1 - i]:
				max_count += 1 
			else:
				break #通过上述操作，已经统计了最大之的个数 
		return max(len(tasks),(count_list[25] - 1) * (n + 1) + max_count)
1
2
3
4
5
6
7
8
9
10
11
12
13