春招第四次算法面试--小米

小米测开的笔试算法题很简单

1.第一题

题目很简单，给一串小字符串和一个大字符串

判断小字符串能不能拼接成大字符串

def read_every_t():
    n, L = input().split(" ")
    n, L = int(n), int(L)
    s = []
    
    s.extend(input().split(" "))
    print(s)
    assert len(s) == n
    un_use = [True] * n
    mubiao = input()
    index = 0
    has_flag = False
    while True:
        for i in range(len(s)):
            print(s[i], index, len(mubiao))
            if s[i][0] == mubiao[index] and un_use[i]:
                if s[i] == mubiao[index:index+len(s[i])]:
                    un_use[i] = False
                    index += len(s[i])
                    has_flag = True
                    break
        if index >= len(mubiao):
                return True
        elif has_flag == False:
                return False

if __name__=="__main__":
    t = int(input())
    for _ in range(t):
        is_ok = read_every_t()
        if is_ok:
            print("True")
        else:
            print("False")

2.第二题

题目，给出一个数组 [2,3,4,5,7,11,15,17,19,...,an] 是必须呆在山上的天数

n 是能在山上待的天数

求最少上下山几次

# 1 上
# 6 下
# 9 上
# 11 下
n, k = input().split(" ")
n, k = int(n), int(k)
days = list(map(int, input().split(" ")))
# print(days)
assert n == len(days)
the_day_under = days[-1] - k
# print(the_day_under)
heap = []
for i in range(1, len(days)):
    free_days = days[i] - days[i-1] - 1
    if free_days > 0:
        heap.append(free_days)

heap = sorted(heap, reverse=True)
for i in range(len(heap)):
    the_day_under -= heap[i]
    if the_day_under <= 0:
        print((i+2) * 2)
        break