腾讯2019.9.1后端开发笔试(超详细的解法!!!)
in 笔试 with 0 comment

腾讯2019.9.1后端开发笔试(超详细的解法!!!)

in 笔试 with 0 comment

0x01

解题思路

题目非常简单,我们知道只有奇数和偶数相加才会得到奇数,那么我们可以分别统计AB中的奇偶个数,最后的结果就是min(A奇,B偶)+min(A偶,B奇)

n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a1, a2, b1, b2 = 0, 0, 0, 0
for i in A:
    if i & 1:
        a1 += 1
    else:
        a2 += 1

for i in B:
    if i & 1:
        b1 += 1
    else:
        b2 += 1

print(min(a1, b2) + min(a2, b1))

0x02

解题思路

我们可以将$a_i*(j-1)+b_i*(n-j)$进行因式分解,得到$(a_i-b_i)*j+(b_i*n-a_i)$,此时我们不难发现最后的得分结果由$(a_i-b_i)*j$决定,也就是我们需要其越小越好,而我们知道$j$是从小到大的数,那么我们只需要将$(a_i-b_i)$按照从大到小的顺序排序,那么最后二者乘积的和一定是最小的。

n = int(input())
dif = []
for _ in range(n):
    data = list(map(int, input().split()))
    dif.append([data[0] - data[1], data[0], data[1]])

dif.sort(key=lambda x:-x[0])

res = 0
for k, v in enumerate(dif):
    res += (k+1)*v[0] + v[2]*n - v[1]
print(res)

0x03

解题思路

首先我们不难想到通过二分法解决这个问题。二分法的关键就是处理合法性问题,我们可以通过贪心的策略处理这个问题的合法性(给定时间x,最少多少人可以完成任务)。

我们知道,如果我们只有一个人的话,那么需要sum(A)+n的时间完成任务。所以我们可以遍历数组A计算前缀和cnt,如果cnt+i>=xi表示遍历到的A中元素位置),说明此时人手不够了,我们需要增加人手。当我们增加一个人手后,我们相应的消耗时间就要减少x-i(其中x表示我们的目标时间,在位置i,每个人有x-i时间搬物品)。当最后所需人手个数小于m或者人手恰好是m且前缀合cnt小于等于0的时候,说明在x时间内可行,否则不可行。

接着就是二分法的常规套路,但我们发现当前的mid可行的时候,我们的r=mid,否则l=mid+1

n, m = list(map(int,input().split()))
A = list(map(int, input().split()))
acc = sum(A)

def check(x):
    cnt, p = 0, 0
    for i in range(1, n + 1):
        cnt += A[i-1]
        if i >= x:
            return False
        while i + cnt > x:
            cnt -= x - i
            p += 1
            if p > m:
                return False
    if p == m:
        return cnt <= 0
    return True

if m > acc:
    print(n + 1)
else:
    l, r = 2, n + acc
    while l < r:
        mid = l + r >> 1
        if check(mid):
            r = mid
        else:
            l = mid + 1
    print(r)

0x04

解题思路

区间和的问题不难想到前缀和,最小值的问题不难想到单调栈,思路就非常清晰了。这个问题和Leetcode 84:柱状图中最大的矩形(超详细的解法!!!)非常类似。

我们需要维护一个严格的单调递增栈(通过这个栈我们可以得到区间的最小值,也就是栈顶元素),区间长度由栈顶和当前位置决定。具体步骤还是看Leetcode 84吧!

n = int(input())
data = list(map(int, input().split()))
data.append(0)
res = 0
s = []
pre = [0]*len(data)
for i in range(1, len(data)):
    pre[i] += pre[i-1] + data[i-1]
    
for i, v in enumerate(data):
    while s and v <= data[s[-1]]:
        t = s.pop()
        res = max(res, data[t]*(pre[i] - pre[s[-1] + 1 if s else 0]))
    s.append(i)
print(res)

0x05

解题思路

典型的动态规划问题,我们定义函数$f(i)$表示长度为$i$的时候合法方案数。那么

解释一下上面这个式子,$f(i)$的方案数只能来源于两种情况:一种是前面的白花不连续,一种是白花连续。

最后区间查询问题,显然就是通过前缀和来处理了。

#include <iostream>
using namespace std;

typedef long long LL;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
int a[MAX];
LL dp[MAX], sum[MAX];

int main()
{
    int t, k;
    scanf("%d %d", &t, &k);
    for(int i = 0; i < k; i++) dp[i] = 1;
    for(int i = k; i < MAX; i++) dp[i] = (dp[i - 1] % MOD + dp[i - k] % MOD) % MOD;
    
    sum[1] = dp[1];
    for(int i = 2; i < MAX; i++) sum[i] = (sum[i - 1] % MOD + dp[i] % MOD) % MOD;
    while (t--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%lld\n", (MOD + sum[b] - sum[a - 1]) % MOD);
    }
}

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses