春招第八、九次算法笔试
第八次是京东的，第九次是得物的 ，都是早上10:00开始，还好得物是10:00-13:00
最后京东做了2H，得物1H
理论题京东的还好，应该能对六七成，得物的最多可能就5成吧，几分钟搞完20题，没认真看
算法题：
京东第一题（前面还有个sql题）：
输入一个字符串和一个数字n，表示可以删掉最多n个字符串，给出删除后字典序最小的
差点因为不知道什么是字典序被克制了，只过了60%的用例，完整的估计是使用线段树的，但不会
# 字符串的字典序是
def get_min_str(s, m):
index = 0
re = ""
the_min_last = min(s[index: min(index + m + 1, len(s))])
max = 0
while m > 0:
the_min = min(s[index: min(index + m + 1, len(s))])
the_min_index = index
# print(s[index : min(index + m + 1, len(s))])
for i in range(index, min(index + m + 1, len(s))):
if s[i] == the_min:
the_min_index = i
break
re += the_min
m -= the_min_index - index
index = the_min_index + 1
# print(the_min, the_min_index, re, m)
print(re + s[index:])
if __name__=="__main__":
get_min_str("abcab", 2)
get_min_str("lkqijxsnny", 4)
京东第二题
有n个任务，m天，初始完成时间都是1，每天其中一个任务的完成时间会增加，给出每天完成其中一个任务需要的最少时间
过了90%的用例，剩下的还是超时了，暂时也不知道该怎么优化
if __name__ == "__main__":
n, m = input().split(" ")
n, m = int(n), int(m)
day_task = {1: list(range(1, n + 1))}
task_day = {task_id: 1 for task_id in range(1, n + 1)}
# print(day_task, task_day)
the_min = 1
for _ in range(m):
task_id, ci = input().split(" ")
task_id, ci = int(task_id), int(ci)
cost = task_day[task_id]
# 更新数据
task_day[task_id] += ci
print("task_id", task_id)
day_task[cost].remove(task_id)
if day_task.get(cost + ci, None) is None:
day_task.update({cost + ci: [task_id]})
else:
day_task[cost + ci].append(task_id)
while len(day_task.get(the_min, [])) == 0:
the_min += 1
# 找到最小的，输出
print(the_min)
print(day_task, task_day)
得物第一题：
题目是 有M个盒子，每个盒子有N*2个块，每一块有红绿两种情况，每次可以把一个绿色改成红色
要求给出至少操作多少次能使得至少 M-1 个盒子中的红色块不少于绿色块，挺简单，AC了
if __name__=="__main__":
N, M = input().split(" ")
N, M = int(N), int(M)
red_list = []
for _ in range(M):
red, green = input().split(" ")
red, green = int(red), int(green)
if red < N:
red_list.append(red)
# print(red_list)
the_min = min(red_list)
red_list.remove(the_min)
sum_green = sum(red_list)
needed = N * len(red_list)
print(needed - sum_green)
得物第二题：
这题自测的用例能通过，提交后通过0%，不知道为什么
题目是有个函数 f(x),返回x的所有因子的和
比如: f(1) = 1, f(2) = 1 + 2 = 3, f(9) = 1 + 3 + 9 = 14, f(19) = 1 + 19 = 20
有另一个函数 g(n) = sum([f(i) for i in range(1, n+1)] )
每次输入一个数m，给出n，使得 g(n) = m,如果不存在则返回-1
def get_prime(n):
prime = [2, 3, 5]
for i in range(6, n):
is_prime = True
for j in prime:
if i % j == 0:
is_prime = False
break
if is_prime:
prime.append(i)
return prime
def get_yinzi(prime, num):
yinzi = [1, num]
for p in prime:
if p < num :
if num % p == 0:
yinzi.append(p)
yinzi.append(num // p)
else:
break
return set(yinzi)
if __name__=="__main__":
t = int(input())
the_m_list = []
for _ in range(t):
the_m_list.append(int(input()))
max_m = max(the_m_list)
prime = get_prime(max_m)
sum_n = {1:1}
for i in range(2, max_m):
yinzi = get_yinzi(prime, i)
sum_n.update({i: sum_n[i-1] + sum(yinzi)})
if sum_n[i] > max_m:
break
n_sum = {sum:n for n,sum in sum_n.items()}
for m in the_m_list:
print(n_sum.get(m, -1))
得物第三题
输入一个列表[1,2,5,6,3,4,5,8,55,6,2,33],求最长递增子序列
好像过了80%或者90%，应该是没AC
if __name__=="__main__":
inp = input()
inp = inp[1:-1]
nums = inp.split(",")
nums = list(map(float, nums))
the_max_len = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i-1, -1, -1):
if nums[j] < nums[i]:
the_max_len[i] = the_max_len[j] + 1
break
elif nums[j] == nums[i]:
the_max_len[i] = the_max_len[j]
break
# print(the_max_len)
print(max(the_max_len))