美团0316春招笔试题

2024-03-29 03:20
文章标签 笔试 美团 春招 0316

本文主要是介绍美团0316春招笔试题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

下面是美团2024-03-16笔试真题,进行了VP,由于未参与评测,故不保证正确性,仅供参考。

第一题 小美点外卖

在这里插入图片描述

求和然后减去满减和红包即可。

#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
int n, t, x, y;
LL ans;int main() {scanf("%d", &n);while (n -- ) {scanf("%d", &t);ans += t;}scanf("%d%d", &x, &y);printf("%lld\n", ans - x - y);
}

第二题 小美的合法单词

在这里插入图片描述

考虑三种情况分别需要的操作次数,取最小值即可。

先扫描字符串s,并用变量big和small分别统计字符串s中大写字母、小写字母的个数。

然后还要处理第一个字符是大写的情况:

首先初始化变量t=s.size(),当第一个字符是大写字母时,执行t = t - 1 - small。减去1是因为去掉第一个大写字母,然后再减去small,这样得到的就是后面剩余的大写字符个数。

为什么是t-1-small而不是t-1-big呢?举个例子:s=“AaaBbCD”,此时big=4,small=3。

  • 若执行t-1-big,则此时t的结果就是2,那么答案为min{big, small, t} = 2,但显然答案应该是3(将后面的B,C,D修改为小写)。
  • 若执行t-1-small,则此时t的结果就是3,那么答案为min{big, small, t} = 3,这显然就是正确答案3(将后面的B,C,D修改为小写)。

说白了就是由于题目要求第一个字母大写,后面所有字母都是小写。t-1-small就是将后面统计除了首位这个大写字母外剩余部分的大写字母个数,而我们需要将这些大写字母个数就是我们需要修改为小写字母所需要的操作次数。

#include <bits/stdc++.h>
using namespace std;int main() {string s;cin >> s;int big = 0, small = 0, t = s.size();for (auto& c : s) {if (c >= 'A' && c <= 'Z')   ++ big;else if (c >= 'a' && c <= 'z')  ++ small;}if (s[0] >= 'A' && s[0] <= 'Z') t = t - 1 - small;printf("%d\n", min({small, big, t}));
}

第三题 翻倍元素

在这里插入图片描述

统计每个元素最后翻倍的次数即可。

如下表:

数组元素a[]翻倍次数times[]最终结果
a[1]=11 1 × 2 1 1\times 2^1 1×21
a[2]=21 2 × 2 1 2\times 2^1 2×21
a[3]=32 3 × 2 2 3\times 2^2 3×22
a[4]=42 4 × 2 2 4\times 2^2 4×22

因此最终结果为2、4、12、16,答案即为2+4+12+16=34。

对于快速求 a b a^b ab显然可以使用快速幂。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, MOD = 1e9 + 7;
int a[N], times[N], n, m;int qmi(int a, int b) {int ans = 1;while (b) {if (b & 1)  ans = ans * a % MOD;a = a * a % MOD;b >>= 1;}return ans % MOD;
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++ i) {scanf("%d", &a[i]);times[i] = m;}for (int i = 1; i <= m; ++ i) {int x;scanf("%d", &x);-- times[x];}int ans = 0;for (int i = 1; i <= n; ++ i) {ans = (ans + a[i] * qmi(2, times[i]) % MOD) % MOD;}printf("%d\n", ans);
}

第四题 小美的众数

在这里插入图片描述

首先需要观察到元素 a i a_i ai只有1和2这两种取值。由于它的数值只有1和2,所以记录一个前缀和。如果说当前值是1就前缀和加1,如果说当前值是2,就前缀和减1。即我们定义数组 s i s_i si表示区间 [ 1 , i ] [1,i] [1,i]中元素1和元素2的被标记为+1和-1之后的前缀和。

对于一个前缀和 s i s_i si来说,它前面有多少个 s j s_j sj的值比 s i s_i si小,就说明,1的个数会大于等于2的个数,那么这些数量的区间,众数必然是元素1。 i i i减去这些区间的数量,也就是剩下的区间数量,众数就是2了。

对于如何求一个前缀和 s i s_i si来说,它前面有多少个 s j s_j sj的值比 s i s_i si小,这可以用树状数组来求解。

为什么要加偏移量OFFSET = n+1呢?

这是因为数组s[]取值有可能是负数(这是由于将元素1和元素2的被标记为+1和-1导致的),最坏情况下s[]取值可能是 − n -n n。但是我们知道树状数组下标是从1开始的,不能是<1的,故我们加上偏移量n+1,使得保证树状数组的下标是正确从1开始。

如何理解query(s[i] + OFFSET) + (i - query(s[i] + OFFSET)) * 2这个式子呢?

  • query(s[i] + OFFSET)其实完整写法是query(s[i] + OFFSET) * 1,它求解的是如果当前区间 [ 1 , i ] [1,i] [1,i]中的众数是元素1的话,那么就求这些子区间中众数1的总和。
  • (i - query(s[i] + OFFSET)) * 2,它求解的是如果当前区间 [ 1 , i ] [1,i] [1,i]中的众数是元素1的话,那么就求这些子区间中众数1的总和。当前有 i i i个元素,其中众数是元素1的个数有query(s[i] + OFFSET)个,那么众数是元素2的个数就为(i - query(s[i] + OFFSET))。然后求这些子区间中众数2的总和即可。
#include <bits/stdc++.h>
const int N = 2e5 + 10;
using LL = long long ;
int a[N], s[N], tr[N * 2], n;inline int lowbit(int x) {return x & -x;
}void modify(int x, int k) {for (int i = x; i <= 2 * n + 10; i += lowbit(i)) tr[i] += k;
}LL query(int x) {LL ans = 0;for (int i = x; i; i -= lowbit(i)) ans += tr[i];return ans;
}int main() {scanf("%d", &n);int OFFSET = n + 1;	// 偏移量,防止下标是负数,使得下标从1开始for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);modify(0 + OFFSET, 1);  // 边界初始化!!!LL ans = 0;for (int i = 1; i <= n; ++ i) {if (a[i] == 1)  s[i] += s[i - 1] + 1;else    s[i] += s[i - 1] - 1;// query(s[i] + OFFSET) * 1计算出如果1是众数时的和// (i - query(s[i] + OFFSET)) * 2计算出如果2是众数时的和ans += query(s[i] + OFFSET) + (i - query(s[i] + OFFSET)) * 2;modify(s[i] + OFFSET, 1);}printf("%lld", ans);
}

第五题 小美的逆序对

在这里插入图片描述

本题可以考虑使用树状数组来求逆序对。

我们可以先对原数组求一遍逆序对。对于第 i i i个数字,它在变为最小的数字后,在它之前的所有比它小的数字都会和它组成逆序对,在它之后所有比它小的数字会由原本构成逆序对转变成不构成逆序对。设在它左侧比它小的数字的个数为cnt,那么在它右侧比它小的数字的个数就是x - 1 - cnt。因此当元素x取反后,它左侧这cnt个数字就比x大,增加了cnt个逆序对,然后它右侧这x-1-cnt个数字就比x大,减少了x-1-cnt个逆序对。由此逆序对的增量就是x - (x - 1 - cnt)个。考虑原本的逆序对数目s,则第 i i i个数字取反后的逆序对数目为s + x - (x - 1 - cnt)

#include <bits/stdc++.h>
const int N = 2e5 + 10;
using LL = long long ;
int t[N], tr[N], n;inline int lowbit(int x) {return x & -x;
}void modify(int x, int k) {for (int i = x; i <= n; i += lowbit(i)) tr[i] += k;
}LL query(int x) {LL ans = 0;for (int i = x; i; i -= lowbit(i)) ans += tr[i];return ans;
}int main() {scanf("%d", &n);LL s = 0;for (int i = 1; i <= n; ++ i) {int x;scanf("%d", &x);s += query(n) - query(x);// cnt表示x左侧比x小的元素个数, x - 1 - cnt表示x右侧比x小的元素个数LL cnt = query(x - 1);t[i] = cnt - (x - 1 - cnt);modify(x, 1);}for (int i = 1; i <= n; ++ i) printf("%lld ", s + t[i]);
}

这篇关于美团0316春招笔试题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/857465

相关文章

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

两道笔试题

“char a='\72'”是什么意思? 这么理解:\为转义字符,\072转义为一个八进制数072,也就是十进制数的58买一送一,将转义字符对照表也一并贴给你吧:转义字符 意义 ASCII码值(十进制) \a 响铃(BEL) 007 \b 退格(BS) 008 \f 换页(FF) 012 \n 换行(LF) 010 \r 回车(CR) 013 \t 水平制表(HT) 009 \v 垂直制表(VT

华为23年笔试题

消息传输 题目描述 在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中,分布着一些信号塔,用于区域间通信。 每个单元格可以有以下三种状态:  值 0 代表空地,无法传递信号;  值 1 代表信号塔 A,在收到消息后,信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔; 值 2 代表信号塔 B,在收到消息后,信号塔 B 可以在 2ms

实现的动态规划问题华为笔试题C++实现

秋招刷力扣题,我觉得我对动态规划不是熟练,在此处做总结 动态规划(Dynamic Programming,DP)算法通常用于求解某种具有最优性质的问题。在这类问题中,可能会有许多可行解,每一个解都对应一个值,我们希望找到具有最优值的解。我觉得最大的问题就是对问题的分解,分解后的问题与分解前的问题具有相同的决策机制,将决策机制进行抽象,最终可以得到对应的解; 动态规划中开始介绍的爬楼梯等问题,答

某公司笔试编程题

参加了某公司编程题,这些题都来自牛客网,记录总结吧! 一、蛇形矩阵 题目描述 蛇形矩阵是有1开始的自然数依次排列成的一个上三角矩阵. 接口说明 void GetResult(int Num, int* pResult);输入参数:int Num :输入的正整数N输出参数:int *pResult: 指向放蛇形矩阵的字符串指针指针指向的内存区域保证有效 样例输入: 4

CVTE java web后台实习生笔试+技术一面总结

投的第一份简历,也可以说是第一次写笔试和参加面试。题在前面,总结在最后,努力不骗人。 笔试 题型:20道不定项选择题+2道算法题+1道架构设计题 选择题 选择题出的很全面,因为是不定项选择,一道题就可以考很多知识点。 当时做的时候以为笔试都是这么难,做完实验室同学告诉我这个算比较难的了,而且据我观察可能是跟春招找正式offer的一批难度的题。可能最后过的标准不一样吧。 选项信息量很大,

大厂算法例题解之网易2018秋招笔试真题 (未完)

1、字符串碎片 【题目描述】一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,“aaabbaaac” 是由下面碎片组成的:‘aaa’,‘bb’,‘c’。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的 平均长度是多少。 输入描述: 输入包括一个字符串 s,字符串 s 的长度 length(1 ≤ length ≤ 50),s 只含小写字母(‘a’-‘z’) 输出描述

C++笔试强训12、13、14

文章目录 笔试强训12一、选择题1-5题6-10题 二、编程题题目一题目二 笔试强训13一、选择题1-5题6-10题 二、编程题题目一题目二 笔试强训14一、选择题1-5题6-10题 二、编程题题目一题目二 笔试强训12 一、选择题 1-5题 引用:是一个别名,与其被引用的实体公用一份内存空间,编译器不会给引用变量单独开辟新的空间。A错误 故选A。 A

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

Java笔试面试题AI答之JDBC(3)

文章目录 13. 编写JDBC连Oracle的程序?14. 简述JDBC的主要组件有哪些 ?15. JDBC中如何防止SQL注入攻击?1. 使用预处理语句(PreparedStatement)2. 避免在SQL查询中直接拼接用户输入的数据总结 16. JDBC的脏读是什么?哪种数据库隔离级别能防止脏读?脏读(Dirty Read)哪种数据库隔离级别能防止脏读? 17. 简述JDBC ex