春招第八、九次算法笔试

第八次是京东的，第九次是得物的 ，都是早上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))