100分值题
- 生成Huffman树
- 小朋友来自多少小区
- 堆内存申请
- 跳格子3
- 测试用例执行计划
- 路口最短时间问题
- 贪吃的猴子
- 小扇和小船的数字游戏
- 幸存数之和
- CPU算力分配
- 5G网络建设
- 亲子游戏
- 传递悄悄话
- 宽度最小的子矩阵
- 部门人力分配
- 电脑病毒感染
- 会议室占用时间段
生成Huffman树
- 给定一个数值数组weights，每个值代表二叉树叶子节点的权值（>=1）;
- 根据权值数组，生成哈夫曼树，并中序遍历输出；
- 左节点权值<= 右节点权值，根节点权值为左右节点权值之和；
- 左右节点权值相同时，左子树高度<=右子树;
输入描述：
第一行输入数组长度n;
第二行输入权值，以空格分隔；
输出描述：
哈夫曼树的中序遍历序列，以空格分隔；
示例1
输入：
5
5 15 40 30 10
输出：
40 100 30 60 15 30 5 15 10
==思路：==建立哈夫曼树的过程
- 以每个权值创建一个节点（只有一个树根的二叉树），放入nodes_list，并按照权值从小到大排序；
- 取出权值最小的两个节点，进行合并，根节点权值为左右子节点的权值之和
- 设置根节点的左子树、右子树
- 当左右子树（根节点）权值相同时，对比两者的树高，高的子树作为右子树；
- 统计子树的高度 max(h_left, h_right)，h_left为每次取左子树；
- 将合并后的root根节点放入nodes_list，继续以上步骤，直到nodes_list中只有一个根节点；
# 中序遍历结果
result = []
# 输入n
n = int(input().strip())
weights = [int(x) for x in input().strip().split()]
class TreeNode:
def __init__(self, left, right, weight, height):
self.left = left
self.right = right
self.weight = weight
self.height = height
# 中序遍历
def dfs(node):
# 中序遍历左子树
if node.left is not None:
dfs(node.left)
# 中间处理根
result.append(node.weight)
# 中序遍历右子树
if node.right is not None:
dfs(node.right)
# 建立哈夫曼树
nodes_list = []
for i in range(n):
nodes_list.append(TreeNode(None, None, weights[i], 1))
# 比较树高
def comp(o1, o2):
if(o1.weight == o2.weight): # 权值相等
if o1.height > o2.height:
return 1
else:
return -1
if o1.weight > o2.weight:
return 1
else:
return -1
while True:
if len(nodes_list) == 1:
break
else :
nodes_list = sorted(nodes_list, key=lambda i:i.weight)
node1 = nodes_list.pop(0)
node2 = nodes_list.pop(0)
root = TreeNode(None, None, node1.weight + node2.weight, max(node1.height, node2.height) + 1)
if comp(node1, node2) == 1:
root.right = node1
root.left = node2
else:
root.right = node2
root.left = node1
nodes_list.append(root)
dfs(nodes_list[0]) # 传入树根，中序遍历
# 输出字符串
output_str = ""
for i in range(len(result)):
output_str += str(result[i])
if(i!=len(result)-1):
output_str+=" "
print(output_str)
小朋友来自多少小区
- 每个小朋友报出与自己同一个小区的人数，存入数组garden中；
- 计算至少有几个小区？多少小朋友？
输入描述：
输入garden数组，如2 2 3， 即第一个小朋友报出有2个小朋友跟自己同一个小区，第二个小朋友同样报出2个，依次类推; garden数组长度最大为999；
输出描述：
至少的小区数，小朋友数
示例1
输入：
2 2 3
输出：
2，7
示例2
输入：
2 2 2 2 2 3 3
输出：
3,10
思路：
- 贪心算法，依次遍历，让尽可能多的小朋友在同一个小区；
- garden 升序排序；
- 初始化 小区数areas=1, friend_nums = garden[0]+1，dist= garden[0]
- 从i=1开始遍历garden，for i in range(1, len(garden)): 如果当前报数与前一个报数相同，则判断能否算入同一个小区；
- 是，则dist-=1，继续下一次遍历；
- 否，则areas += 1, friend_nums += garden[i] +1, dist=garden[i]
- 输出areas,friend_nums
class GardenNum:
def solution(self, garden):
# 排序
garden.sort()
# 初始化
areas = 1
friend_nums = garden[0] + 1
dist = garden[0]
for i in range(1, len(garden)):
if garden[i] == garden[i-1]: # 可能是同一个小区
if dist > 0:
# 算入同一个小区
dist -= 1
else:
areas += 1 #
friend_nums += garden[i] + 1
dist = garden[i]
else:
# 报数与前一个不同，肯定不是同一个小区
areas += 1 #
friend_nums += garden[i] + 1
dist = garden[i]
print(areas, end=",")
print(friend_nums)
if __name__ == '__main__':
garden_num = GardenNum()
while True:
try:
garden = list(map(int, input().strip().split()))
garden_num.solution(garden)
except KeyboardInterrupt:
break
其他基于索引的实现：
nums = [int(x) for x in input().split(" ")]
#index为报告的结果，zones[index]为报告相同结果的总人数
zones = [0 for x in range(1000)]
count = 0
i=0
while(True):
if(i>=len(nums)):
break
else:
zones[nums[i]]+=1
i+=1
for j in range(1000):
if (zones[j] <= 0):
continue
else:
total = math.ceil(zones[j] / (j+1));
count += total * (j+1);
print(count);
堆内存申请
n = int(input())
memorys = []
while (True) :
try:
nums = [int(x) for x in input().split(" ")]
memorys.append([nums[0], nums[0]+nums[1]- 1])
except:
break
memorys.sort()
length = len(memorys)
flag = 0
for i in range(length):
x = memorys[i][0]
y = memorys[i][1]
if (not ((x >= 0 and y >= 0 and x < 100 and y < 100 and x <= y) and
(not (i > 0 and x <= memorys[i-1][1])))) :
flag = 1
break
if (flag!=1) :
offset = -1
max_distance = 100
start = memorys[0][0]
if (start >= n and start < max_distance + n) :
offset = 0
max_distance = start - n
i=1
while(True):
if(i>=length):
break
else :
current = memorys[i][0]
before = memorys[i-1][1]
if (current - before > n):
if(current - before < max_distance + n) :
offset = before + 1
max_distance = current - before - n
break
i+=1
end = memorys[length - 1][1]
if (end<=99-n and end > 99-n-max_distance) :
offset = end + 1
print(offset)
else:
print(-1)
跳格子3
n =int(input())
nums = [int(x) for x in input().split(" ")]
k = int(input())
queue = [[0 for i in range(2)] for j in range(n)]
cache =[0 for i in range(n)]
cache[0] = nums[0]
queue[0][0] = 0
queue[0][1] = cache[0]
index1 = 0
index2 = 1
i=1
while(True):
if(i>=n):
break
else :
while(index1<index2):
if(queue[index1][0] < i - k):
index1 +=1
else :
break
cache[i] = nums[i] + queue[index1][1]
while(index1<index2):
if(queue[index1][1] <= cache[i]):
index1 +=1
else :
break
queue[index2][0] = i
queue[index2][1] = cache[i]
index2+=1
i+=1
print(cache[n - 1])
测试用例执行计划
import functools
import sys
import copy
import re
import math
import queue
nums = [int(x) for x in input().split(" ")]
n = nums[0]
m = nums[1]
prioritys = []
for i in range(n):
prioritys.append(int(input()))
list_a =[]
for i in range(m):
nums1 = [int(x) for x in input().split(" ")]
total = 0
for j in range(len(nums1)):
total += prioritys[nums1[j]-1]
list_a.append([i + 1, total])
list_a =sorted(list_a, key=lambda x : (-x[1],x[0]))
for i in range(len(list_a)):
print(list_a[i][0])
路口最短时间问题
directions = [[-1,0],[0,1],[1,0],[0,-1]]
def calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd) :
result = [[[float('inf') for i in range(4)] for j in range(colEnd+1)] for k in range(rowEnd+1)]
pq = queue.PriorityQueue()
for i in range(4):
pq.put([0, [rowStart, colStart, i, 0]])
result[rowStart][colStart][i] = 0
while (True) :
if(pq.qsize()<=0):
break
else :
point_t = pq.get()
point = point_t[1]
if (point[3] > result[point[0]][point[1]][point[2]]) :
continue
for i in range(4):
if (not(directions[i][0] == 1 and directions[i][1] == 0)) :
new_dir = (point[2] + i) % 4
new_x = point[0] + directions[new_dir][0]
new_y = point[1] + directions[new_dir][1]
if (new_x >= 0 and new_x < len(lights) and new_y >= 0 and new_y < len(lights[new_x])) :
new_speed = point[3] + timePerRoad
if (not(directions[i][0] == 0 and directions[i][1] == 1)):
new_speed += lights[point[0]][point[1]]
if (new_speed < result[new_x][new_y][new_dir]) :
result[new_x][new_y][new_dir] = new_speed
pq.put([new_speed, [new_x, new_y, new_dir, new_speed]])
return min(min(result[rowEnd][colEnd][0],result[rowEnd][colEnd][1]), result[rowEnd][colEnd][2])
lights = [[1,2,3],[4,5,6],[7,8,9]]
timePerRoad = 60
rowStart = 0
colStart = 0
rowEnd = 2
colEnd = 2
print(calcTime(lights,timePerRoad, rowStart,colStart, rowEnd, colEnd))
贪吃的猴子
n = int(input())
nums = [int(x) for x in input().split(" ")]
count = int(input())
temp_sum = 0
for i in range(count):
temp_sum += nums[i]
result = temp_sum
left = count - 1
right = n - 1
while (True):
if(left < 0):
break
else :
temp_sum += nums[right] - nums[left]
if(temp_sum>result):
result = temp_sum
right-=1
left-=1
print(result)
小扇和小船的数字游戏
def getBinaryOneCount(num):
count = 0
while(True):
if(num <=0):
break
else :
count += num % 2
num = int(num/2)
return count
n = int(input())
m = n+1
while(True):
if (getBinaryOneCount(m) == getBinaryOneCount(n)):
break
m+=1
print(m)
幸存数之和
pass
CPU算力分配
params = [int(x) for x in input().split(" ")]
count1 = params[0]
count2 = params[1]
nums1 = [int(x) for x in input().split(" ")]
sum1 = sum(nums1)
nums2 = [int(x) for x in input().split(" ")]
sum2 = sum(nums2)
num2_map = {}
for key in nums2:
num2_map[key] = 1
nums1.sort()
i=0
while(True):
if(i>=count1):
break
else :
target = nums1[i] - int((sum1-sum2)/2)
if (target in num2_map) :
print(str(nums1[i]) + " " + str(target))
break
i+=1
5G网络建设
class UF:
def __init__(self, n):
self.root = [i for i in range(n+1)]
self.rank = [1 for i in range(n+1)]
self.count = 0
def find(self,x):
if (x == self.root[x]):
return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self,x, y):
self.root[self.find(x)] = self.find(y)
self.count+=1
def get_count(self):
return self.count
n = int(input())
m = int(input())
uf = UF(n)
networks = []
for i in range(m):
data = [int(x) for x in input().split(" ")]
if (data[3] == 1):
if (uf.find(data[0]) != uf.find(data[1])):
uf.union(data[0], data[1])
else:
networks.append([data[0],data[1],data[2]])
sorted(networks, key=lambda x : x[2])
result = 0
i=0
while(True):
if(i>=len(networks)):
break
else:
if (uf.find(networks[i][0]) != uf.find(networks[i][1])):
uf.union(networks[i][0], networks[i][1])
result += networks[i][2]
if (uf.get_count() == n - 1):
break
i+=1
if(uf.get_count() != n - 1):
result = -1
print(result)
亲子游戏
class Cell:
def __init__(self, x,y):
self.x = x
self.y = y
directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
n = int(input())
matrix = []
for i in range(n):
matrix.append([int(x) for x in input().split(" ")])
start = Cell(0,0)
end= Cell(0,0)
for i in range(n):
for j in range(n):
if(matrix[i][j] == -3):
start.x = i
start.y = j
if(matrix[i][j] == -2):
end.x = i
end.y = j
visited = [[0 for i in range(n)] for j in range(n)]
candys = [[-1 for i in range(n)] for j in range(n)]
#第一轮BFS找到最短时间
queue = []
queue.append(start)
time = 0
flag = 0
while (True):
if(len(queue)<=0) :
break
else :
size = len(queue)
for k in range(size):
cur = queue.pop(0)
if (cur.x == end.x and cur.y == end.y) :
flag = 1
break
for i in range(4):
xx = cur.x + directions[i][0]
yy = cur.y + directions[i][1]
if (xx >= 0 and xx < n and yy >= 0 and yy < n
and visited[xx][yy]==0 and matrix[xx][yy] != -1) :
visited[xx][yy] = 1
temp = Cell(xx,yy)
queue.append(temp)
if(flag==1):
break
time += 1
if(flag==0):
print(-1)
else:
#第二轮BFS找到最大糖果数
candy_queue = []
candy_queue.append(start)
candys[start.x][start.y]=0
while(True):
if(time <0):
break
else :
size = len(candy_queue)
for k in range(size):
cur = candy_queue.pop(0)
for i in range(4):
xx = cur.x + directions[i][0]
yy = cur.y + directions[i][1]
if (xx >= 0 and xx < n and yy >= 0 and yy < n
and matrix[xx][yy] != -1) :
if(candys[xx][yy] == -1):
temp = Cell(xx,yy)
candy_queue.append(temp)
if(matrix[xx][yy] != -2):
if(candys[cur.x][cur.y] + matrix[xx][yy] > candys[xx][yy]):
candys[xx][yy] = candys[cur.x][cur.y] + matrix[xx][yy]
else :
if(candys[cur.x][cur.y] > candys[xx][yy]):
candys[xx][yy] = candys[cur.x][cur.y]
time -=1
print(candys[end.x][end.y])
传递悄悄话
queue = []
result = 0
nums = [int(x) for x in input().split(" ")]
queue.append(0)
def check(index, father):
global nums,result
if (index < len(nums) and nums[index] != -1) :
nums[index] += nums[father]
queue.append(index)
if(nums[index]>result):
result = nums[index]
while (True):
if(len(queue)<=0):
break
else :
father = queue.pop(0)
#左节点
check(2 * father+1,father)
#右节点
check(2 * father+2, father)
print(result)
宽度最小的子矩阵
def check(cur_map, target_map) :
for i in range(1000):
if (cur_map[i] < target_map[i]) :
return False
return True
params = [int(x) for x in input().split(" ")]
n = params[0]
m = params[1]
matrix = []
for i in range(n):
matrix.append([int(x) for x in input().split(" ")])
k = int(input())
nums = [int(x) for x in input().split(" ")]
#每一列，出现数字的个数
count_map = [[0 for i in range(1000)] for j in range(m)]
for i in range(n):
for j in range(m):
count_map[j][matrix[i][j]] +=1
target_map = [0 for i in range(1000)]
for i in range(k):
target_map[nums[i]]+=1
cur_count_map = [0 for i in range(1000)]
width = float('inf')
left = 0
right = 0
while(True):
if(right>=m):
break
else :
for i in range(1000):
cur_count_map[i] += count_map[right][i]
while (check(cur_count_map, target_map)) :
if(right - left + 1 < width):
width = right - left + 1
for i in range(1000):
cur_count_map[i] -= count_map[left][i]
left+=1
right += 1
if(width == float('inf')):
print(-1)
else :
print(width)
部门人力分配
m = int(input())
nums = [int(x) for x in input().split(" ")]
nums.sort()
def cal(k, nums, length) :
low = 0
high = length - 1
months = 0
while (True) :
if(low > high):
break
else :
if (nums[low] + nums[high] > k) :
high -= 1
else :
low += 1
high -= 1
months+=1
return months
low = nums[len(nums)-1]
high = nums[len(nums)-1] + nums[len(nums)-2]
result = -1
while (True) :
if(low > high):
break
else :
k = int((low + high) / 2)
if (cal(k, nums, len(nums)) <= m) :
high = k - 1
result = k
else :
low = k + 1
print(result)
电脑病毒感染
https://blog.csdn.net/m0_70980326/article/details/133862402
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] = 0
for 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)
break
else :
if (time[i] == float('inf')) :
print(-1)
break
if(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=1
while(True):
if(i>=len(meetings)):
break
else :
if (cur[1] >= meetings[i][0] and cur[1] <= meetings[i][1]) :
cur[1] = meetings[i][1]
elif(cur[1] > meetings[i][1]):
pass
else :
result.append(meetings[i])
cur = meetings[i]
i+=1
print(result)
return result
merge(meetings)
