京东9.2算法岗笔试编程卷:题面+解答

第一题

题目描述:a有三个区间[l1,r1] [l2,r2] [l3,r3],a,b在这三个区间内同时选择一个自己喜欢的区间,这两个区间不能相同

接下来a和b需要在自己喜欢的区间内选择一个数,且必须都在对方的区间内,还要使得这两个数的和尽可能大

输入

1 3 2 4 4 6

输出

8

范围:均小于1e9;如果不存在这种值,输出-1

思路:确定ab区间后,每次选交集最大的数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int solve(int a1,int b1,int a2,int b2)
{
	if(b1<a2 || b2<a1)
		return -1;
	return min(b1,b2)*2;
}
int main()
{
	int a1,b1,a2,b2,a3,b3;
	cin>>a1>>b1>>a2>>b2>>a3>>b3;
	cout<<max(max(solve(a1,b1,a2,b2),solve(a1,b1,a3,b3)),solve(a2,b2,a3,b3));
	return 0;
}

第二题

题目描述:小红准备买n件物品,第i件物品的价格是ai。另外,小红有m种优惠券,第i个优惠券是:买一件价格不小于bi的商品时,可以减去ci的价格。每件商品最多只能用一次优惠券。每种优惠券可以使用多次。问买全部商品最少需要多少钱?

输入

3 2

4 8 6

5 1

8 5

输出

12

数据范围:n,m<=200000 ;ai,bi,ci<=1e9

思路:从小到大考虑所有优惠券的bi,那么优惠券的ci也应该递增。因此删去所有无用的优惠券,再找每件商品能用的最大券,这里可以用二分加速

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

const int N=2e5+3;

int n,m;
int a[N];

struct yh{
	int b,c;
	bool operator<(const yh&o)const{
		if(b==o.b)
			return c>o.c;
		return b<o.b;
	}; 
}t[N];

int cnt=0, inc[N];
map<int,int>h;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);

	for(int i=0;i<m;i++)
		scanf("%d%d",&t[i].b,&t[i].c);

	sort(t,t+m);
	int a1=-1, b1=-1;
	for(int i=0;i<m;i++)
		if(t[i].b>a1 && t[i].c>b1)
		{
			a1=t[i].b;
			b1=t[i].c;
			inc[cnt++]=a1;
			h[a1]=b1;
		}
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		int*t=upper_bound(inc,inc+cnt,a[i]);
		if(t>inc)
			ans+=a[i]-h[*(t-1)];
		else
			ans+=a[i];
		
	}
	cout<<ans;
	return 0;
}

第三题

题目描述:小红拿到了一个矩形的蛋糕,分成n行m列,共n*m个区域,每个区域是一个小正方形,已知蛋糕每个区域都有一个美味度

小红希望切割出一个正方形的小蛋糕(正方形边长必须平行于矩形的边长,且必须都是完整的区域),自己吃掉正方形的部分,把剩下的部分给小紫吃

小红希望两人吃的部分的美味度之和尽可能接近,小红吃的蛋糕美味度之和为s1,小紫吃的蛋糕美味度之和为s2,请输出|s1-s2|的最小值

输入

3 3

1 2 3

2 3 4

3 2 1

输出

1

数据范围:n,m<1000

思路:求|s1*2-sum|的最小值,其中sum为整个矩阵的和

首先预处理矩阵前缀和,从而O(1)地求子矩阵的和

考虑在每个位置上,枚举正方形的边长,可以O(n3)地求解;在枚举正方形的边长时,可以用二分查找来快速找到最小值点,整体复杂度O(n2*logn)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=1e3+2;

int n,m;
int a[N][N];
ll sum_l[N][N], sum[N][N];
ll ans=1e10;

bool check(int x, int y, int r)
{
	ll s1 = sum[x+r-1][y+r-1] -sum[x-1][y+r-1] -sum[x+r-1][y-1] + sum[x-1][y-1];
	return s1*2 < sum[n][m];
}
void solve(int x,int y)
{
	int l=1, r=min(n-x+1,m-y+1),mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(x,y,mid))
			l=mid+1;
		else
			r=mid;
	}
	mid =l;
	
	ll s1,d;
	s1 = sum[x+mid-1][y+mid-1] -sum[x-1][y+mid-1] -sum[x+mid-1][y-1] + sum[x-1][y-1];
	d = s1*2 - sum[n][m];
	if(d<0)d*=-1;
	ans=min(ans,d);

	if(mid>1)
	{
		mid--;
		s1 = sum[x+mid-1][y+mid-1] -sum[x-1][y+mid-1] -sum[x+mid-1][y-1] + sum[x-1][y-1];
		d = s1*2 - sum[n][m];
		if(d<0)d*=-1;
		ans=min(ans,d);
	}

}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
			
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			sum_l[i][j]=sum_l[i][j-1]+a[i][j];

	for(int j=1;j<=m;j++)
		for(int i=1;i<=n;i++)
			sum[i][j]=sum[i-1][j]+sum_l[i][j];
			
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			solve(i,j);
			
	cout<<ans;
	return 0;
}

#笔试透题##笔试题目##笔试##笔试真题#
全部评论
我请求超时..交不上去什么鬼😡
1 回复 分享
发布于 2023-09-02 12:31 河南
佑神我的超人
点赞 回复 分享
发布于 2023-09-02 13:32 湖北

相关推荐

咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
刘湘_passion:太强了牛肉哥有被激励到
点赞 评论 收藏
分享
评论
11
22
分享

创作者周榜

更多
牛客网
牛客企业服务