【美团笔试题汇总】2023-09-02-美团春秋招笔试题-三语言题解(CPP/Python/Java)

🍭 大家好这里是KK爱Coding ,一枚热爱算法的程序员

✨ 本系列打算持续跟新美团近期的春秋招笔试题汇总~

💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总,如果有需要的小伙伴可以关注后私信一下 KK领取,会在飞书进行同步的跟新。

**

💻听说明天上午要笔美团啦,这里给大家带来一些去年秋招的题目来练练手。

🎉 祝大家明天超常发挥,笔试AK,rp ++++++

**

文章目录

    • 💻听说明天上午要笔美团啦,这里给大家带来一些去年秋招的题目来练练手。
    • 🎉 祝大家明天超常发挥,笔试AK,rp `++++++`
    • 01.LYA的魔法药水
      • 问题描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 数据范围
      • 题解
      • 参考代码
    • 02.K 小姐的魔法书
      • 问题描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 数据范围
      • 题解
      • 参考代码
    • 03.K小姐的蛋糕店
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 样例解释
      • 数据范围
      • 题解
      • 参考代码
    • 04.LYA的魔法卡牌
      • 问题描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 数据范围
      • 题解
      • 参考代码
    • 05.K 小姐的珠宝搭配
      • 问题描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 数据范围
      • 题解
      • 参考代码
    • 写在最后
    • 📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总,如果有需要的小伙伴可以关注后私信一下 KK领取,会在飞书进行同步的跟新。

01.LYA的魔法药水

问题描述

LYA是一位魔法学徒,她正在学习制作魔法药水。一个合格的魔法药水需要满足以下两个条件:

  1. 药水中的材料必须按照一定的顺序排列,材料的魔力值需要严格递增。即对于相邻的两种材料,后一种材料的魔力值必须大于前一种。

  2. 相邻两种材料的魔力值之差也需要严格递增。即对于排序后的任意三种连续的材料,第三种与第二种材料魔力值之差必须大于第二种与第一种材料魔力值之差。

现在LYA准备了一组材料,她想知道这组材料是否可以制作出合格的魔法药水。你能帮助她吗?

输入格式

第一行包含一个正整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \leq n \leq 10^5) n(1n105),表示材料的数量。

第二行包含 n n n 个正整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 1 0 9 ) a_1, a_2, \ldots, a_n(1 \leq a_i \leq 10^9) a1,a2,,an(1ai109),表示每种材料的魔力值。

输出格式

如果这组材料可以制作合格的魔法药水,输出 "Yes",否则输出 "No"

样例输入

5
1 3 7 13 21

样例输出

Yes

数据范围

  • 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105
  • 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1ai109

题解

本题可以通过遍历材料的魔力值数组,同时维护相邻两个材料的魔力值之差来判断是否满足题目要求。

具体步骤如下:

  1. 遍历材料魔力值数组,检查是否满足严格递增,如果不满足直接输出 "No"

  2. 在遍历的过程中,计算相邻两个材料的魔力值之差,并用一个数组 b b b 存储。

  3. 遍历数组 b b b,检查是否满足严格递增,如果不满足直接输出 "No"

  4. 如果遍历完成后没有出现不满足条件的情况,输出 "Yes"

时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n)

参考代码

  • Python
n = int(input())
a = list(map(int, input().split()))

b = [0] * (n - 1)
for i in range(1, n):
    if a[i] <= a[i - 1]:
        print("No")
        exit()
    b[i - 1] = a[i] - a[i - 1]

for i in range(1, n - 1):
    if b[i] <= b[i - 1]:
        print("No")
        exit()
        
print("Yes")
  • 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[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int[] b = new int[n - 1];
        for (int i = 1; i < n; i++) {
            if (a[i] <= a[i - 1]) {
                System.out.println("No");
                return;
            }
            b[i - 1] = a[i] - a[i - 1];
        }
        
        for (int i = 1; i < n - 1; i++) {
            if (b[i] <= b[i - 1]) {
                System.out.println("No");
                return;
            }
        }
        
        System.out.println("Yes");
    }
}
  • Cpp
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<int> b(n - 1);
    for (int i = 1; i < n; i++) {
        if (a[i] <= a[i - 1]) {
            cout << "No" << endl;
            return 0;
        }
        b[i - 1] = a[i] - a[i - 1];
    }
    
    for (int i = 1; i < n - 1; i++) {
        if (b[i] <= b[i - 1]) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    
    return 0;
}

02.K 小姐的魔法书

问题描述

K 小姐是一位热爱收藏古籍的魔法师。她拥有 n n n 本魔法书,每本书都有 m m m 页。

这些魔法书中蕴藏着强大的魔力,每一页都记载着神秘的魔法符号。K 小姐相信,如果从每本书中选取一个符号,并按照从上到下的顺序将它们组合成一个新的咒语,就能够释放出非凡的魔力。

现在,K 小姐想知道能否从这些符号中找到一个 "lyasuki" 的咒语。

输入格式

第一行包含两个整数 n n n m m m ( 1 ≤ n , m ≤ 1000 ) (1 \leq n, m \leq 1000) (1n,m1000),分别表示魔法书的数量和每本书的页数。

接下来 n n n 行,每行一个长度为 m m m 的字符串,表示从上到下每本魔法书的符号。

输出格式

如果能够找到 "lyasuki" 的咒语,则输出 "Yes",否则输出 "No"

样例输入

7 4
lkjh
yqrs
airt
yszx
uvmw
noky
abki

样例输出

Yes

数据范围

  • 1 ≤ n , m ≤ 1000 1 \leq n, m \leq 1000 1n,m1000

题解

本题可以使用贪心的思想来解决。我们可以按照 "lyasuki" 中字符的顺序,从上到下遍历每一本魔法书,看是否能找到对应的字符。

具体做法如下:

  1. "lyasuki" 转换为字符数组 index
  2. 从上到下遍历每本魔法书,用指针 l 表示当前需要匹配的字符在 index 中的位置,用指针 r 表示当前遍历到的魔法书的编号。
  3. 如果当前魔法书包含 index[l] 字符,则 lr 都向后移动一位。
  4. 如果当前魔法书不包含 index[l] 字符,则只将 r 向后移动一位。
  5. 重复步骤 3 和 4,直到 l 到达 index 的末尾或 r 到达最后一本魔法书。
  6. 如果 l 到达了 index 的末尾,说明找到了 "lyasuki" 咒语,输出 "Yes",否则输出 "No"

时间复杂度 O ( n m ) O(nm) O(nm),空间复杂度 O ( n ) O(n) O(n)

参考代码

  • Python
n, m = map(int, input().split())
index = list("lyasuki")
books = [input() for _ in range(n)]

l = r = 0
while l < len(index) and r < n:
    if index[l] in books[r]:
        l += 1
    r += 1

print("Yes" if l == len(index) else "No")
  • Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        char[] idx = "lyasuki".toCharArray();
        sc.nextLine();
        String[] books = new String[n];
        for (int i = 0; i < n; i++) {
            books[i] = sc.nextLine();
        }
        
        int l = 0, r = 0;
        while (l < idx.length && r < n) {
            if (books[r].indexOf(idx[l]) != -1) {
                l++;
            }
            r++;
        }
        
        System.out.println(l == idx.length ? "Yes" : "No");
    }
}
  • Cpp
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    string idx = "lyasuki";
    string books[1005];
    for (int i = 0; i < n; i++) {
        cin >> books[i];
    }
    
    int l = 0, r = 0;
    while (l < idx.size() && r < n) {
        if (books[r].find(idx[l]) != string::npos) {
            l++;
        }
        r++;
    }
    
    cout << (l == idx.size() ? "Yes" : "No") << endl;
    return 0;
}

03.K小姐的蛋糕店

题目描述

K小姐开了一家蛋糕店,店里有 n n n 种不同口味的蛋糕。每种蛋糕都有一个美味度,第 i i i 种蛋糕的美味度为 a i a_i ai

K小姐想要通过一些操作,使得第一种蛋糕的美味度 a 1 a_1 a1 成为所有蛋糕中最高的。她可以进行以下两种操作:

  1. a 1 a_1 a1 的美味度乘以 2 2 2
  2. 选择一种蛋糕 i ( 2 ≤ i ≤ n ) i(2\leq i \leq n) i(2in),将其美味度 a i a_i ai 变成 ⌊ a i 2 ⌋ \lfloor\frac{a_i}{2}\rfloor 2ai

现在K小姐想知道,最少需要多少次操作,才能使得第一种蛋糕的美味度成为最高。

输入格式

第一行输入一个正整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1\leq n\leq 10^5) n(1n105),表示蛋糕的种类数。

第二行输入 n n n 个正整数,第 i i i 个数为 a i ( 1 ≤ a i ≤ 1 0 9 ) a_i(1\leq a_i\leq 10^9) ai(1ai109),表示第 i i i 种蛋糕的美味度。

输出格式

输出一个整数,表示最少需要的操作次数。

样例输入

6
1 1 4 4 1 4

样例输出

2

样例解释

将第一种蛋糕的美味度连续乘 2 2 2 两次,就可以使其美味度达到 4 4 4,成为所有蛋糕中最高的。

数据范围

  • 1 ≤ n ≤ 1 0 5 1\leq n\leq 10^5 1n105
  • 1 ≤ a i ≤ 1 0 9 1\leq a_i\leq 10^9 1ai109

题解

本题可以用贪心的思想来解决。首先统计出有多少种蛋糕的美味度高于第一种蛋糕,记为 c n t cnt cnt。然后进行如下操作:

  • 如果 c n t ≥ 2 cnt\geq 2 cnt2,就将第一种蛋糕的美味度乘以 2 2 2,同时更新 c n t cnt cnt 的值。
  • 如果 c n t = 1 cnt=1 cnt=1,就将唯一比第一种蛋糕美味度高的那种蛋糕的美味度除以 2 2 2,同时更新 c n t cnt cnt 的值。

重复上述操作,直到 c n t = 0 cnt=0 cnt=0,此时第一种蛋糕的美味度就成为了最高。

总操作次数即为最少需要的操作次数。

时间复杂度为 O ( n log ⁡ M ) O(n\log M) O(nlogM),其中 M = max ⁡ { a i } M=\max\{a_i\} M=max{ai}。空间复杂度为 O ( n ) O(n) O(n)

参考代码

  • Python
n = int(input())
a = list(map(int, input().split()))

a1 = a[0]
cnt = sum(ai > a1 for ai in a[1:])
ops = 0

while cnt > 0:
    if cnt >= 2:
        a1 *= 2
        cnt = sum(ai > a1 for ai in a[1:]) 
    else:
        for i in range(1, n):
            if a[i] > a1:
                a[i] //= 2
                if a[i] <= a1:
                    cnt -= 1
                break
    ops += 1

print(ops)
  • 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[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int a1 = a[0];
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            if (a[i] > a1) {
                cnt++;
            }
        }
        
        int ops = 0;
        while (cnt > 0) {
            if (cnt >= 2) {
                a1 *= 2;
                cnt = 0;
                for (int i = 1; i < n; i++) {
                    if (a[i] > a1) {
                        cnt++;
                    }
                }
            } else {
                for (int i = 1; i < n; i++) {
                    if (a[i] > a1) {
                        a[i] /= 2;
                        if (a[i] <= a1) {
                            cnt--;
                        }
                        break;
                    }
                }
            }
            ops++;
        }
        
        System.out.println(ops);
    }
}
  • Cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int a1 = a[0];
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > a1) {
            cnt++;
        }
    }

    int ops = 0;
    while (cnt > 0) {
        if (cnt >= 2) {
            a1 *= 2;
            cnt = 0;
            for (int i = 1; i < n; i++) {
                if (a[i] > a1) {
                    cnt++;
                }
            }
        } else {
            for (int i = 1; i < n; i++) {
                if (a[i] > a1) {
                    a[i] /= 2;
                    if (a[i] <= a1) {
                        cnt--;
                    }
                    break;
                }
            }
        }
        ops++;
    }

    cout << ops << endl;
    
    return 0;
}

04.LYA的魔法卡牌

问题描述

LYA是一名魔法学徒,她有一套由 n n n 张卡牌组成的魔法卡牌。每张卡牌上都有一个魔力值 a i ( 1 ≤ a i ≤ 1 0 9 ) a_i(1 \leq a_i \leq 10^9) ai(1ai109)

现在,LYA需要从这套卡牌中移除恰好 k k k 张卡牌,使得剩下的卡牌满足以下条件:对于任意两张卡牌,它们的魔力值要么互为倍数,要么其中一张卡牌的魔力值是另一张的倍数。特别地,如果移除后卡牌数量为 1 1 1 0 0 0,也视为满足条件。

LYA想知道,一共有多少种不同的移除方案呢?

输入格式

第一行包含两个整数 n n n k ( 1 ≤ k ≤ n ≤ 1 0 3 ) k(1 \leq k \leq n \leq 10^3) k(1kn103),分别表示初始卡牌数量和需要移除的卡牌数量。

第二行包含 n n n 个整数,第 i i i 个整数表示第 i i i 张卡牌的魔力值 a i ( 1 ≤ a i ≤ 1 0 9 ) a_i(1 \leq a_i \leq 10^9) ai(1ai109)

数据保证初始卡牌的魔力值两两不同。

输出格式

输出一个整数,表示不同的移除方案数。

样例输入

3 1
1 2 4

样例输出

3

数据范围

  • 1 ≤ k ≤ n ≤ 1 0 3 1 \leq k \leq n \leq 10^3 1kn103
  • 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1ai109
  • 初始卡牌的魔力值两两不同

题解

本题可以使用动态规划求解。令 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示考虑前 i i i 张卡牌,保留 j j j 张卡牌的方案数。

首先,我们对卡牌按照魔力值从小到大排序。然后,我们可以得到以下状态转移方程:

  • 对于第一张卡牌,只有一种方案,即 d p [ 1 ] [ 1 ] = 1 dp[1][1] = 1 dp[1][1]=1
  • 对于第 i i i 张卡牌,如果我们不保留它,则方案数等于不考虑第 i i i 张卡牌时的方案数,即 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i-1][j] dp[i][j]=dp[i1][j]
  • 如果我们保留第 i i i 张卡牌,则需要枚举第 i i i 张卡牌之前的所有卡牌,如果它们的魔力值是第 i i i 张卡牌魔力值的因数,则可以转移状态,即 d p [ i ] [ j ] + = d p [ k ] [ j − 1 ] dp[i][j] += dp[k][j-1] dp[i][j]+=dp[k][j1],其中 a [ i ] a[i] a[i] a [ k ] a[k] a[k] 的倍数。

最后,我们将所有 d p [ i ] [ n − k ] dp[i][n-k] dp[i][nk] 的值求和即可得到答案。

时间复杂度为 O ( n 3 ) O(n^3) O(n3),空间复杂度为 O ( n 2 ) O(n^2) O(n2)

参考代码

  • Python
n, k = map(int, input().split())
a = list(map(int, input().split()))

if n == k:
    print(1)
    exit()

a.sort()
m = n - k 
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    dp[i][1] = 1

for i in range(1, n + 1):
    for j in range(1, i):
        if a[i - 1] % a[j - 1] == 0:
            for l in range(1, min(m, i) + 1):
                dp[i][l] += dp[j][l - 1]

ans = 0
for i in range(1, n + 1):
    ans += dp[i][m]

print(ans)
  • Java
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        if (n == k) {
            System.out.println(1);
            return;
        }

        Arrays.sort(a);
        int m = n - k;
        long[][] dp = new long[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            dp[i][1] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (a[i - 1] % a[j - 1] == 0) {
                    for (int l = 1; l <= Math.min(m, i); l++) {
                        dp[i][l] += dp[j][l - 1];
                    }
                }
            }
        }

        long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dp[i][m];
        }

        System.out.println(ans);
    }
}
  • Cpp
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (n == k) {
        cout << 1 << endl;
        return 0;
    }

    sort(a.begin(), a.end());
    int m = n - k;
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));

    for (int i = 1; i <= n; i++) {
        dp[i][1] = 1;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[i - 1] % a[j - 1] == 0) {
                for (int l = 1; l <= min(m, i); l++) {
                    dp[i][l] += dp[j][l - 1];
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dp[i][m];
    }

    cout << ans << endl;

    return 0;
}

05.K 小姐的珠宝搭配

问题描述

K 小姐是一位珠宝设计师,她有 n n n 颗宝石。现在,她想把这些宝石两两配对,设计出独特的珠宝首饰。

为了让珠宝更加美观,K 小姐规定,在每一对宝石 ( a , b ) (a,b) (a,b) 中,第一颗宝石的大小 a a a 必须小于等于第二颗宝石的大小 b b b

现在,K 小姐想知道,在满足上述条件的情况下,她最多能设计出多少种不同的宝石搭配方案。

注意, ( a , b ) (a,b) (a,b) ( b , a ) (b,a) (b,a) 被视为同一种搭配方案。

输入格式

第一行包含一个整数 n n n ( 1 ≤ n ≤ 1 0 5 ) (1 \leq n \leq 10^5) (1n105),表示宝石的数量。

第二行包含 n n n 个整数,第 i i i 个整数 a i a_i ai ( 1 ≤ a i ≤ 1 0 9 ) (1 \leq a_i \leq 10^9) (1ai109) 表示第 i i i 颗宝石的大小。

输出格式

输出一个整数,表示最多能设计出的不同宝石搭配方案数。

样例输入

8
1 1 2 2 2 2 3 3

样例输出

4

数据范围

  • 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105
  • 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1ai109

题解

本题可以使用贪心的思想来解决。我们可以先将宝石按照大小进行排序,然后统计每种大小的宝石的数量。

接下来,我们按照宝石数量从多到少的顺序进行配对。对于数量最多的宝石,我们优先与其他种类的宝石进行配对。如果配对完所有其他种类的宝石后,该种宝石还有剩余,则再将剩余的宝石两两配对。

具体步骤如下:

  1. 将宝石按照大小进行排序。
  2. 使用字典 dict_ 统计每种大小的宝石的数量。
  3. 将字典转换为列表 a_,其中每个元素为 ( s i z e , c o u n t ) (size, count) (size,count) 的元组,表示宝石的大小和数量。
  4. 将列表 a_ 按照宝石数量从多到少进行排序。
  5. 遍历列表 a_,对于每种宝石:
    • 从下一种宝石开始,依次与其配对,直到当前宝石数量为 0 0 0 或者遍历完所有其他种类的宝石。
    • 如果当前宝石还有剩余,则将剩余的宝石两两配对。
  6. 输出配对的总数。

时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn),空间复杂度为 O ( n ) O(n) O(n)

参考代码

  • Python
n = int(input())
a = list(map(int, input().split()))
a.sort()

count = {}
for x in a:
    count[x] = count.get(x, 0) + 1

pairs = [(size, cnt) for size, cnt in count.items()]
pairs.sort(key=lambda x: x[1], reverse=True)

res = 0
for i in range(len(pairs) - 1):
    while count[pairs[i][0]] > 0:
        j = i + 1
        while j < len(pairs) and count[pairs[j][0]] > 0:
            count[pairs[i][0]] -= 1
            count[pairs[j][0]] -= 1
            res += 1
            j += 1
        if count[pairs[i][0]] >= 2:
            count[pairs[i][0]] -= 2
            res += 1

print(res)
  • Java
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(a);
        
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : a) {
            count.put(x, count.getOrDefault(x, 0) + 1);
        }
        
        List<int[]> pairs = new ArrayList<>();
        for (int size : count.keySet()) {
            pairs.add(new int[]{size, count.get(size)});
        }
        pairs.sort((p1, p2) -> p2[1] - p1[1]);
        
        int res = 0;
        for (int i = 0; i < pairs.size() - 1; i++) {
            while (count.get(pairs.get(i)[0]) > 0) {
                int j = i + 1;
                while (j < pairs.size() && count.get(pairs.get(j)[0]) > 0) {
                    count.put(pairs.get(i)[0], count.get(pairs.get(i)[0]) - 1);
                    count.put(pairs.get(j)[0], count.get(pairs.get(j)[0]) - 1);
                    res++;
                    j++;
                }
                if (count.get(pairs.get(i)[0]) >= 2) {
                    count.put(pairs.get(i)[0], count.get(pairs.get(i)[0]) - 2);
                    res++;
                }
            }
        }
        
        System.out.println(res);
    }
}
  • Cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    
    unordered_map<int, int> count;
    for (int x : a) {
        count[x]++;
    }
    
    vector<pair<int, int>> pairs;
    for (auto p : count) {
        pairs.emplace_back(p.first, p.second);
    }
    sort(pairs.begin(), pairs.end(), [](const auto& p1, const auto& p2) {
        return p1.second > p2.second;
    });
    
    int res = 0;
    for (int i = 0; i < pairs.size() - 1; i++) {
        while (count[pairs[i].first] > 0) {
            int j = i + 1;
            while (j < pairs.size() && count[pairs[j].first] > 0) {
                count[pairs[i].first]--;
                count[pairs[j].first]--;
                res++;
                j++;
            }
            if (count[pairs[i].first] >= 2) {
                count[pairs[i].first] -= 2;
                res++;
            }
        }
    }
    
    cout << res << endl;
    return 0;
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总,如果有需要的小伙伴可以关注后私信一下 KK领取,会在飞书进行同步的跟新。

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519038.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用 mitmproxy 抓包 grpc

昨天在本地执行 grpc 的 quick start&#xff08;python版本的&#xff09;&#xff0c;我了解 grpc 内部使用的是 HTTP2&#xff0c;所以我就想着抓包来试试&#xff0c;下面就来记录一下这个过程中的探索。 注意&#xff1a;我的电脑上面安装了 Fiddler Classic&#xff0c;…

数据结构day2--双向链表

双向链表: 即可以从头遍历到尾部和从尾部遍历到头部的链表&#xff0c;每个结点包括两个链域&#xff1a;前驱指针域和后继指针域&#xff0c;所以比起单向链表&#xff0c;其可以在任意一个结点访问前后两个结点 关于双向链表的一个完整步骤为&#xff1a; 创建一个表头结构…

微软detours代码借鉴点备注

comeasy 借鉴点1 Loadlibray的时间选择 注入库wrotei.dll&#xff0c;为了获取istream的接口&#xff0c;需要loadlibrary&#xff0c;但是在dllmain中是不建议这样做的。因此&#xff0c;动态库在dllmain的时候直接挂载了comeasy.exe的入口 //获取入口 TrueEntryPoint (i…

【其他】灾害预警,科技助力:手机地震预警功能设置指导

22024年4月3日7时58分在台湾花莲县海域遭遇了一场7.3级的强烈地震&#xff0c;震源深度12公里&#xff0c;震中位于北纬23.81度&#xff0c;东经121.74度&#xff0c;距台湾岛约14公里。震中5公里范围内平均海拔约-3560米。这场突如其来的自然灾害给当地居民的生活带来了巨大的…

【MATLAB】GA_BP神经网络时序预测算法

有意向获取代码&#xff0c;请转文末观看代码获取方式~ 1 基本定义 GA_BP神经网络时序预测算法是一种结合了遗传算法(GA)和反向传播(BP)神经网络的时序预测方法。它利用了遗传算法的全局搜索和优化能力&#xff0c;以及BP神经网络的学习和逼近能力&#xff0c;可以更有效地预…

Qtxlsx第三方库的安装和使用

本文仅作为一个记录&#xff0c;安装QtXlsx方便操作excel&#xff0c;主要参考了这篇博文&#xff1a;https://blog.csdn.net/u014779536/article/details/111769792 1&#xff0c;下载安装Perl脚本Strawberry Perl for Windows&#xff0c;默认安装strawberry-perl-5.30.0.1-…

【Redis教程0x0F】Redis实战篇

Redis如何实现延迟队列&#xff1f; 延迟队列是指把当前要做的事情&#xff0c;往后推迟一段时间再做。延迟队列的常见使用场景有以下几种&#xff1a; 在淘宝、京东等购物平台上下单&#xff0c;超过一定时间未付款&#xff0c;订单会自动取消&#xff1b;打车的时候&#x…

ES6学习(五)-- Module 语法

文章目录 Module 语法1.1 痛点介绍(1) 异步加载(2) 私密(3) 重名(4) 依赖 1.2 解决方法(1) 解决异步加载问题(2) 解决私密问题(3) 重名解决方法(4) 解决依赖问题 1.3 模块化使用案例 Module 语法 之前js 出现的某些痛点&#xff1a; 在script 中引入的变量名不可以重复&#…

深入了解 Python 中标准排序算法 Timsort

&#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ Timsort&#xff1a;一个非常快速的、时间复杂度为 O ( n l o g n ) O (n \ log\ n) O(n log n)、稳健&#xff08;即不改变等值元素间的相对顺序&#xff09;的排序算法&#xff0c;在处理真实世界数…

蓝桥杯单片机真题实践篇

这里就不完全写思路过程代码什么的&#xff0c;这一篇文章就写我在训练真题中遇到的过程。 &#xff08;呜呜呜&#xff0c;时间不够辣&#xff0c;能做多少算多少吧....&#xff09; 十三届省赛题 问题1&#xff1a;数码管的数字消影不明显 &#xff08;参考&#xff1a;蓝…

ms-前端八股文

1、暂时性死区 是指在 JavaScript 中使用 let 或 const 声明变量时&#xff0c;变量在其声明之前不能被访问或使用的特性。 var可以变量提升&#xff08;在 JavaScript 中&#xff0c;变量声明提升是指在执行代码之前&#xff0c;变量声明会被提升到作用域的顶部。&#xff0…

SSM 项目学习(Vue3+ElementPlus+Axios+SSM)

文章目录 1 项目介绍1.1 项目功能/界面 2 项目基础环境搭建2.1 创建项目2.2 项目全局配置 web.xml2.3 SpringMVC 配置2.4 配置 Spring 和 MyBatis , 并完成整合2.5 创建表&#xff0c;使用逆向工程生成 Bean、XxxMapper 和 XxxMapper.xml2.6 注意事项和细节说明 3 实现功能 01-…

【C++】二叉搜索数

目录 一、二叉搜索树的概念 二、二叉搜索树的模拟实现 1、定义节点 2、构造二叉树 3、析构二叉树 ​4、拷贝二叉树 5、二叉树赋值 6、插入节点 &#x1f31f;【非递归方式】 &#x1f31f;【递归方式】 7、打印节点 8、搜索节点 &#x1f31f;【非递归方式】 &…

臻奶惠无人售货奶柜:定义新时代的健康生活方式

臻奶惠无人售货奶柜&#xff1a;定义新时代的健康生活方式 臻奶惠的无人售货奶柜&#xff0c;代表着科技与生活方式融合的一个新趋势&#xff0c;它不仅仅是一个简单的购买平台&#xff0c;更是一种全新的生活体验。在这个快节奏的时代&#xff0c;臻奶惠通过其无人售货奶柜&a…

第四百四十三回

文章目录 1. 概念介绍2. 思路与方法2.1 整体思路2.2 使用方法 3. 示例代码4. 内容总结 我们在上一章回中介绍了"自定义Action菜单"相关的内容&#xff0c;本章回中将介绍如何获取屏幕相关参数.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在本…

(一)小案例银行家应用程序-介绍

案例示例如下所示&#xff1a; 登录之后就会出现下面所示&#xff1a; 项目案例流程图如下 ● 首先我们建立四个账号对象&#xff0c;用于登录 const account1 {owner: ItShare,movements: [200, 450, -400, 3000, -650, -130, 70, 1300],interestRate: 1.2, // %pin: 11…

数学建模-最优包衣厚度终点判别法(主成分分析)

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是viperrrrrrr~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#xff…

线程安全问题与解决方法~

本文内容仅供对线程安全问题、锁的认识和使用等&#xff0c;进行一个介绍。适合小白的文章&#xff01; 目录 一、线程安全问题 1.什么是线程安全问题 2.解释上述安全问题 3.线程安全的五大原因 二、使用锁解决线程安全问题 1.介绍锁 2.加锁操作 一、线程安全问题 在多线…

【吊打面试官系列】Redis篇 - 使用过 Redis 分布式锁么,它是什么回事?

大家好&#xff0c;我是锋哥。今天分享关于 【使用过 Redis 分布式锁么&#xff0c;它是什么回事&#xff1f;】面试题&#xff0c;希望对大家有帮助&#xff1b; 使用过 Redis 分布式锁么&#xff0c;它是什么回事&#xff1f; 先拿 setnx 来争抢锁&#xff0c;抢到之后&#…

C语言中的字符与字符串:魔法般的函数探险

前言 在C语言的世界里&#xff0c;字符和字符串是两个不可或缺的元素&#xff0c;它们像是魔法般的存在&#xff0c;让文字与代码交织出无限可能。而在这个世界里&#xff0c;有一批特殊的函数&#xff0c;它们如同探险家&#xff0c;引领我们深入字符与字符串的秘境&#xff0…