米哈游 9.24 java笔试

单选题和多选题难度还可以;
算法题第三道我还是卡在了双循环超时上
对于一个一维数组

有没有佬能指点一下,这种双循环该怎么优化以避免超时呢?
全部评论
就是算1*a[i-1]+2*a[i-2]+....+i-1*a[1]再乘上a[i]就可以啦
2 回复 分享
发布于 2023-09-24 22:06 安徽
可以把sum[i-1]和t[i-1]换成一个变量存储,也能节省一些空间 int n = in.nextInt(); int[] a = new int[n+1]; long[] sum = new int[n+1];//存前缀和 sum[0]=0; long[] t = new int[n+1]; t[0]=0; long res; for(int i=1;i<=n;i++){ a[i]=in.nextInt(); sum[i]=sum[i-1]+a[i]; t[i]=t[i-1]+sum[i-1]; long tmp = (t[i]*a[i])%1000000007; res = (res+tmp)%1000000007; }
1 回复 分享
发布于 2023-09-25 08:56 上海
开辟两个数组b和c,数组b遍历一次k*a[k]+b[k-1],数组c遍历一边a[k]+c[k-1],最后求和res+=a[k]*(b[k]-k*c[k]),应该是这么解的吧(还有些细节0应该手动初始化,k从1开始)
1 回复 分享
发布于 2023-09-24 23:07 四川
这样步步mod就可以保证不溢出了
1 回复 分享
发布于 2023-09-24 22:59 湖北
就是j*aj的和乘ai,然后因为每层计算前面的j会-1,所以每次计算前给他减掉i后面所有数的sum就出来了
1 回复 分享
发布于 2023-09-24 22:07 安徽
合并一下同类项就可以a1(a2+2a3+3a4+…)
1 回复 分享
发布于 2023-09-24 22:04 湖北
众安保险投了没,众安科技投了没,500强工资高,流程刚开始,保险公司可老有钱了~ https://app.mokahr.com/m/campus_apply/zhongan/71908?recommendCode=DS5jTXpa#/jobs
点赞 回复 分享
发布于 2023-09-25 10:10 上海
一样的循环 超时过20
点赞 回复 分享
发布于 2023-09-24 22:18 陕西
前缀和20%,改long long70%
点赞 回复 分享
发布于 2023-09-24 22:15 广东
只用单层循环即可,首先你需要记录前缀和。然后第二次计算的时候,需要有一个变量,每次只需要计算临时变量*arr【i】就行,这个临时变量每次循环后+第i个前缀和。
点赞 回复 分享
发布于 2023-09-24 22:13 北京
为啥我这种后缀和的方法不超时但是还是只能过20啊,result和result2我自验证是一样的
点赞 回复 分享
发布于 2023-09-24 22:08 湖北
我想出来了后缀和的方法,但是结果错误,不知道哪搞错了
点赞 回复 分享
发布于 2023-09-24 22:01 湖北
蹲,感觉是数学公式推导,能在O(n)算完
点赞 回复 分享
发布于 2023-09-24 22:01 江苏
试了分治还是超时...
点赞 回复 分享
发布于 2023-09-24 22:00 北京
蹲 我也是
点赞 回复 分享
发布于 2023-09-24 22:00 新加坡

相关推荐

不愿透露姓名的神秘牛友
2025-12-04 02:00
offer1:字节跳动(北京)-&nbsp;后端开发岗-&nbsp;薪资:总包42w(基本工资30w+绩效6w+年终奖6w),15薪,加班费按法定标准发放-&nbsp;福利:公积金按12%缴纳,无宿舍,每月住房补贴2000元,餐补1500元,每年2次体检,免费健身房-&nbsp;工作强度:996是常态,忙的时候可能到凌晨,团队节奏快,压力大-&nbsp;其他:平台大,技术氛围浓,晋升路径清晰,对转行选手来说履历加分多,但北京生活成本高,租房压力大offer2:美团(上海)-&nbsp;客户端开发岗-&nbsp;薪资:总包38w(基本工资26w+绩效5w+年终奖7w),14薪,加班无加班费,可调休-&nbsp;福利:公积金按10%缴纳,无宿舍,每月住房补贴1800元,餐补800元,每年1次体检,节日福利丰富-&nbsp;工作强度:995为主,偶尔周末加班,项目紧急时会通宵,整体压力中等-&nbsp;其他:公司业务成熟,行业地位稳固,客户端岗位需求稳定,上海生活节奏比北京稍缓,但租房成本仍较高offer3:网易(杭州)-&nbsp;测试开发岗-&nbsp;薪资:总包32w(基本工资22w+绩效4w+年终奖6w),13薪,加班较少,无加班费-&nbsp;福利:公积金按12%缴纳,提供员工宿舍(单人间,前两年免费,第三年按市场价5折),每月餐补1000元,每年1次体检+1次旅游补贴-&nbsp;工作强度:965为主,几乎无强制加班,团队氛围轻松,摸鱼文化盛行-&nbsp;其他:杭州生活成本低于北上,宿舍省房租,测试开发岗入门难度低,适合转行过渡,但技术成长速度可能不如开发岗,未来跳槽竞争力未知本人情况:传统工科转行,编程基础一般,想快速提升技术能力,同时也希望工作生活能平衡,未来不确定是否留在一线城市。有没有同款转行选手或互联网前辈给点建议呀?
森七菜:梦到什么说什么属于是
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务