首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
Colorful612
C++
发布于江苏
关注
已关注
取消关注
@至今依然无offer:
字节面试一道常见的题目
最近看大家面经总有一道常见的题目: 数组A中给定可以使用的1~9的数,返回由A数组中的元素组成的小于n的最大数。例如A={1, 2, 4, 9},n=2533,返回2499有两个常见思路:1.暴力递归回溯,最后判断;2.贪心思想。 其中第二个思路比较有争议,看讨论大家好像也没有很统一的想法,先贴一下自己的代码 #include <iostream>#include <stack>#include <string>#include <vector>using namespace std;int n, x;//将剩余位全部设置为数组里的最大值void getmax(stack<int>& sres, int value, int count){ for(int i = 0; i < count; i++){ sres.push(value); }}//二分查找,取得小于等于传入值的最大值int getindex(vector<int>& vec, int value){ int left = 0, right = vec.size()-1, target = -1; while(left <= right){ int mid = (right-left) / 2 + left; if(vec[mid] > value){ right = mid-1; }else if(vec[mid] < value){ target = mid; left = mid + 1; } else return mid; } return target;}//主函数int helper(vector<int>& vec, string s){ stack<int>sres; int ssize = s.size(); for(int i = 0; i < ssize; i++){ int countnum = s[i] - '0'; int index = getindex(vec, countnum); //如果当前位置的值比数组的所有位置都要小,栈要进行弹出操作,相当于去回溯 if(index == -1){ int tmpcount = 0; while(!sres.empty()){ int top = sres.top(); sres.pop(); int tmpindex = getindex(vec, top-1); if(tmpindex == -1) continue; sres.push(vec[tmpindex]); tmpcount++; break; } if(sres.empty()) getmax(sres, vec[n-1], ssize-1); else getmax(sres, vec[n-1], ssize - sres.size()); break; }else if(vec[index] == countnum){ //若是相等,就加进去 sres.push(countnum); }else if(vec[index] < countnum){ //若是二分查找的值于当前值并不相等,那么把二分查找的值加入,并且后面的值全取数组的最大值 sres.push(vec[index]); getmax(sres, vec[n-1],ssize-i-1); break; } } int res = 0, count = 1; while(!sres.empty()){ res += sres.top() * count; count *= 10; sres.pop(); } return res;}int main() { cin >> n; vector<int> vec(n); for(int i = 0; i < n; i++) cin >> vec[i]; cin >> x; sort(vec.begin(), vec.end()); //传入的值是x-1 std::cout << helper(vec, to_string(x-1)) << std::endl; return 0;}我觉得这个代码是正确的,希望大家可以指正一下, 我自己编造的例子基本都过了。
点赞 11
评论 9
全部评论
推荐
最新
楼层
联想
校招火热招聘中
官网直投
相关推荐
互联网农民工_
05-07 09:24
清华大学 计算机类
暑期实习超全最新更新,技术岗看过来!
5.7 更新 华资软件:https://sinobest.zhiye.com/ 万兴科技:https://app.mokahr.com/campus_apply/wanxingkeji/41591#/jobs?zhineng%5B0%5D=141601 宁德时代:https://talent.catl.com/#/ 奇安信:https://campus.qianxin.com/campus/intern 智臾科技:https://app.mokahr.com/campus-recruitment/dolphindb/101962#/jobs?commitment=%E5%85%A8%E8%8...
投递东方财富等公司10个岗位 >
点赞
评论
收藏
转发
sorano_
05-09 21:48
门头沟学院 计算机类
拼多多5.9笔试3.88/4,但是cpp,有希望进面吗
所有流程都在泡池子,希望这段时间有个面试来转移注意力pdd是笔试完再发测评再约面的吗?cpp选手是不是压根进不了面或者进面就是送的
投递拼多多等公司10个岗位 >
点赞
评论
收藏
转发
有力量的杰克吃不饱
03-30 02:11
南开大学 计算机类
是我不配了
只走了两分钟流程?!
点赞
评论
收藏
转发
chenxi同学
04-02 12:18
西安邮电大学 计算机类
面试最难绷的一集
今天面试到最后的时候,面试官说,来写道算法题吧。哥们打开链接一开,环形链表?狠狠拿下😋结果因为力扣上有以前写过的代码,面试官说你以前做过了吗,那我们换一道吧。整了一道字符串相关的,一点思路没有😇大伙一定要记得清空力扣的做题记录😭
点赞
评论
收藏
转发
思考的陈
05-10 18:22
Java
【面试官】知道MySQL慢查询吗?
面试官:知道MySQL慢查询吗? 面试官:在工作中你怎么优化SQL的? 面试官:遵循第二范式就一定最优? 面试官:还有呢? 面试官:在工作中,表索引你怎么设计的? 面试官:那索引建立越多,查询效率就越高吗? 👉以【面试官面试】形式覆盖Java程序员所需掌握的Java核心知识、面试重点 📚本期是《MySQL系列》,其他系列博客请订阅专栏《Java Offer训练营》 ❤创作不易,不妨点赞、收藏、关注支持一下 文章目录 慢查询 SQL优化 表设计优化 SQL语句优化 索引如何设计 1. 慢查询 面试官:知道MySQL慢查询吗? MySQL的慢查询日志可以记录执行时间超...
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
全站热榜
1
...
寻找暑期实习的记忆就此封档啦
1.1W
2
...
5.11校招&实习招聘信息汇总
8300
3
...
【奖】硬件牛牛答辩过过过!有奖话题领京东卡啦~
6816
4
...
微信支付一面
5333
5
...
5.10校招&实习招聘信息汇总
5145
6
...
无题
5085
7
...
5.9校招&实习招聘信息汇总
5013
8
...
兄弟们之间就别卷了吧,选自己喜欢的offer得了
4846
9
...
小红书一面(半凉)
4560
10
...
阿里国际二面,遇到神人了
4214
正在热议
#
牛客帮帮团来啦!有问必答
#
615693次浏览
10475人参与
#
金融银行面经
#
3273次浏览
94人参与
#
秋招开了,你想投哪些公司呢
#
112519次浏览
3217人参与
#
五一之后,实习真的很难找吗?
#
9867次浏览
64人参与
#
我想象的工作vs实际工作
#
86999次浏览
1491人参与
#
浅聊一下我实习的辛苦费
#
77392次浏览
719人参与
#
简历中的项目经历要怎么写
#
413986次浏览
6946人参与
#
租房前辈的忠告
#
28034次浏览
1953人参与
#
你已经投递多少份简历了
#
279585次浏览
4254人参与
#
华为开奖那些事
#
685546次浏览
5921人参与
#
春招你拿到offer了吗
#
351372次浏览
5219人参与
#
我的成功项目解析
#
78725次浏览
2308人参与
#
机械人怎么评价今年的华为
#
63884次浏览
513人参与
#
我的上岸简历长这样
#
154114次浏览
3083人参与
#
华为工作体验
#
19677次浏览
161人参与
#
快手工作体验
#
52554次浏览
988人参与
#
晒一晒我的offer
#
3161399次浏览
52710人参与
#
我发现了面试通关密码
#
316736次浏览
6096人参与
#
第一次面试
#
46578次浏览
727人参与
#
你的简历改到第几版了
#
290732次浏览
4427人参与
牛客网
牛客企业服务