寬度最小的子矩陣

• 給定一個n行 * m列的矩陣；
• 給定一個k個整數的數組k_list；
• 在n*m的矩陣中找一個寬度最小的子矩陣，該子矩陣包含k_list中所有的整數；
  輸入描述：
  第一行輸入n,m 兩個整數；
  后續n行每行輸入 m個數據；
  輸入k值；
  輸入個整數
  輸出描述：
  最小寬度值，若找不到，則輸出-1

示例1
輸入：
2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 3
輸出：
2
說明，
矩陣第0、3列包含了1、2、3；
矩陣第3、4列包含了1、2、3

示例2
輸入：
2 5
1 2 2 3 1
1 3 2 3 4
3
1 1 4
輸出：
5
思路：

• 滑動的子矩陣
• 從第一列起始，找一個寬度最小的子矩陣；
• 從第二列開始，找一個寬度最小的子矩陣；
• 依次到最后一列…
• 以上的寬度每次取最小值

 
class MinWidth:def solution(self, n, m, matrix, k_list):k_dict = self.to_dict(k_list)min_width = float("inf")# 類似雙指針for start_idx in range(m):for end_idx in range(start_idx, m):temp_list = []# 獲取當前子矩陣的所有元素for i in range(n):temp_list.extend(matrix[i][start_idx:end_idx+1])temp_dict = self.to_dict(temp_list)# 集合操作flag = Truefor key in k_dict:if key in temp_dict and k_dict[key] <= temp_dict[key]:continueelse:flag = Falsebreakif flag:min_width = min(min_width, end_idx - start_idx + 1)breakprint(min_width)def to_dict(self, alist):dict_ = {}for i in alist:dict_[i] = dict_.get(i, 0) + 1return dict_if __name__ == '__main__':min_width = MinWidth()while True:try:n, m = list(map(int, input().strip().split()))matrix = []for i in range(n):matrix.append(list(map(int, input().strip().split())))k = int(input().strip())k_list = list(map(int, input().strip().split()))min_width.solution(n, m, matrix, k_list)except KeyboardInterrupt:break

&nbsp

部門人力分配

• requirements表示開發需求數組，每個值表示當前需求的月數，所有需求需要在m個月內完成；
• 每個月最多有2個需求完成開發；人力安排后每個月人力是固定的；
• 在滿足需求開發進度的情況下，每個月需要的最小人力是多少？
  輸入描述：
  第一行輸入m
  第二行輸入requirements 數組， 值>=1 長度為n;
  1<=n/2<=m<=n<=10000
  輸出描述：
  輸出部門需要的人力？

示例1
輸入：
3
3 5 3 4
輸出：
6
說明：
開發時間為5個月的需求在一個月內完成，則需要5個人；
3 3 合并到一個月完成，需要6個人力；
3 4合并到一個月完成，需要7個人力；
4 5合并到一個月完成，需要9個人力;

示例2
輸入：
3
3 3 4 5 6
輸出：
8

示例3
輸入：
3
3 3 4 5 6 2
輸出：

思路：

• n個需求，n個月完成需要的人力較少，m個月完成人力增加；
• n個需求在m個月內完成，當n==m時，取requirements的最大值；
• n>m時，requirements升序排序，依次取出不需要合并的最大值放入temp_list，直到n==m的情況；
  • 剩余需要合并的數對，利用雙指針進行兩兩合并（最大值組合一個最小值），求的和放入temp_list;
  • 最終 temp_list 長度會等于m，此時取temp_list的最大值即可；

class LeastResource:def solution(self, requirements, m):n = len(requirements)requirements.sort()temp_list = []if n == m:result = max(requirements)print(result)else:while n / 2 < m:temp_list.append(requirements.pop())n -= 1m -= 1# 剩余需求 需要兩兩組合self.merge(temp_list, requirements)result = max(temp_list)print(result)def merge(self, temp_list, requirements):cur_n = len(requirements)pre = 0cur = cur_n - 1while pre < cur:cur_sum = requirements[pre] + requirements[cur]temp_list.append(cur_sum)pre += 1cur -= 1if __name__ == '__main__':least_resource = LeastResource()while True:try:m = int(input().strip())requirements = list(map(int, input().strip().split()))least_resource.solution(requirements, m)except KeyboardInterrupt:break

二分法
最小人力范圍在requirements的最大值—最大值+次最大值 之間；

m = int(input())
nums = [int(x) for x in input().split(" ")]
nums.sort()def cal(k, nums, length) :low = 0high = length - 1months = 0while (True) :if(low > high):breakelse :if (nums[low] + nums[high] > k) :high -= 1else :low += 1high -= 1months+=1return monthslow = nums[len(nums)-1]
high = nums[len(nums)-1] + nums[len(nums)-2]result = -1
while (True) :if(low > high):breakelse :k = int((low + high) / 2)if (cal(k, nums, len(nums)) <= m) :high = k - 1result = kelse :low = k + 1
print(result)

?

電腦病毒感染

• 一個局域網內有n臺電腦，編號為 0 -> n-1，電腦之間病毒感染時間用t表示；
• 現在網絡內已有一臺電腦被病毒感染；
• 求其感染所有其他電腦最少的時間，若最后有電腦不會感染，則返回-1;
• 數組times 表示一臺電腦把相鄰的電腦感染所用的時間；
• path[i] = {i, j, t} 表示 電腦i 感染 電腦j 所用的時間t;
  輸入描述：
  第一行輸入n 在[1, 200]
  第二行輸入m, 表示m條網絡；
  后m行，每行輸入i,j,t, 1<=i,j<=n
  最后一行輸入攜帶病毒的電腦編號；
  輸出描述：
  感染全部電腦的最少時間，不能感染全部輸出-1

示例1
輸入：
4
3
2 1 1
2 3 1
3 4 1
2
輸出：
2

思路

• 單源最短路徑

 
n = int(input())
count = int(input())
time = [float('inf') for i in range(n)]matrix=[[0 for i in range(3)] for j in range(count)]
for j in range(count):nums = [int(x) for x in input().split(" ")]matrix[j][0] = nums[0] matrix[j][1] =nums[1]matrix[j][2] = nums[2]start = int(input())
time[start-1] = 0for i in range(n):for j in range(count):   if (time[matrix[j][0]-1] + matrix[j][2] < time[matrix[j][1]-1]) :time[matrix[j][1]-1] = time[matrix[j][0]-1] + matrix[j][2]result = 0
i=0
while(True):if(i>=n):print(result)breakelse :if (time[i] == float('inf')) :print(-1)breakif(time[i]>result):result = time[i]i+=1

?

會議室占用時間段

 
meetings = [[1,4], [2,5],[7,9], [14,18]]
def merge(meetings) :sorted(meetings,key=lambda x: (x[1],x[0]))result = []result.append(meetings[0])cur = result[0]i=1while(True):if(i>=len(meetings)):breakelse :if (cur[1] >= meetings[i][0] and cur[1] <= meetings[i][1]) :cur[1] = meetings[i][1]elif(cur[1] > meetings[i][1]):passelse :result.append(meetings[i])cur = meetings[i]i+=1print(result)return result
merge(meetings)