腾讯后台开发 笔试 2、3题

第一题暴力了也只是10%，可能菜是原罪

第二题 字符串操作 使字符串中不能出现 "01" 和 "10"

# 1
if __name__ == '__main__':
    n = int(input())
    line = input()
    # 每次检查字符串的起点，减小时间复杂度
    start = 0
    while True:
        # flag 判断是否还存在非法字符串
        flag = True
        for k in range(start, len(line)):
            try:
                if line[k] == '0' and line[k+1] == '1' or line[k] == '1' and line[k+1] == '0':
                    line = line[:k] + line[k + 2:]
                    flag = False
                    start = max(k - 1, 0)
                    break
            except:
                break
        if flag:
            break
    print(len(line))

# 2
if __name__ == '__main__':
    n = int(input())
    line = input()
    _map = {
        '1': 0,
        '0': 0
    }
    for i in line:
        _map[i] += 1
    print(abs(_map['1']-_map['0']))

第三题 给怪兽付金币，求最小付出，雇佣的怪兽会一直守护，遇见的怪兽战力必须小于等于已经雇佣的怪兽战力总和。

def dp(_fight, _money):
    if len(_fight) == 1:
        return [_fight[0], _money[0]]
    _fight_num, _need = dp(_fight[:-1], _money[:-1])
    # 遇见的怪兽战力必须小于等于已有的战力总和，才可以不雇佣
    if _fight[-1] > _fight_num:
        return [_fight_num+_fight[-1], _need+_money[-1]]
    # 如果雇佣当前的怪兽付出的总金额小于下一个遇见的怪兽的保护费，则雇佣当前怪兽
    elif _need + _money[-1] < money[len(_money)]:
        return [_fight_num+_fight[-1], _need+_money[-1]]
    return [_fight_num, _need]


if __name__ == '__main__':
    _ = input()
    fight = list(map(int, input().split()))
    money = list(map(int, input().split()))
    # 防止越界
    fight.append(0)
    money.append(0)
    fight_num, need = dp(fight[:-1], money[:-1])
    print(need)