程序员基德

01-17 20:03 已编辑中国科学技术大学 C++ 发布于浙江

关注

【笔试题解】2024-03-16-美团春招

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

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

T1 外卖订单

题目描述

小基是美团外卖的忠实用户，他经常去美团外卖 app 上面点外卖，因为会员红包的性价比太高。现在小基点了若干道菜，他希望你计算一个订单的总价。你能帮帮他吗？

输入描述

第一行输入一个正整数 $n$ ，代表菜品总数。

第二行输入 $n$ 个正整数 $a_i$ ，代表每道菜的价格。

第三行输入两个正整数 $x$ 和 $y$ ， $x$ 代表满减的价格， $y$ 代表红包的价格。

输出描述

一个正整数，代表小基最终应付的钱数。

样例1

输入：

4
10 20 10 20
25 10

输出：

说明：四个菜一共 60 元，满减减掉了 25 元，再用一个 10 元的红包，因此需要付 25 元。

题解

这是一道简单的模拟题，主要考察基本的数学运算。

解题思路如下：

首先读取所有菜品的价格并求和，得到总价。
从总价中减去满减金额。
再减去红包金额。
输出最终结果。

关键点：

使用 sum() 函数可以快速求出菜品总价
最终价格就是：总价 - 满减 - 红包

时间复杂度： $O(n)$ ，其中 $n$ 是菜品数量。主要时间花在读取和求和上。

参考代码

C++:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int sum = 0;
    for(int i = 0; i < n; i++) {
        int price;
        cin >> price;
        sum += price;
    }
    int x, y;
    cin >> x >> y;
    cout << sum - x - y << endl;
    return 0;
}

Python:

n = int(input())
w = list(map(int, input().split()))
x, y = map(int, input().split())
cost = sum(w)
print(cost - x - y)

Java:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += sc.nextInt();
        }
        int x = sc.nextInt();
        int y = sc.nextInt();
        System.out.println(sum - x - y);
    }
}

T2 字符串规范化

题目描述

小基定义以下三种单词是合法的：

所有字母都是小写。例如：good。
所有字母都是大写。例如：APP。
第一个字母大写，后面所有字母都是小写。例如：Alice。

现在小基拿到了一个单词，他每次操作可以修改任意一个字符的大小写。小基想知道最少操作几次可以使得单词变成合法的？

输入描述

一个仅由大写字母和小写字母组成的字符串，长度不超过 $10^5$ 。

输出描述

一个整数，代表操作的最小次数。

样例1

输入：

AbC

输出：

说明：变成 ABC 或者 Abc 均可。只需要 1 次操作。

题解

这道题需要考虑三种合法情况，分别计算达到每种情况需要的最小操作次数。

解题思路：

统计字符串中大写字母和小写字母的数量。
考虑三种合法情况：
- 全部变成小写：需要修改的次数是大写字母的数量
- 全部变成大写：需要修改的次数是小写字母的数量
- 首字母大写其余小写：需要考虑首字母是否需要修改，以及其余字母变成小写需要的修改次数
取三种情况中的最小值。

时间复杂度： $O(n)$ ，其中 $n$ 是字符串长度。

参考代码

C++:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    int upper = 0, lower = 0;
    for(char c : s) {
        if(isupper(c)) upper++;
        else lower++;
    }
    int n = s.size();
    int ans = min(upper, lower); // 全部变成一种情况
    
    // 首字母大写，其余小写
    int firstCase = (islower(s[0]) ? 1 : 0) + upper - (isupper(s[0]) ? 1 : 0);
    ans = min(ans, firstCase);
    
    cout << ans << endl;
    return 0;
}

Python:

s = input()
upper = sum(1 for c in s if c.isupper())
lower = len(s) - upper

ans = min(upper, lower)  # 全部变成一种情况
# 首字母大写，其余小写
first_case = (s[0].islower()) + upper - (s[0].isupper())
ans = min(ans, first_case)

print(ans)

Java:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int upper = 0, lower = 0;
        
        for(char c : s.toCharArray()) {
            if(Character.isUpperCase(c)) upper++;
            else lower++;
        }
        
        int n = s.length();
        int ans = Math.min(upper, lower);
        
        // 首字母大写，其余小写
        int firstCase = (Character.isLowerCase(s.charAt(0)) ? 1 : 0) + 
                       upper - (Character.isUpperCase(s.charAt(0)) ? 1 : 0);
        ans = Math.min(ans, firstCase);
        
        System.out.println(ans);
    }
}

T3 数组翻倍

题目描述

小基拿到了一个数组，他每次操作会将除了第 $x$ 个元素的其余元素翻倍，一共操作了 $q$ 次。请你帮小基计算操作结束后所有元素之和。由于答案过大，请对 $10^9+7$ 取模。

输入描述

第一行输入两个正整数 $n$ , $q$ ，代表数组的大小和操作次数。

第二行输入 $n$ 个正整数 $a_i$ ，代表数组的元素。

接下来的 $q$ 行，每行输入一个正整数 $x_i$ ，代表第 $i$ 次操作未被翻倍的元素。

数据范围：

$1 \leq n,q \leq 10^5$
$1 \leq x_i \leq n$
$1 \leq a_i \leq 10^9$

输出描述

一个整数，代表操作结束后所有元素之和模 $10^9+7$ 的值。

样例1

输入：

输出：

题解

这道题的关键是理解每个元素被翻倍的次数。

解题思路：

对于每个位置，初始翻倍次数为操作总次数 $q$ 。
当某个位置被指定为不翻倍时，该位置的翻倍次数减1。
使用快速幂计算每个位置最终的值： $a_i \times 2^{cnt_i}$ 。
所有位置的值求和并取模。

时间复杂度： $O(n \log q)$ ，其中快速幂的复杂度是 $O(\log q)$ 。

参考代码

C++:

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

long long quick_pow(long long a, long long b) {
    long long res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    
    vector<int> cnt(n, q);
    for(int i = 0; i < q; i++) {
        int x;
        cin >> x;
        cnt[x-1]--;
    }
    
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        ans = (ans + a[i] * quick_pow(2, cnt[i])) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Python:

MOD = 10**9 + 7
n, q = map(int, input().split())
a = list(map(int, input().split()))
cnt = [q] * n

for _ in range(q):
    x = int(input())
    cnt[x-1] -= 1

ans = 0
for i in range(n):
    ans = (ans + a[i] * pow(2, cnt[i], MOD)) % MOD
print(ans)

Java:

import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    
    static long quickPow(long a, long b) {
        long res = 1;
        while(b > 0) {
            if((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        
        int[] a = new int[n];
        for(int i = 0; i < n; i++) a[i] = sc.nextInt();
        
        int[] cnt = new int[n];
        Arrays.fill(cnt, q);
        
        for(int i = 0; i < q; i++) {
            int x = sc.nextInt();
            cnt[x-1]--;
        }
        
        long ans = 0;
        for(int i = 0; i < n; i++) {
            ans = (ans + a[i] * quickPow(2, cnt[i])) % MOD;
        }
        System.out.println(ans);
    }
}

T4 区间众数

题目描述

小基拿到了一个数组，他希望你求出所有区间众数之和。定义区间的众数为出现次数最多的那个数，如果有多个数出现次数最多，那么众数是其中最小的那个数。

输入描述

第一行输入一个正整数 $n$ ，代表数组的大小。

第二行输入 $n$ 个正整数 $a_i$ ，代表数组的元素。

数据范围：

$1 \leq n \leq 2 \times 10^5$
$1 \leq a_i \leq 2$

输出描述

一个正整数，代表所有区间的众数之和。

样例1

输入：

3
2 1 2

输出：

说明：

[2]，[2,1,2]，[2] 的众数是 2
[2,1]，[1]，[1,2] 的众数是 1 因此答案是 9。

题解

这道题可以使用前缀和和树状数组来解决。

解题思路：

由于数组元素只有1和2，可以将1视为-1，2视为1。
计算前缀和，区间和大于0表示2的数量多，否则1的数量多或相等。
使用树状数组维护区间统计。

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

参考代码

C++:

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

int lowbit(int x) { return x & (-x); }

void update(vector<int>& tree, int pos, int val) {
    while(pos < tree.size()) {
        tree[pos] += val;
        pos += lowbit(pos);
    }
}

int query(vector<int>& tree, int pos) {
    int sum = 0;
    while(pos > 0) {
        sum += tree[pos];
        pos -= lowbit(pos);
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    vector<int> tree(n+1);
    
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = (a[i] == 2 ? 1 : -1);
    }
    
    long long ans = 0;
    int sum = 0;
    update(tree, n/2, 1);  // 初始化
    
    for(int i = 1; i <= n; i++) {
        sum += a[i];
        ans += query(tree, sum + n/2);
        update(tree, sum + n/2 + 1, 1);
    }
    
    cout << ans << endl;
    return 0;
}

Python:

def lowbit(x):
    return x & (-x)

def update(tree, pos, val):
    while pos < len(tree):
        tree[pos] += val
        pos += lowbit(pos)

def query(tree, pos):
    sum = 0
    while pos > 0:
        sum += tree[pos]
        pos -= lowbit(pos)
    return sum

n = int(input())
a = [0] + list(map(lambda x: 1 if x == 2 else -1, map(int, input().split())))
tree = [0] * (n+1)

ans = 0
sum = 0
update(tree, n//2, 1)

for i in range(1, n+1):
    sum += a[i]
    ans += query(tree, sum + n//2)
    update(tree, sum + n//2 + 1, 1)

print(ans)

Java:

import java.util.*;

public class Main {
    static int lowbit(int x) {
        return x & (-x);
    }
    
    static void update(int[] tree, int pos, int val) {
        while(pos < tree.length) {
            tree[pos] += val;
            pos += lowbit(pos);
        }
    }
    
    static int query(int[] tree, int pos) {
        int sum = 0;
        while(pos > 0) {
            sum += tree[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        int[] tree = new int[n+1];
        
        for(int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            a[i] = (a[i] == 2 ? 1 : -1);
        }
        
        long ans = 0;
        int sum = 0;
        update(tree, n/2, 1);
        
        for(int i = 1; i <= n; i++) {
            sum += a[i];
            ans += query(tree, sum + n/2);
            update(tree, sum + n/2 + 1, 1);
        }
        
        System.out.println(ans);
    }
}

T5 排列取反

题目描述

小基拿到了一个排列，他定义 $f(i)$ 为：将第 $i$ 个元素取反后，形成的数组的逆序对数量。小基希望你求出 $f(1)$ 到 $f(n)$ 的值。排列是指一个长度为 $n$ 的数组，1 到 $n$ 每个元素恰好出现了一次。

输入描述

第一行输入一个正整数 $n$ ，代表排列的大小。

第二行输入 $n$ 个正整数 $a_i$ ，代表排列的元素。

数据范围：

$1 \leq n \leq 2 \times 10^5$
$1 \leq a_i \leq n$

输出描述

输出 $n$ 个整数，第 $i$ 个整数是 $f(i)$ 的值。

样例1

输入：

3
1 2 3

输出：

0 1 2

说明：

第一个元素取反，数组变成 [-1,2,3]，逆序对数量为 0
第二个元素取反，数组变成 [1,-2,3]，逆序对数量为 1
第三个元素取反，数组变成 [1,2,-3]，逆序对数量为 2

题解

这道题可以使用树状数组来维护逆序对的数量。

解题思路：

首先计算原数组的逆序对数量。
对于每个位置 i：
- 将该位置的数取反后，会与左边所有数形成新的逆序对
- 同时会与右边的某些数消除原有的逆序对
使用树状数组维护区间统计。

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

参考代码

Python:

def lowbit(x):
    return x & -x

def query(tree, pos):
    res = 0
    while pos > 0:
        res += tree[pos]
        pos -= lowbit(pos)
    return res

def update(tree, pos, val):
    while pos < len(tree):
        tree[pos] += val
        pos += lowbit(pos)

n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] * (n+1)
tr1 = [0] * (n+1)
tr2 = [0] * (n+1)

# 计算原始逆序对
ans = 0
for i in range(1, n+1):
    val = query(tr1, n) - query(tr1, a[i])
    ans += val
    b[i] += val
    update(tr1, a[i], 1)

# 计算取反后的影响
for i in range(n, 0, -1):
    b[i] += query(tr2, a[i])
    update(tr2, a[i], 1)

# 输出结果
for i in range(1, n+1):
    print(ans - b[i] + i - 1, end=" ")

C++:

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

int lowbit(int x) { return x & (-x); }

void update(vector<int>& tree, int pos, int val) {
    while(pos < tree.size()) {
        tree[pos] += val;
        pos += lowbit(pos);
    }
}

int query(vector<int>& tree, int pos) {
    int sum = 0;
    while(pos > 0) {
        sum += tree[pos];
        pos -= lowbit(pos);
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1);
    vector<int> tr1(n+1), tr2(n+1);
    
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        int val = query(tr1, n) - query(tr1, a[i]);
        ans += val;
        b[i] += val;
        update(tr1, a[i], 1);
    }
    
    for(int i = n; i > 0; i--) {
        b[i] += query(tr2, a[i]);
        update(tr2, a[i], 1);
    }
    
    for(int i = 1; i <= n; i++) {
        cout << ans - b[i] + i - 1 << " ";
    }
    cout << endl;
    return 0;
}

Java:

import java.util.*;

public class Main {
    static int lowbit(int x) {
        return x & (-x);
    }
    
    static void update(int[] tree, int pos, int val) {
        while(pos < tree.length) {
            tree[pos] += val;
            pos += lowbit(pos);
        }
    }
    
    static int query(int[] tree, int pos) {
        int sum = 0;
        while(pos > 0) {
            sum += tree[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        int[] b = new int[n+1];
        int[] tr1 = new int[n+1];
        int[] tr2 = new int[n+1];
        
        for(int i = 1; i <= n; i++) a[i] = sc.nextInt();
        
        long ans = 0;
        for(int i = 1; i <= n; i++) {
            int val = query(tr1, n) - query(tr1, a[i]);
            ans += val;
            b[i] += val;
            update(tr1, a[i], 1);
        }
        
        for(int i = n; i > 0; i--) {
            b[i] += query(tr2, a[i]);
            update(tr2, a[i], 1);
        }
        
        for(int i = 1; i <= n; i++) {
            System.out.print((ans - b[i] + i - 1) + " ");
        }
        System.out.println();
    }
}

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

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

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