腾讯笔试题AC代码

题目可能和大家的有些不一样，题目没存，做了的应该知道题目。。

第1题，压缩算法

大意是将[3|AB]这样的字符串转为ABABAB。这个题典型的做法是递归，因为可能有嵌套的情形。这个题有点像LeetCode 394。

但是，为了追求速度，使用正则表达式直接循环替换，迅速解决。

import re

s = input()
while '[' in s:
    for b in re.findall(r'\[\d+\|[A-Z]+\]', s):
        n, c = re.findall(r'\[(\d+)\|([A-Z]+)\]', b)[0]
        s = s.replace(b, c * int(n))

print(s)

第2题，逆序对

不会。。

第3题，视野争夺

这个其实是LeetCode原题，LeetCode1024，只是把题面变一下。我当时做这个题的时候用的是贪心的算法，不过似乎也有别的解法。

def solve(clips, L):
    if (len(clips) == 0):
        return L == 0
    elif (len(clips) == 1):
        return clips[0][0] == 0 and clips[0][1] == L

    clips.sort(key=lambda c : c[0])
    valid = [True] * len(clips)
    for i in range(len(clips) - 1):
        if valid[i]:
            for j in range(i + 1, len(clips)):
                if clips[i][0] <= clips[j][0] and clips[i][1] >= clips[j][1]:
                    valid[j] = False
                elif clips[j][0] <= clips[i][0] and clips[j][1] >= clips[i][1]:
                    valid[i] = False;
                    break
                elif clips[i][1] >= clips[j][0]:
                    break
    
    valid_clips = [clips[i] for i in range(len(clips)) if valid[i]]

    t = 0 
    pre = -1
    res = 0
    while t < L:
        avail = []
        for i in range(pre + 1, len(valid_clips)):
            if valid_clips[i][0] <= t <= valid_clips[i][1]:
                avail.append(i)
            else:
                break
        if not avail:
            return -1
        avail.sort(key=lambda x : -1 * valid_clips[x][1])
        res += 1
        pre = avail[0]
        t = valid_clips[pre][1]
    return res 


def main():
    n, L = map(int, input().split())
    clips = []
    for i in range(n):
        clips.append(list(map(int, input().split())))
    res = solve(clips, L)
    print(res)
    

if __name__ == '__main__':
    main()

第4题，逛街

大意是，一个高度数组，每个元素上，可以看到多少个元素，高的会挡住矮的。

给人第一感觉就是单调栈，先算出每个元素上，左侧和右侧比自己大的元素索引，再计算每个元素上，从左侧和右侧能看到的元素数。

n = int(input())
W = list(map(int, input().split()))

stk = []
R = [-1] * n
i = 0
while i < n:
    if not stk or W[i] <= W[stk[-1]]:
        stk.append(i)
        i += 1
    else:
        R[stk.pop()] = i

stk = []
L = [-1] * n
i = n - 1
while i >= 0:
    if not stk or W[i] <= W[stk[-1]]:
        stk.append(i)
        i -= 1
    else:
        L[stk.pop()] = i

LL = [0] * n
i = 0
while i < n:
    if L[i] != -1:
        LL[i] = 1 + LL[L[i]]
    i += 1
    
RR = [0] * n
i = n - 1
while i >= 0:
    if R[i] != -1:
        RR[i] = 1 + RR[R[i]]
    i -= 1

res = []
for i in range(n):
    if i == 0 or i == n - 1:
        t = 2
    else:
        t = 3
    if i > 0:
        t += LL[i - 1]
    if i < n - 1:
        t += RR[i + 1]
    res.append(t)
    
print(' '.join(map(str, res)))

第5题，假期

大意是，假期里，每天选择休息、健身或工作，不连续两天健身或工作，最少休息多少天。

不连续两天健身或工作，这意味着前一天做什么会影响第二天的选择，也就是存在状态的转移。

另外，这是个求最优解的问题，因此很容易想到是DP。

n = int(input())
C = list(map(int, input().split()))
G = list(map(int, input().split()))

'''
dp[i][0]  第i天休息
dp[i][1]  第i天工作
dp[i][2]  第i天健身
'''

dp = [[0] * 3 for _ in range(n + 1)]

for i in range(1, n + 1):
    a = dp[i-1][0]
    b, c = 100010, 100010
    if i > 1:
        if C[i-2]:
            b = dp[i-1][1]
        if G[i-2]:
            c = dp[i-1][2]
    dp[i][0] = 1 + min(a, b, c)
    dp[i][1] = min(a, c) + (not C[i-1])
    dp[i][2] = min(a, b) + (not G[i-1])

print(min(dp[-1]))

#腾讯##笔试题目#