牛客网试题

牛客网 —— 腾讯2020校园招聘试题解答

Posted by Jack on 2020-04-20
Words 3.9k and Reading Time 16 Minutes
Viewed Times

传送门：腾讯2020校园招聘试题

1. 压缩算法

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 256M，其他语言512M

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为m|S，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入描述:

输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述:

输出一个字符串，代表解压后的字符串。

输入例子1:

HG[3|B[2|CA]]F

输出例子1:

HGBCACABCACABCACAF

例子说明1:

HG[3|B[2|CA]]F −> HG[3|BCACA]F −> HGBCACABCACABCACAF

1.1 解题思路

这个题其实是括号匹配问题，是栈的经典应用。解题思路如下：
（1）遍历输入字符串，如果不是右括号，则直接压栈；
（2）如果是右括号，则依次出栈直到弹出左括号，这里需要还原被压缩的子串，并压栈；
（3）最后取出栈中子串进行拼接得到结果。

1.2 Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string = input()
stack = []
for s in string:
    if s != ']':
        stack.append(s)
    else:
        temp = ''
        while stack[-1] != '[':
            temp = stack[-1] + temp
            stack.pop(-1)
        stack.pop(-1)
        n, subs = temp.split('|')
        temp = subs * int(n)
        stack.append(temp)
ans = ''.join(stack)
print(ans)

2. 逛街

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 256M，其他语言512M

小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

输入描述:

输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字w_i(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=w_i<=100000;

输出描述:

输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。

输入例子1:

6
5 3 8 3 2 5

输出例子1:

3 3 5 4 4 4

例子说明1:

当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，
加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，
向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。

2.1 解题思路

这个题可以用动态规划的思想来解决，其方程如下：

i=0:        dp[i] = 2 + dp_r[i+1]
i=n-1:      dp[i] = 2 + dp_l[i-1]
i=[1,n-2]:  dp[i] = 3 + dp_l[i-1] + dp_r[i+1]

dp[i] 表示当前位置能够看到的总楼栋数目，dp_l[i] 表示当前位置向前看到的楼栋数目，dp_r[i] 表示当前位置向后看到的楼栋数目。需要注意的是计算 dp_l 和 dp_r 的时候，是不包含当前楼栋的。

2.2 Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
n = int(input())
nums = input().split()
maxl, maxr = [int(nums[0])], [int(nums[-1])]

dp = [0] * n
dp_l = [0] * n
dp_r = [0] * n
for i in range(1, n + 1):
    # 计算 dp_left
    if i < n:
        if int(nums[i-1]) > int(nums[i]):
            dp_l[i] = 1 + dp_l[i - 1]
        else:
            while maxl and maxl[-1] <= int(nums[i]):
                maxl.pop(-1)
            dp_l[i] = len(maxl)
        maxl.append(int(nums[i]))

    # 计算 dp_right
    if i > 1:
        if int(nums[-i]) < int(nums[-i + 1]):
            dp_r[-i] = 1 + dp_r[-i + 1]
        else:
            while maxr and maxr[-1] <= int(nums[-i]):
                maxr.pop(-1)
            dp_r[-i] = len(maxr)
        maxr.append(int(nums[-i]))

for i in range(n):
    if i == 0:
        dp[i] = str(2 + dp_r[i + 1])
    elif i == n - 1:
        dp[i] = str(2 + dp_l[i - 1])
    else:
        dp[i] = str(3 + dp_l[i - 1] + dp_r[i + 1])

ans = ' '.join(dp)
print(ans)

3. 逆序对

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 256M，其他语言512M

作为程序员的小Q，他的数列和其他人的不太一样，他有 2n 个数。
老板问了小Q一共 m 次，每次给出一个整数 qi, 要求小Q把这些数每 2qi 分为一组，然后把每组进行翻转，小Q想知道每次操作后整个序列中的逆序对个数是多少呢？

例如:
对于序列1 3 4 2，逆序对有(4, 2),(3, 2), 总数量为2。
翻转之后为2 4 3 1，逆序对有(2, 1),(4, 3), (4, 1), (3, 1), 总数量为4。

输入描述:

第一行一个数n(0 <= n <= 20)
第二行2^n个数，表示初始的序列(1 <= 初始序列 <= 10^9)
第三行一个数m(1 <= m <= 10^6)
第四行m个数表示q_i(0 <= q_i <= n)

输出描述:

m行每行一个数表示答案。

输入例子1:

2
2 1 4 3
4
1 2 0 2

输出例子1:

0
6
6
0

例子说明1:

初始序列2 1 4 3
2^{q_1} = 2 ->
第一次：1 2 3 4 -> 逆序对数为0
2^{q_2} = 4 ->
第二次：4 3 2 1 -> 逆序对数为6
2^{q_3} = 1 ->
第三次：4 3 2 1 -> 逆序对数为6
2^{q_4} = 4 ->
第四次：1 2 3 4 -> 逆序对数为0

3.1 解题思路

这个题很容易被题目迷惑，最容易想到的方法是每次先将序列翻转后，再去求翻转序列的逆序对数目（关于求解逆序对数目的方法，可以参考这篇博客）。但是，这种做法的时间复杂度太高，无法通过所有的测试用例。
这里提供另外一种的思路，就是根据顺序对和逆序对之间的关系来求解。简单地说，原序列翻转后的逆序对数目，等于原序列的顺序对数目。比如：

原序列为：2, 1, 4, 3
顺序对有(2,4)、(2,3)、(1,4)、(1,3)共4对。

翻转后的序列为：3, 4, 1, 2
逆序对有(3,1)、(3,2)、(4,1)、(4,2)共4对。

因此，每次按照长度 k 翻转之后，其实只需要把长度不超过 k 的顺序对数目和逆序对数目交换，然后对长度不超过 k 的逆序对数目求和就得到总的逆序对数目。

3.2 Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def merge(nums, left_begin, left_end, right_begin, right_end, index, count):
    # 最后拷贝回 nums 的起始位置
    nums_begin = left_begin
    # 用来存储排序后的结果
    sorted_list = [0] * (right_end - left_begin + 1)
    # 计算逆序对的数目
    cnt = 0
    i = 0
    while left_begin <= left_end and right_begin <= right_end:
        # 发现逆序对，如果左边最小值大于右边最小值，则左边所有值都能构成逆序对
        if nums[left_begin] > nums[right_begin]:
            cnt += (left_end - left_begin + 1)
            sorted_list[i] = nums[right_begin]
            right_begin += 1
        else:
            sorted_list[i] = nums[left_begin]
            left_begin += 1
        i += 1
    # 左边有剩余未参与比较的
    while left_begin <= left_end:
        sorted_list[i] = nums[left_begin]
        left_begin += 1
        i += 1
    # 右边有剩余未参与比较的
    while right_begin <= right_end:
        sorted_list[i] = nums[right_begin]
        right_begin += 1
        i += 1
    # 最后将 sorted_list 拷贝回 nums 中
    for num in sorted_list:
        nums[nums_begin] = num
        nums_begin += 1
    # 保存逆序对数目
    count[index] += cnt


# 归并思想求逆序对
def merge_sort(nums, begin, end, index, count):
    if begin >= end:
        return
    mid = (begin + end) // 2
    merge_sort(nums, begin, mid, index-1, count)
    merge_sort(nums, mid+1, end, index-1, count)
    merge(nums, begin, mid, mid+1, end, index, count)


n = int(input())
nums = list(map(int, input().split()))
m = int(input())
q = input().split()

reorder = [0] * (n + 1)
order = [0] * (n + 1)
reverse_nums = list(reversed(nums))
# 求最初不同长度的逆序对数目
merge_sort(nums, 0, len(nums) - 1, n, reorder)
# 求最初不同长度的顺序对数目
merge_sort(reverse_nums, 0, len(nums) - 1, n, order)

for i in range(m):
    k = int(q[i])
    ans = 0
    # 将长度不超过 k 的逆序对数目与顺序对数目交换
    # 然后对长度不超过 k 的逆序对数目求和就得到总的逆序对数目
    for j in range(1, k + 1):
        reorder[j], order[j] = order[j], reorder[j]
    ans = sum(reorder[1:])
    print(ans)

4. 假期

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 256M，其他语言512M

由于业绩优秀，公司给小Q放了 n 天的假，身为工作狂的小Q打算在在假期中工作、锻炼或者休息。他有个奇怪的习惯：不会连续两天工作或锻炼。只有当公司营业时，小Q才能去工作，只有当健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，求小Q最少需要休息几天。

输入描述:

第一行一个整数 n(1 <= n <= 10^5) 表示放假天数
第二行 n 个数 每个数为0或1,第 i 个数表示公司在第 i 天是否营业
第三行 n 个数 每个数为0或1,第 i 个数表示健身房在第 i 天是否营业
（1为营业 0为不营业）

输出描述:

一个整数，表示小Q休息的最少天数

输入例子1:

4
1 1 0 0
0 1 1 0

输出例子1:

2

例子说明1:

小Q可以在第一天工作，第二天或第三天健身，小Q最少休息2天

4.1 解题思路

首先我们定义小Q每天的状态如下：

-1：  rest，在家休息
 0：  company，在公司工作
 1：  sports，在健身房锻炼
 2:   do any，在公司工作 或 在健身房锻炼

于是对于任意一天i（注意要保证 i 的有效性），有下列的几种情况：
（1）如果第 i 天公司和健身房都营业：

a. 第 i-1 天去了公司，那么第 i 天就去健身房，状态为1
b. 第 i-1 天去了健身房，那么第 i 天就去公司，状态为0
c. 第 i-1 天在家，那么第 i 天就可以去健身房或去公司，状态为2

（2）如果第 i 天只有公司营业：

a. 第 i-1 天没有去公司，那么第 i 天就去公司，状态为0
b. 第 i-1 天可能去了健身房或公司，若第 i-2 天没有去公司，那么第 i 天就去公司，状态为0

（3）如果第 i 天只有健身房营业：

a. 第 i-1 天没有去健身房，那么第 i 天就去健身房，状态为1
b. 第 i-1 天可能去了健身房或公司，若第 i-2 天没有去健身房，那么第 i 天就去健身房，状态为1

4.2 Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
n = int(input())
company = input().split()
sports = input().split()

# status: -1 - rest, 0 - company, 1 - sports, 2 - do any
status = [-1] * n
for i in range(n):
    # 公司、健身房都营业
    if (int(sports[i]) & int(company[i])) == 1:
        if i >= 1 and status[i-1] == 0:     # 昨天去公司，今天就去健身
            status[i] = 1
        elif i >= 1 and status[i-1] == 1:   # 昨天去健身，今天就去公司
            status[i] = 0
        else:                           # 否则就是 do any
            status[i] = 2
    else:
        # 标识今天是否去公司
        comp_flag = False
        # 只有公司营业
        if int(company[i]) == 1:
            if i == 0:    # 第一天
                status[i] = 0
                comp_flag = True
            else:
                if status[i-1] == 2:    # 昨天是 do any
                    if i == 1:
                        status[i] = 0
                        comp_flag = True
                    elif i >= 2 and status[i-2] != 1:    # 前天没去健身房（如果前天去了，那么昨天就去公司了）
                        status[i] = 0
                        comp_flag = True
                elif status[i-1] != 0:    # 昨天没有去公司
                    status[i] = 0
                    comp_flag = True
        # 只有健身房营业
        if int(sports[i]) == 1:
            if not comp_flag:
                if i == 0:    # 第一天
                    status[i] = 1
                else:
                    if status[i-1] == 2:    # 昨天是 do any
                        if i == 1:
                            status[i] = 1
                        elif i >= 2 and status[i-2] != 0:    # 前天没去公司（如果前天去了，那么昨天就去健身房了）
                            status[i] = 1
                    elif status[i-1] != 1:    # 昨天没有去健身房
                        status[i] = 1
print(status.count(-1))

5. 视野争夺

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M

小Q在进行一场竞技游戏,这场游戏的胜负关键就在于能否能争夺一条长度为L的河道,即可以看作是[0,L]的一条数轴。
这款竞技游戏当中有n个可以提供视野的道具−真视守卫,第i个真视守卫能够覆盖区间[xi,yi]。现在小Q想知道至少用几个真视守卫就可以覆盖整段河道。

输入描述:

输入包括n+1行。
第一行包括两个正整数n和L(1 <= n <= 10^5, 1 <= L <= 10^9)
接下来的n行,每行两个正整数x_i,y_i(0 <= x_i <= y_i <= 10^9), 表示第i个真视守卫覆盖的区间。

输出描述:

一个整数，表示最少需要的真视守卫数量, 如果无解, 输出-1。

输入例子1:

4 6
3 6
2 4
0 2
4 7

输出例子1:

3

5.1 解题思路

这是一个区间覆盖问题，解决这类问题的步骤如下：
（1）首先对区间进行从小到大排序（按照左边界排序，若左边界相同则对右边界排序）；
（2）判断排序后区间的最小左边界和最大右边界能否覆盖整段河道，如果不能则无解；
（3）在确定有解的情况下，每次遇到有效区间（该区间与已经能够覆盖的区间有交集）的时候，需要判断该区间是否能取代上一个有效区间，如果可以取代则更新能够覆盖的区间，如果不能取代则丢弃该区间：
a. 上一个有效区间是该区间的子集，即该区间虽然左边界相同，但右边界更大；
b. 该区间与上一个有效区间产生交集，移除上一个有效区间后，若该区间仍然是有效区间则循环继续移除前面的有效区间，直到该区间无效循环停止（注意此处需要还原最后一个移除的有效区间，然后添加该区间）；
（4）在遍历处理每个区间的时候，如果当前的有效区间已经能够覆盖整个河道，则需提前停止遍历。

5.2 Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
n, L = input().split()
n, L = int(n), int(L)

nums = []
for i in range(n):
    [a, b] = input().split()
    nums.append([int(a), int(b)])

# 区间按照左边界排序
nums.sort()
begin = nums[0][0]
end = nums[-1][1]
# 两边界都未覆盖，无解
if begin > 0 or end < L:
    print(-1)
else:
    left, right = nums[0]
    # 记录添加区间的右边界
    right_arr = [right]
    for num in nums[1:]:
        # 区间能够覆盖更长的宽度
        if num[0] == left and num[1] > right:
            right = num[1]
            # 原区间上扩大，只需改变记录的右边界
            right_arr[-1] = right
        else:
            # 区间有交集的情况
            if num[0] <= right < num[1]:
                if right_arr:
                    temp = right_arr[-1]
                    # 标识是否需要添加temp
                    add_flag = False
                    while right_arr and right_arr[-1] >= num[0]:
                        temp = right_arr[-1]
                        right_arr.pop()
                        add_flag = True
                    if add_flag:
                        right_arr.append(temp)
                left, right = num
                right_arr.append(right)
        # 已经覆盖到L就提前结束
        if right >= L:
            break
    print(len(right_arr))

...

...

00:00
00:00
FEATURED TAGS
牛客网试题
FRIENDS