记一道字节面试题:小于n的最大数

nums = [5,6,8,7]
target = 500
nums.sort()
target = str(target)
def search(nums, target):
    low, high = 0, len(nums) - 1 
    while low < high:
        mid = low + (high - low + 1) // 2
        if nums[mid] <= target:
            low = mid
        else:
            high = mid - 1
    return nums[low] if nums[low] <= target else -1
def getMaxNumbers(nums, target):
    res, ans, flag = [], 0, False
    for i in range(len(target)):
        if flag:
            res.append(nums[-1])
            continue
        subtarget = target[i]
        temp = search(nums, int(subtarget))
        if temp == -1:
            if i == 0:
                if len(target) == 1:
                    return 0
                else:
                    return str(nums[-1]) * (len(target) - 1)
            else:
                index = i - 1
                while temp == -1 and index >= 0:
                    temp = search(nums, int(target[index]) - 1)
                    index -= 1
                if temp == -1:
                    return str(nums[-1]) * (len(target) - 1)
                res[index + 1] = temp
                for j in range(index + 2, i):
                    res[j] = nums[-1]
                res.append(nums[-1])
                flag = True
        else:
            if temp == int(subtarget):
                res.append(temp)
            else:
                res.append(temp)
                flag = True
    for i in range(len(res)):
        ans = ans * 10 + res[i]
    return ans
print(getMaxNumbers(nums, target))

问题描述:给一个数组nums=[5,4,8,2],给一个n=5416, 让你从nums中选出一些元素,使得组成的数字是小于n的最大数,比如这个例子应该返回5288,当时没想出来,让面试官换了一道题,事后顺着一些大佬的思路写了下,感觉贪心加二分这个思路比较接近正确答案,有没有人看下这个方法行不行
 

#字节跳动#
全部评论
void maxNumber(const vector<int> &v, int num) { vector<int> arr, ans; int minChoose=10, maxChoose=0; bool exist[10]; for(int x:v) { exist[x]= true; minChoose = min(minChoose, x); //可选择的最小值 maxChoose = max(maxChoose, x); //可选择的最大值 } while(num) //将num每一位存到数组 { arr.push_back(num%10); num /= 10; } reverse(arr.begin(), arr.end()); //答案应尽可能和num位数相同,若位数相同无解,则答案减少一位且每位取最大值,如100 {2,3,4}的答案为44 for(int i=0;i<arr.size>= minChoose ? arr[i] : arr[i] - 1); while (j >= 0 && !exist[j]) j--; if(j<0) //同位数无解,退而求次降低解的位数 { ans.clear(); for (int k = 0; k < arr.size() - 1; ++k) ans.push_back(maxChoose); break; } else if(j!=arr[i]) //当前位取了小于原数同位的值,则解确定,后面每一位都可以取最大值 { ans.push_back(j); while (ans.size()</arr.size></int></int>
1 回复 分享
发布于 2022-05-03 16:16
实际上 数只有十个 那我们贪心就好了 我们首先匹配这个数 如果每一位都在这个数组中存在 就修改最小的一位 如果不 就把最高的不能匹配的位之后变成数组中最大值 这一位找一个小的数代替
5 回复 分享
发布于 2022-05-02 00:28
代码考虑不周全,好几次跑出来的值和taget相等
1 回复 分享
发布于 2022-05-26 00:05
我也是贪心➕二分的解法,前两天我朋友问我的,一会我贴上来,不保证没有漏洞,但是目前的用例是都过了
1 回复 分享
发布于 2022-05-02 10:28
这个代码有点问题呀,没有考虑到最后如果全部都是匹配成等于的情况,例如nums = [2], target = 22的情况。
点赞 回复 分享
发布于 2024-10-13 14:54 福建
数位dp?
点赞 回复 分享
发布于 2024-08-28 23:18 浙江
有人知道这道题的oj链接吗,想测试下
点赞 回复 分享
发布于 2022-08-08 21:54
你这个5416咋输出888,我尝试了一下
点赞 回复 分享
发布于 2022-07-23 17:12
题目规模不大,2**31 也就 10 个数字,dfs+剪枝方法 虽然不是最优不过也可以过给的用例
点赞 回复 分享
发布于 2022-05-25 17:00
今天我也问的这道题,和他说的是贪心+二分,然后面试官说应该就是最优的
点赞 回复 分享
发布于 2022-05-06 15:58
重新编辑了下,有几个边界情况考虑错了
点赞 回复 分享
发布于 2022-05-02 16:34
我擦,长的
点赞 回复 分享
发布于 2022-05-02 00:15

相关推荐

04-26 23:17
已编辑
门头沟学院 C++
#牛客AI配图神器#不鸣科技(服务器开发实习生)一面(40分钟)1.父类指针怎么调用子类的虚函数?2.析构函数需要是虚函数吗?3.父类指针析构子类对象会调用父类的析构吗?4.父类指针析构子类对象时,子类string成员、子类、父类的析构顺序?(没理解清楚,回答不是很好,应该先析构string、子类的析构、父类的析构)5.vector扩容的机制?6.vector拷贝行为可以怎么优化?(移动语义)7.如何在map中遍历删除指定的元素?8.给你一系列的元素,每个元素有一个权重,怎么让取到的元素概率和元素的权重呈比例?(没回答出来,加权随机选择,前缀和+二分查找)9.浮点数如何判断相等?(不知道,浮点数近似存储,因此不能直接==,fabs(a&nbsp;-&nbsp;b)&nbsp;10.手撕一个stack,提供push、pop、top、getMin接口反问:1.技术栈(C++和Lua)2.什么时候出结果二面(45分钟)1.面试官介绍了下面试主要内容,说后面还会有业务三面2.子类、父类、子类的成员类,它们的构造顺序?3.类成员的初始化顺序?4.为什么按照声明顺序而不是初始化列表顺序?从设计者的角度考虑为什么这么设计(开放性问题,面试官对我的回答不太满意,最后给提示,函数重载是一个原因)5.类中的成员类实例存储在栈上还是在堆上?(分情况)6.基类的析构函数为什么建议是虚函数?7.如何判断浮点数是否相等?8.基于内存对齐规则,如何设计一个类?9.在map中如何在遍历过程中删除元素?10.说说条件断点和数据断点?还有的忘了反问:1.不足的地方(思维能力要提高)后续:五分钟后约三面(以为是HR面,结果被告知三面也是技术面)三面(25min)1.问了下感兴趣的技术方向(操作系统、数据库)好那就聊聊操作系统2.进程调度算法有哪些?3.进程和线程的区别?4.线程会共享进程的哪些资源?5.线程栈空间?6.说一说内联函数?7.函数调用的步骤?反问:1.不足之处&nbsp;2.实习生培养方案后续:三面挂了三面那么短就觉得不太对劲果然是g了timeline:4.15&nbsp;投递4.18&nbsp;一面4.23&nbsp;二面4.24&nbsp;三面4.25&nbsp;感谢信#牛客解忧铺##牛客在线求职答疑中心##牛客创作赏金赛##牛客激励计划#
点赞 评论 收藏
分享
评论
7
64
分享

创作者周榜

更多
牛客网
牛客企业服务