拼多多2020实习笔试题题解

题解是交卷后做的,不保证AC。

题目1

题目描述

给出长虔都为n的两个整数数组a[n]和b[n],特殊运算 S = a[0]*b[0] + ... + a[n-1]*b[n-1],你可以改变a数组的顺序使得运算S得到的值最小,给出最终的最小值。
数组长度n大于50,对于每个元素X,0<=X<=100。

输入描述

输入一共三行。
第一行为n,表示两个数组的长度。
第二行包括n个数字,用空格隔开,是a数组的值。
第三行包括n个数字,用空格隔幵,是b数组的值。

输出描述

输出一行,包含一个数字,表示最小的S值。

示例1

输入

3
1 1 3
10 30 20

输出

80

题解

水题。先对数组a、b排序,一个升序遍历一个降序遍历。

代码:

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())), reverse=True)
res = 0
for i in range(n):
    res += a[i] * b[i]
print(res)

题目2

题目描述

小明给儿子小小明买了一套英文字母卡片(总共包合52张,区分大小写),小小明把卡片丢在地上玩耍,并从中取出若干张排成一排,形成了一个卡片序列。
此时.小明需要将卡片序列中的重复字母剔除(同一个字母的大小写只保留一个)。
请问,所有可能的结果中,字母序最小(不区分大小写)的序列的第一张卡片上是哪个字母?

输入描述

一行输入,包合一个非空字符串,表示卡片序列,长度为 N(1<=N<=52)。

输出描述

一行输出,包合一个字母(如果结果是大写字母,则需要转成小写)。

示例1

输入

xaBXY

输出

a

说明

剔除完后的结果为abxy

题解

这道题题意比较绕。大意就是,52个字母中的若干个组成的一个序列,对于每对重复字母(不区分大小写),都剔除其中一个,由于剔除的位置不同,处理后的序列有多种情况,从中找到字母序最小的,返回其首字母。

例如,xaBXY,其中x重复出现,剔除其中一个x,有两种情况:aBXY、xaBY,前者的字母序最小,所以返回其首字母a。
又如,bBa,有两种情况:Ba、ba,两者不区分大小写是一样的,首字母是b。
又如,cDadC,字母序最小的序列是adC,返回a。

理清楚题意后,解决起来就比较简单。考虑哪些字母可能成为序列的首字母。从左往右扫描,如果遇到只出现一次的字母,由于该字母不会被剔除,所以其后的字母将不会成为首字母,将该字母加入待选首字母并结束扫描;如果遇到出现两次的字母,若第一次遇到该字母,则将该字母加入待选并继续扫描,但若第二次遇到该字母,就需要停止扫描了,因为如果剔除前一个该字母,则当前位置的该字母将会被保留,所以其后的字母将不会成为首字母。

代码:

from collections import Counter

s = input().lower()
cnt = Counter(list(s))
rec = set()
heads = []
for c in s:
    if cnt[c] == 1:
        heads.append(c)
        break
    else:
        if c in rec:
            break
        else:
            heads.append(c)
            rec.add(c)
print(min(heads))

题目3

题目描述

小镇沿街分布(可以理解为都在数轴上),有n家银行(位置以数轴的坐标表示,金额表示可以被抢走的金额),两个绑匪试图分别抢劫一个银行,为了让警方多奔波他们商定选择的两个银行距离不小于d,请问符合约定的情况下他们能抢到的总金额最大是多少?

输入描述

输入包括 n+1 行。
第一行包含两个数字n和d(1<=n<=200000,1<=d<=100000000),n表示银行的数量,d表示约定的距离。
下面n行,每一行包括两个数字a, b(1<=a,b<=100000000),分别表示坐标和金额,空格分隔。

输出描述

输出一个数字,表示可以获得的最大金额。

示例1

输入

6 3
1 1
3 5
4 8
6 4
10 3
11 2

输出

11

题解

首先,需要对银行按位置排序。对于每家银行,找到其右侧符合距离限制的金额最大值。

由于每次都需要某位置及其右侧的金额最大值,不妨先计算出来,存为后缀max数组。然后,对于每家银行,找到其右侧符合距离限制且最近的银行,取其后缀max数组的值,即右侧银行可获得的最大金额,并更新可获得的最大金额。

代码:

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, d;
    cin >> n >> d;
    vector<pair<int, int> > banks(n, make_pair(0, 0));
    for (int i = 0; i < n; i++) {
        cin >> banks[i].first >> banks[i].second;
    }
    sort(banks.begin(), banks.end(), [](pair<int, int> a, pair<int, int> b) {
        return a.first < b.first;
    });
    vector<int> rmax(n, banks.back().second);
    for (int i = n - 2; i >= 0; i--) {
        rmax[i] = max(banks[i].second, rmax[i+1]);
    }
    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (banks[j].first - banks[i].first >= d) {
                res = max(res, banks[i].second + rmax[j]);
                break;
            }
        }
    }
    cout << res << endl;
    return 0;
}

题目4

题目描述

一个合法的圆括号表达式满足一下条件:
1.""空字符串被认为是合法的
2.如果字符串"X"与"Y"是合法的,则"XY"也被认为是合法的
3.如果字符串"X"是合法的,则"(X)"也是合法的
例子:"", "()", "()()", "(())"这些都是合法的
现给出两个不保证合法的由圆括号组成的字符串,你需要交错这两个圆括号序列(在组成的新字符串中,每个初始字符串都保持原来的顺序)得到一个新的合法的圆括号表达式(不同的交错方式可能会得到相同的表达式,这种情况分开计数),求共有多少结果合法的交错方式(无法得到合法的圆括号表达式则输出0),输出结果模 10^9+7 的值(^符号是乘方的意思)

输入描述

输入包括两行,分别是两个只有"(和")"组成的字符串,长度小于2500

输出描述

输出为一个数字,表示合法的交错方式数量模上10^9+7的结果

示例1

输入

(()
())

输出

19

题解

好吧,不会。。。

刷题

上一篇 N-sum问题通解
下一篇 《实战Java高并发程序设计》读书笔记

添加新评论

*
*