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

leetcode 933. 最近的请求次数

解题重点：
裸的的队列题，每次把元素进行入队操作，并且和队首元素进行比较，如果超过3000 毫秒则进行队首元素出队操作，每次返回队列中元素的数量。
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)

面试题 17.09. 第 k 个数

解题重点：
类似数学证明题：
1.生成一个队列，生成3 个指针p3, p5, p7 这三个指针分别对应得是3， 5， 7 ， 分别指向1， p3, p5, p7, 乘以第1 个元素，比较其中大小，选出最小的放入到队列中，然后最小元素的P指针向后移动一位，继续此操作，当p3和 P5 相乘的元素最小的时候，把p3 指针和p5 指针同时向后移动一位。
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]

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

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

leetcode 969. 煎饼排序（这道题的编码技巧比较好玩）

煎饼排序简单来说，就是每次只能反转数组中的第一个元素到第K 个元素的子数组，然后我们每反转一次，就将 k 值 记录下来。
直到这个数组变成有序递增的，就输出我们记录的所有的值。

解题重点：
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

621. 任务调度器

解题思路:

1. 把任务最多的次数安排上，优先安排冷却时间，把出现第二多的安排上。
   二. 要讨论的几种情况，
2. 把所有冷却时间都填满，时间是任务总数量
   n 代表出现的次数，m 种任务 K 冷却时间
   任务总数量：（n – 1）* (k + 1) + m

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)