牛客2018年校招真题

发表于   |   更新于 | 分类于 | 评论数： | 阅读次数：
本文字数： 9.6k | 阅读时长 ≈ 9 分钟

拼多多-最大乘积

题目描述

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
输入描述:
无序整数数组A[n]
输出描述:
满足条件的最大乘积

示例1
输入
3 4 1 2
输出
24

解法一: 记录三个最大值, 两个最小值

最终的结果只可能是三个最大值的乘积, 或者是两个最小值(负负得正)和一个最最大值的乘积

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
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <climits>

int main() {

    int n;
    std::cin >> n;
    std::vector<long long> vec(n);
    for (int i = 0; i < n; i++) {
        std::cin >> vec[i];
    }
    if (vec.size() < 3) return 0;
    std::priority_queue<long long, std::vector<long long>, std::greater<long long>> min_heap;
    std::priority_queue<long long> max_heap;

    for (auto v : vec) {
        if (min_heap.size() < 3 or v > min_heap.top()) {
            if (min_heap.size() == 3)
                min_heap.pop();
            min_heap.push(v);
        }
        if (max_heap.size() < 2 or v < max_heap.top()) {
            if (max_heap.size() == 2)
                max_heap.pop();
            max_heap.push(v);
        }
    }

    long long max_digits[3];
    for(int i = 0; i < 3; i++) {
        max_digits[i] = min_heap.top();
        min_heap.pop();
    }
    long long res1 = max_digits[0] * max_digits[1] * max_digits[2];
    long long min_digits[2];
    for(int i = 0; i < 2; i++) {
        min_digits[i] = max_heap.top();
        max_heap.pop();
    }
    long long res2 = min_digits[0] * min_digits[1] * max_digits[2];
    std::cout << std::max(res1, res2) << std::endl;
    return 0;
}

拼多多-大整数相乘

题目描述

大数乘法, 给定任意位数的两个大数, 写出计算结果(以字符串形式).

常用的解法有三种: 模拟计算的普通大数乘法, 分治算法, FFT算法

普通大数乘法: 空间复杂度低, 时间复杂度为 $O(nm)$
分治算法: 时间复杂度为 $O(N^{log_2 3}) = O(N^{1.58})$
FFT算法(快速傅里叶变换): 较复杂, 一般不会作为考察点

解法一: 模拟乘法

时间复杂度: $O(mn)$, $m, n$ 分别为两个大整数的长度

先实现大整数乘以单个数的乘法, 再实现两个大整数的加法

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
import sys

str_num1, str_num2 = sys.stdin.readline().split()

len1 = len(str_num1)
len2 = len(str_num2)

def multiply(str_num1, c):
    str_num1 = list(str_num1)
    len1 = len(str_num1)
    carry = 0
    res = 0
    for i, n in enumerate(str_num1[::-1]):
        i = len1 - 1 - i
        tmp = int(n) * int(c) + carry
        carry = tmp // 10
        str_num1[i] = str(tmp % 10)
    return ''.join(str_num1) if carry == 0 else str(carry) + ''.join(str_num1)

def big_add(str1, str2):
    if (len(str1) < len(str2)):
        str1, str2 = str2, str1
    len1 = len(str1)
    len2 = len(str2)
    str1 = list(str1)
    carry = 0
    for i, c in enumerate(str1[::-1]):
        j = len2 - 1 - i
        i = len1 - 1 - i
        if (j >= 0):
            tmp = int(str1[i]) + int(str2[j]) + carry
            str1[i] = str(tmp % 10)
            carry = tmp // 10
        elif carry != 0:
            tmp = int(str1[i]) + carry
            str1[i] = str(tmp % 10)
            carry = tmp // 10
        else:
            break;
    return ''.join(str1) if carry == 0 else str(carry) + ''.join(str1)

res = '0'
suffix = ''

for i, n in enumerate(str_num2[::-1]):
    tmp = multiply(str_num1, n)
    tmp += suffix
    suffix += '0'
    res = big_add(res, tmp)

print(res)

解法二: 模拟乘法

时间复杂度与解法一相同, 只不过这里是直接先申请了一定长度的结果列表res, 然后根据乘法的规则从后往前填写每一位的值, 注意进位的存储和使用.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys

str_num1, str_num2 = sys.stdin.readline().split()
len1 = len(str_num1)
len2 = len(str_num2)
res = ['0'] * (len1 + len2)
for i, n1 in enumerate(str_num1[::-1]):
    for j, n2 in enumerate(str_num2[::-1]):
        index = (len1 + len2) - 1 - j - i
        tmp = int(n1) * int(n2) + int(res[index])
        res[index] = str(tmp % 10)
        res[index-1] = str(int(res[index-1]) + tmp // 10)
        #这里注意之前不能直接等于, 因为上一次得到的进位还没有加到结果中
print(''.join(res)) if res[0] != '0' else print(''.join(res[1:]))

分治法

https://blog.csdn.net/jeffleo/article/details/53446095

Nowcoder2018%2Fbig_num.png

对于任意位数的两个数相乘 $a \times b$, 可以写成 ($n_1, n_2$ 分别为两个乘数的位数):

于是就有:

通过 递归 的方法不断分解上面的乘法, 最终可以不断降低问题的规模, 时间复杂度可以降为 $O(N^{log_2 3}) = O(N^{1.58})$

通常, 我们选择两个数中有一个数的位数为 1 时结束递归, 代码实现如下:

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
import sys

str_num1, str_num2 = sys.stdin.readline().split()

# 自己实现的普通加法
def str_add(str_num1, str_num2):
    len1 = len(str_num1)
    len2 = len(str_num2)
    res = ['0'] * max(len1 + 1, len2 + 1)
    for i in range(len(res)):
        i1 = len1 - 1 - i
        i2 = len2 - 1 - i
        i = len(res) - 1 - i
        num1 = 0 if i1 < 0 else int(str_num1[i1])
        num2 = 0 if i2 < 0 else int(str_num2[i2])
        tmp = int(res[i]) + num1 + num2
        res[i] = str(tmp % 10)
        if i > 0: res[i-1] = str(tmp // 10)
    return ''.join(res) if res[0] != '0' else ''.join(res[1:])

# 分治
def dc_multiply(str_num1, str_num2, str_zero): # dc: divide and conquer
    len1 = len(str_num1)
    len2 = len(str_num2)
    if (len1 == 1 or len2 == 1): # 当某个为1时, 直接乘法, 实际上也可以定为当某个数位数为8时就执行
        val = int(str_num1) * int(str_num2)
        return str(val) + str_zero

    str_num1_front = str_num1[ : len1//2]
    str_num1_back = str_num1[len1//2 : ]

    str_num2_front = str_num2[ : len2//2]
    str_num2_back = str_num2[len2//2 : ]

    # 分别计算四个分段的乘法, 注意不要忘了记录各个位数的 0 的个数
    tmp1 = dc_multiply(str_num1_front, str_num2_front,
                       '0' * (len(str_zero) + len1 - len1//2 + len2 - len2//2))
    tmp2 = dc_multiply(str_num1_front, str_num2_back,
                       '0' * (len(str_zero) + len1 - len1//2))
    tmp3 = dc_multiply(str_num1_back, str_num2_front,
                       '0' * (len(str_zero) + len2 - len2//2))
    tmp4 = dc_multiply(str_num1_back, str_num2_back,
                       '0' * len(str_zero))

    # 将四个加起来
    res = str_add(tmp1,
                 str_add(tmp2,
                        str_add(tmp3, tmp4)))
    return res

print(dc_multiply(str_num1, str_num2, ''))

上面的写法是当某个数的位数为 1 时, 使用内置乘法进行计算, 但是实际上, 会存在一个数的位数为 1, 另一个数为大整数的情况, 此时, 就必须使用自实现的大整数乘法来计算, 如下所示

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
import sys

str_num1, str_num2 = sys.stdin.readline().split()

# 自己实现的普通乘法
def str_multiply(str_num1, str_num2, str_zero):
    len1 = len(str_num1)
    len2 = len(str_num2)
    res = ['0'] * (len1 + len2)
    for i, n1 in enumerate(str_num1[::-1]):
        for j, n2 in enumerate(str_num2[::-1]):
            index = (len1 + len2) - 1 - j - i
            tmp = int(n1) * int(n2) + int(res[index])
            res[index] = str(tmp % 10)
            if index > 0: res[index-1] = str(int(res[index-1]) + tmp // 10)
            #这里注意之前不能直接等于, 因为上一次得到的进位还没有加到结果中
    res.append(str_zero)
    return ''.join(res) if res[0] != '0' else ''.join(res[1:])

# 自己实现的普通加法
def str_add(str_num1, str_num2):
    len1 = len(str_num1)
    len2 = len(str_num2)
    res = ['0'] * max(len1 + 1, len2 + 1)
    for i in range(len(res)):
        i1 = len1 - 1 - i
        i2 = len2 - 1 - i
        i = len(res) - 1 - i
        num1 = 0 if i1 < 0 else int(str_num1[i1])
        num2 = 0 if i2 < 0 else int(str_num2[i2])
        tmp = int(res[i]) + num1 + num2
        res[i] = str(tmp % 10)
        if i > 0: res[i-1] = str(tmp // 10)
    return ''.join(res) if res[0] != '0' else ''.join(res[1:])

# 分治
def dc_multiply(str_num1, str_num2, str_zero): # dc: divide and conquer
    len1 = len(str_num1)
    len2 = len(str_num2)
    if (len1 == 1 or len2 == 1): # 当某个为1时, 直接乘法, 实际上也可以定为当某个数位数为8时就执行
        return str_multiply(str_num1, str_num2, str_zero)

    str_num1_front = str_num1[ : len1//2]
    str_num1_back = str_num1[len1//2 : ]

    str_num2_front = str_num2[ : len2//2]
    str_num2_back = str_num2[len2//2 : ]

    # 分别计算四个分段的乘法, 注意不要忘了记录各个位数的 0 的个数
    tmp1 = dc_multiply(str_num1_front, str_num2_front,
                       '0' * (len(str_zero) + len1 - len1//2 + len2 - len2//2))
    tmp2 = dc_multiply(str_num1_front, str_num2_back,
                       '0' * (len(str_zero) + len1 - len1//2))
    tmp3 = dc_multiply(str_num1_back, str_num2_front,
                       '0' * (len(str_zero) + len2 - len2//2))
    tmp4 = dc_multiply(str_num1_back, str_num2_back,
                       '0' * len(str_zero))

    # 将四个加起来
    res = str_add(tmp1,
                 str_add(tmp2,
                        str_add(tmp3, tmp4)))
    return res

print(dc_multiply(str_num1, str_num2, ''))

拼多多-六一儿童节

题目描述

六一儿童节，老师带了很多好吃的巧克力到幼儿园。每块巧克力j的重量为w[j]，对于每个小朋友i，当他分到的巧克力大小达到h[i] (即w[j]>=h[i])，他才会上去表演节目。老师的目标是将巧克力分发给孩子们，使得最多的小孩上台表演。可以保证每个w[i]> 0且不能将多块巧克力分给一个孩子或将一块分给多个孩子。
输入描述:
第一行：n，表示h数组元素个数
第二行：n个h数组元素
第三行：m，表示w数组元素个数
第四行：m个w数组元素
输出描述:
上台表演学生人数

解法一: 排序

时间复杂度: $O(mn)$
空间复杂度:$$ $O(1)$

先将两个数组排序, 然后对于每块巧克力, 找到恰好能满足的小孩, count+1, 并将该小孩清除出队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys

n = sys.stdin.readline().split()
h = [int(x) for x in sys.stdin.readline().split()]
m = sys.stdin.readline().split()
w = [int(x) for x in sys.stdin.readline().split()]

h.sort()
w.sort()

count = 0
for i, wi in enumerate(w):
    for j, hj in enumerate(h):
        if wi >= hj:
            h.pop(j)
            count += 1
            break

print(count)

拼多多-迷宫寻路

题目描述

题目链接

题目描述
假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙
输入描述:
迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N
后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。
输出描述:
路径的长度，是一个整数

解法