字节面试一道常见的题目

最近看大家面经总有一道常见的题目:
数组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;
}

我觉得这个代码是正确的,希望大家可以指正一下, 我自己编造的例子基本都过了。

#字节跳动##面经##笔经##C/C++#
全部评论
感觉我练过这道题啊
点赞 回复 分享
发布于 2022-05-19 16:19
遇到过!!!字节一面,没做出来哈哈哈哈,暴力
1 回复 分享
发布于 2022-05-19 16:54
我的想法是这样的,首先把给定的数组按从大到小排序,然后对给定的数字,检测其从高到低每位是否在给定的数组中(这里可以考虑复制一个set或者dict来加快查找?),如果在数组中,就直接填充对应位,否则,找到对应的数组中的小于对应数字的最大值,填充之后,后面的所有位使用数组中最大值填充,如果数组中没有小于对应位数字的,就要回溯到上一位重复操作,直到找到这样的位数,并把后面的位数按最大值填充
2 回复 分享
发布于 2022-05-24 15:02
我感觉这个不复杂吧,以题目为例,n=2533,先到数组中找有没有2,如果有,就递归,递归时n=533,将递归的结果加上2000就是答案了。如果没有2,就更简单了,找到第一个比2小的数y,找到最大的数x,结果一定是yxxx,如果找不到比2小的数了,那结果一定是xxx
点赞 回复 分享
发布于 2022-05-22 10:47
枚举➕二分行吗
点赞 回复 分享
发布于 2022-05-22 21:33
三面做了,然后过了
点赞 回复 分享
发布于 2022-05-24 13:47
牛逼,你至今无 offer 我不理解
点赞 回复 分享
发布于 2022-06-01 20:18
感觉是数位dp
点赞 回复 分享
发布于 2023-03-09 23:12 湖北
楼主,为什么helper要传入n-1而不是n呀
点赞 回复 分享
发布于 2023-07-23 17:15 北京

相关推荐

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;我仔细思考了一下灵犀互娱四面为啥挂,想到了一个非常有可能的原因。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;四面是技术面,说是技术面但实际上问的全是开放性问题,比如你最近了解哪些国际进展(不限于技术),比如你对AI&nbsp;的看法等等。按理说这些问题时很好回答的,但是我犯了一个致命的问题,我一直在谈老东家。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;问到国际进展的时候,我说我了解到了字节国际电商的业务进展和今年的形式,然后面试官问你觉得国际电商业务转好的原因是什么,我又一直在谈周受资的牛逼和能力之强大。聊到AI的看法时,我也提到实习的时候字节这边也有很多AI结合创新的点子,等等。我提了太多太多的字节,在四面的时候,这是很致命的,给面试官一种你其实根本不想去他们那边,只关注字节的感觉。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;这是我踩到最大的雷区。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;以下还有几个我认为的雷区:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1.提前准备没做好&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;在实习的时候面钉钉,当时提前10分钟我才发现没有给我发邮件,想找hr或者面试官的邮箱和联系方式也找不到,最后只能等面试官打电话问我怎么没通过他的钉钉好友,我才知道要下载钉钉。那个时候以及迟到两分钟了,然后现场下钉钉,手机电脑扫码之类的,最后迟到十分钟才进去。虽然疯狂道歉,回答的也还行,但是泡了9天挂了。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2.突发状况影响面试体验&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;这个点就是,面试官可以有突发状况,但你不能有(扶额苦笑)。秋招面美团到店二面,首先是面试面着面着突然掉线,然后花了一点时间才上来;其次是会议室约的时间不够,写算法写到一半,后面的人来了,只好跟面试官说换个位置。最重要的,以上情况加上手撕没撕出来。。。挂了是我活该。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;大家还遇到过什么奇葩原因挂你的,可以评论分享一下,避免再次踩雷!#牛客创作赏金赛##24届软开秋招面试经验大赏##如何判断面试是否凉了#
点赞 评论 收藏
分享
11 69 评论
分享
牛客网
牛客企业服务