程序员基德

01-19 11:50 中国科学技术大学 C++ 发布于浙江

关注

【笔试题解】2024-04-13-美团春招

大家好这里是程序员基德，今天给大家带来的是美团笔试题(改编题面)的题目解析。

感兴趣的朋友可以来订阅基德的笔试专栏，感谢大家的支持。

互联网刷题必备宝典🔗

第一题：好矩阵

题目内容

小基定义一个矩阵是"好矩阵"，当且仅当该矩阵所有元素都相同。现在小基拿到了一个矩阵，她想知道该矩阵有多少个 $2 \times 2$ 的子矩阵是好矩阵？

输入描述

第一行输入两个正整数 $n$ 和 $m$ ，代表矩阵的行数和列数。接下来的 $n$ 行，每行输入 $m$ 个正整数 $a_{i,j}$ ，代表小基拿到的矩阵。 $1 \leq n,m \leq 100$ $1 \leq a_{i,j} \leq 10^9$

输出描述

$2 \times 2$ 好子矩阵的数量。

样例1

输入：

输出：

说明：只有左下角一个好子矩阵。

题解

这是一道简单的模拟题。只需要枚举每个可能的 $2 \times 2$ 子矩阵的左上角位置，然后判断这个子矩阵的四个元素是否相等即可。

时间复杂度： $O(n \times m)$ 空间复杂度： $O(1)$

三语言参考代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m - 1; j++) {
            if (g[i][j] == g[i + 1][j] && g[i + 1][j] == g[i][j + 1] && g[i][j + 1] == g[i + 1][j + 1]) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Python

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for i in range(n - 1):
    for j in range(m - 1):
        if g[i][j] == g[i + 1][j] and g[i + 1][j] == g[i][j + 1] and g[i][j + 1] == g[i + 1][j + 1]:
            ans += 1
print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] g = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = scanner.nextInt();
            }
        }
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                if (g[i][j] == g[i + 1][j] && g[i + 1][j] == g[i][j + 1] && g[i][j + 1] == g[i + 1][j + 1]) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
        scanner.close();
    }
}

第二题：最多零的数组

题目内容

小基拿到了一个数组，她可以进行最多 $k$ 次操作，每次操作任选一个元素加 1 或者减 1。小基希望最终 0 的数量尽可能多。你能帮帮她吗？

输入描述

第一行输入 2 个正整数 $n,k$ ，代表数组大小和小基的操作次数。第二行输入 $n$ 个整数 $a_i$ ，代表小基拿到的数组。 $1 \leq n \leq 10^5$ $1 \leq k \leq 10^{14}$ $-10^9 \leq a_i \leq 10^9$

输出描述

一个整数，代表最终 0 的数量的最大值。

样例1

输入：

4 5
-2 3 -2 9

输出：

说明：对第二个元素操作 3 次减 1，对第三个元素操作 2 次加 1，这样数组变成 [-2,0,0,9]。

题解

这道题的关键是贪心思想。对于每个数，将其变成 0 需要的操作次数就是其绝对值。因此，应该优先选择绝对值小的数进行操作。

时间复杂度： $O(n \log n)$ 空间复杂度： $O(n)$

三语言参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1E5 + 10;
typedef long long ll;
ll a[N], n, k;

int main() {
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] = abs(a[i]);
    }
    sort(a, a + n);
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        if(k < a[i]) break;
        k -= a[i];
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Python

n, k = map(int, input().split())
nums = list(map(int, input().split()))
nums = sorted(map(abs, nums))
count = 0
for num in nums:
    if k >= num:
        k -= num
        count += 1
    else:
        break
print(count)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong(), k = in.nextLong();
        Long[] arr = new Long[(int)n];
        for(int i = 0; i < n; i++) arr[i] = in.nextLong();
        Arrays.sort(arr, (Long a, Long b) -> Long.compare(Math.abs(a), Math.abs(b)));
        int res = 0;
        for(int i = 0; i < n; i++) {
            if(k >= Math.abs(arr[i])) {
                k -= Math.abs(arr[i]);
                res++;
            }
            else break;
        }
        System.out.println(res);
    }
}

第三题：红黑树

题目内容

小基有一棵有 $n$ 个节点的树，根节点为 1 号节点，树的每个节点是红色或者黑色，她想知道有多少节点的子树中同时包含红点和黑点。

输入描述

第一行输入一个整数 $n(1 \leq n \leq 10^5)$ 表示节点数量。第二行输入一个长度为 $n$ 的字符串 $s$ 表示节点的颜色，第 $i$ 个节点的颜色为 $s_i$ ，若 $s_i$ 为'B'表示节点的颜色为黑色，若 $s_i$ 为'R'则表示节点的颜色为红色。接下来 $n-1$ 行，每行输入两个整数 $u,v(1 \leq u,v \leq n)$ 表示树上的边。

输出描述

输出一个整数表示答案。

样例1

输入：

3
BRB
1 2
2 3

输出：

题解

这是一道树形 DFS 问题。对于每个节点，需要统计其子树中红色和黑色节点的数量。如果两种颜色的节点数量都大于 0，则这个子树满足条件。

时间复杂度： $O(n)$ 空间复杂度： $O(n)$

三语言参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1E5 + 10;
int n, res;
string s;
vector<int> g[N];

vector<int> dfs(int u, int fa) {
    vector<int> color(2, 0);
    if(s[u] == 'B') color[0]++;
    else color[1]++;
    for(int &x : g[u]) {
        if(x == fa) continue;
        auto v = dfs(x, u);
        color[0] += v[0];
        color[1] += v[1];
    }
    if(color[0] > 0 && color[1] > 0) res++;
    return color;
}

int main() {
    cin >> n >> s;
    s = " " + s;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0);
    cout << res << endl;
    return 0;
}

Python

import sys
sys.setrecursionlimit(200000)

n = int(input())
color = input()
adj = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    adj[u-1].append(v-1)

count = 0

def dfs(i):
    global count
    if len(adj[i]) == 0:
        return False
    flag = False
    for j in adj[i]:
        if dfs(j):
            flag = True
        else:
            if color[i] != color[j]:
                flag = True
    if flag:
        count += 1
    return flag

dfs(0)
print(count)

Java

import java.util.*;
import java.io.*;

class Main {
    static int n;
    static Node[] nodes;
    static int res = 0;

    static int dfs(int nodeIndex, HashMap<Integer,Integer> visited) {
        visited.put(nodeIndex, 0);
        Node node = nodes[nodeIndex];
        boolean red = node.color == 'R';
        boolean black = node.color == 'B';
        
        for(int i : node.children.keySet()) {
            if(visited.get(i) != null) continue;
            int num = dfs(i, visited);
            if(num == 0) black = true;
            else if(num == 1) red = true;
            else {
                black = true;
                red = true;
            }
        }
        
        if(red && black) {
            res++;
            return 2;
        }
        return red ? 1 : 0;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine());
        nodes = new Node[n+1];
        String s = reader.readLine();
        
        for(int i = 1; i <= n; i++) {
            nodes[i] = new Node();
            nodes[i].color = s.charAt(i-1);
        }
        
        for(int i = 1; i < n; i++) {
            String[] ss = reader.readLine().split(" ");
            int u = Integer.parseInt(ss[0]);
            int v = Integer.parseInt(ss[1]);
            nodes[u].children.put(v, 0);
            nodes[v].children.put(u, 0);
        }
        
        dfs(1, new HashMap<>());
        System.out.println(res);
    }
}

class Node {
    HashMap<Integer,Integer> children = new HashMap<>();
    char color;
}

第四题：区间乘积因子数

题目内容

小基拿到了一个数组，她有 $q$ 次查询，每次询问一个区间内所有元素的乘积有多少因子。你能帮帮她吗？

注：由于数组元素过多，所以是按连续段的方式给定。例如，[1,1,2,3,3,3]有 2 个 1，1 个 2，3 个 3，因此表示为<2,1>,<1,2>,<3,3>。

输入描述

第一行输入两个正整数 $n,m$ ，代表数组的大小，以及连续段的数量。接下来的 $m$ 行，每行输入两个正整数 $u_i,v_i$ ，代表一段区间内有 $v_i$ 个 $u_i$ 。接下来的一行输入一个正整数 $q$ ，代表询问次数。接下来的 $q$ 行，每行输入两个正整数 $l,r$ ，代表询问的是第 $l$ 个数到第 $r$ 个数的乘积的因子数量。

$1 \leq n \leq 10^{14}$ $1 \leq m,q \leq 10^5$ $1 \leq u_i \leq 10$ $1 \leq v_i \leq 10^9$ $1 \leq l,r \leq n$ 保证所有的 $v_i$ 之和恰好等于 $n$

输出描述

输出 $q$ 行，每行输出一个整数，代表最终的乘积因子数量。由于答案可能过大，请对 $10^9+7$ 取模。

样例1

输入：

输出：

2
8

题解

这是一道需要用到二分和前缀和的问题。一个数的因子数等于其每个质因子的数量加 1 的乘积。因为 10 以内只有 2,3,5,7 这 4 个质数，所以可以对这 4 个质数预处理前缀和。

时间复杂度： $O(q \log n)$ 空间复杂度： $O(m)$

三语言参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    cin.tie(0)->sync_with_stdio(false);
    LL n, m, q;
    cin >> n >> m;
    const int mod = 1e9 + 7;
    vector<int> primes = {2, 3, 5, 7};
    vector<LL> s(m + 1);
    vector<int> a(m + 1);
    vector<array<LL, 4>> pre(m + 1, {0});
    
    auto get = [&](int x) -> vector<int> {
        vector<int> cnt(4, 0);
        for (int j = 0; j < 4; ++j) {
            while(x % primes[j] == 0) {
                x /= primes[j];
                ++cnt[j];
            }
        }
        return cnt;
    };
    
    for (int i = 1; i <= m; ++i) {
        cin >> a[i] >> s[i];
        pre[i] = pre[i - 1];
        vector<int> cnt = get(a[i]);
        for (int j = 0; j < 4; ++j) {
            pre[i][j] = (pre[i][j] + cnt[j] * s[i]) % mod;
        }
        s[i] += s[i - 1];
    }
    
    cin >> q;
    while (q--) {
        LL l, r;
        cin >> l >> r;
        int L = lower_bound(s.begin(), s.end(), l) - s.begin();
        int R = lower_bound(s.begin(), s.end(), r) - s.begin();
        vector<int> cnt(4, 0);
        vector<int> cntl = get(a[L]), cntr = get(a[R]);
        LL ans = 1;
        
        for (int j = 0; j < 4; ++j) {
            if (L == R) {
                ans = ((r - l + 1) * cntl[j] % mod + 1) * ans % mod;
            } else {
                LL t = (s[L] - l + 1) % mod * cntl[j] % mod;
                if (L < R) {
                    t += (r - s[R - 1]) % mod * cntr[j] % mod;
                }
                if (L + 1 < R) {
                    t += pre[R - 1][j] - pre[L][j];
                }
                t = (t % mod + mod) % mod;
                ans = (t + 1) * ans % mod;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Python

def get_prime_factors(x):
    primes = [2, 3, 5, 7]
    cnt = [0] * 4
    for i, p in enumerate(primes):
        while x % p == 0:
            x //= p
            cnt[i] += 1
    return cnt

n, m = map(int, input().split())
MOD = 10**9 + 7

# 读取连续段
segments = []
total = 0
for _ in range(m):
    u, v = map(int, input().split())
    segments.append((u, v))
    total += v

# 预处理前缀和
prefix_sum = [0]
prime_counts = [[0] * 4]
for u, v in segments:
    prefix_sum.append(prefix_sum[-1] + v)
    cnt = get_prime_factors(u)
    new_counts = [
        (prime_counts[-1][i] + cnt[i] * v) % MOD
        for i in range(4)
    ]
    prime_counts.append(new_counts)

# 处理查询
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    left_seg = next(i for i, x in enumerate(prefix_sum) if x >= l)
    right_seg = next(i for i, x in enumerate(prefix_sum) if x >= r)
    
    result = 1
    for i in range(4):
        count = 0
        if left_seg == right_seg:
            count = (r - l + 1) * get_prime_factors(segments[left_seg-1][0])[i]
        else:
            # 左段
            count = (prefix_sum[left_seg] - l + 1) * get_prime_factors(segments[left_seg-1][0])[i]
            # 中间段
            if left_seg + 1 < right_seg:
                count += prime_counts[right_seg-1][i] - prime_counts[left_seg][i]
            # 右段
            if left_seg < right_seg:
                count += (r - prefix_sum[right_seg-1]) * get_prime_factors(segments[right_seg-1][0])[i]
        count = count % MOD
        result = result * (count + 1) % MOD
    
    print(result)

Java

import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    static int[] primes = {2, 3, 5, 7};
    
    static int[] getPrimeFactors(int x) {
        int[] cnt = new int[4];
        for (int i = 0; i < 4; i++) {
            while (x % primes[i] == 0) {
                x /= primes[i];
                cnt[i]++;
            }
        }
        return cnt;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int m = sc.nextInt();
        
        long[] prefixSum = new long[m + 1];
        int[][] primeCounts = new int[m + 1][4];
        int[] nums = new int[m + 1];
        long[] counts = new long[m + 1];
        
        for (int i = 1; i <= m; i++) {
            nums[i] = sc.nextInt();
            counts[i] = sc.nextLong();
            prefixSum[i] = prefixSum[i-1] + counts[i];
            
            int[] factors = getPrimeFactors(nums[i]);
            for (int j = 0; j < 4; j++) {
                primeCounts[i][j] = (int)((primeCounts[i-1][j] + 
                    (long)factors[j] * counts[i]) % MOD);
            }
        }
        
        int q = sc.nextInt();
        while (q-- > 0) {
            long l = sc.nextLong();
            long r = sc.nextLong();
            
            int leftSeg = 1;
            while (prefixSum[leftSeg] < l) leftSeg++;
            int rightSeg = leftSeg;
            while (rightSeg <= m && prefixSum[rightSeg] < r) rightSeg++;
            
            long result = 1;
            for (int i = 0; i < 4; i++) {
                long count = 0;
                if (leftSeg == rightSeg) {
                    count = (r - l + 1) * getPrimeFactors(nums[leftSeg])[i];
                } else {
                    count = (prefixSum[leftSeg] - l + 1) * 
                        getPrimeFactors(nums[leftSeg])[i];
                    if (leftSeg + 1 < rightSeg) {
                        count = (count + primeCounts[rightSeg-1][i] - 
                            primeCounts[leftSeg][i]) % MOD;
                    }
                    if (leftSeg < rightSeg) {
                        count = (count + (r - prefixSum[rightSeg-1]) * 
                            getPrimeFactors(nums[rightSeg])[i]) % MOD;
                    }
                }
                count = (count % MOD + MOD) % MOD;
                result = result * (count + 1) % MOD;
            }
            System.out.println(result);
        }
    }
}

第五题：子序列计数

题目内容

小基有一个数字串 $x$ ，她将 $x$ 的所有非空子序列都取了出来，将其中满足相邻数位两两不同的子序列都加入了集合 $S$ 中。她想知道集合 $S$ 的大小最终有多大。

注意：

集合中的元素具有互异性，即两两不同。
子序列可以存在前导 0，也就是说如"011"和"00011"是不同的。

输入描述

输入包含一行一个数字串 $x(0 \leq x \leq 10^{1000000})$ ，表示小基的数字 $x$ 。 ( $x$ 可能含有前导 0)

输出描述

输出包含一行一个整数，表示集合的大小。由于结果可能很大，因此你只要输出答案对 1000000007 取的结果。

样例1

输入：

输出：

题解

这是一道动态规划问题。设 $f[i][j]$ 表示前 $i$ 个字符组成的以 $j$ 为结尾的合法子序列个数。对于当前位 $j$ ，由于要去重，前面所有以 $j$ 结尾的子序列对于当前位来说同样可以构造，所以只需要考虑前一位不是以 $j$ 结尾的答案。

时间复杂度： $O(n)$ 空间复杂度： $O(1)$

三语言参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<ll>> dp(n, vector<ll>(10, 0));
    dp[0][s[0]-'0'] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            if (s[i] - '0' == j) {
                int sum = 0;
                for(int k = 0; k < 10; k++) {
                    sum = (sum + dp[i-1][k]) % mod;
                }
                dp[i][j] = (sum - dp[i-1][j] + 1 + mod) % mod;
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    ll ans = 0;
    for (int j = 0; j < 10; j++) {
        ans = (ans + dp[n-1][j]) % mod;
    }
    cout << ans;
    return 0;
}

Python

x = input()
n, mod = len(x), 10**9+7
f = [0] * 10
f[int(x[0])] = 1
for i in range(1, n):
    c = int(x[i])
    f[c] = (sum(f) - f[c] + 1) % mod
print((sum(f) + mod) % mod)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String x = scanner.nextLine();
        int n = x.length();
        int mod = 1000000007;
        
        long[] f = new long[10];
        f[Character.getNumericValue(x.charAt(0))] = 1;

        for (int i = 1; i < n; i++) {
            int c = Character.getNumericValue(x.charAt(i));
            long sumF = 0;
            for (long value : f) {
                sumF = (sumF + value) % mod;
            }
            f[c] = (sumF - f[c] + 1 + mod) % mod;
        }

        long result = 0;
        for (long value : f) {
            result = (result + value) % mod;
        }
        System.out.println((result + mod) % mod);
    }
}

#美团##美团求职进展汇总##刷题#

互联网刷题笔试宝典文章被收录于专栏

互联网刷题笔试宝典，这里涵盖了市面上大部分的笔试题合集，希望助大家春秋招一臂之力