vivo 2022 届提前批数据挖掘 面试题 | 文末免费送书

star2017 1月前 ⋅ 78 阅读

第 1 题:输入一个数组,统计数组中有多少个数是 7 的倍数或者含有数字 7

判断一个数是否是 7 的倍数可以直接用取余的方法,判断一个数中是否含有数字 7,这里提供两种方法:一种是将数字转换成字符串,用 in 进行判断;另一种是将数字转换成字符串,用 find 方法,如果不包含会返回 -1。

代码如下:

2021 年 6 月 22 日,vivo 2022 届提前批数据挖掘 面试题

第 2 题:0-1 背包问题

题目描述: 给定物品的重量 weights=[1, 2, 5, 6, 7] ,对应的价值 values=[1, 6, 18, 22, 28] , 背包能装的最大重量为 capicity=11。问:我们用这个背包装什么物品能获得最大价值? 注意:每件物品只有一件。并且最终重量不能超过背包所能承载的重量。

本题解析参考:https://www.pianshen.com/article/2073277310/

分析:

首先,说明一下,本题采用动态规划, 因为问题的本身含最优子结构。 我们先给出转态转移方程:

2021 年 6 月 22 日,vivo 2022 届提前批数据挖掘 面试题

c(i, w)表示包容量为 w 时,考虑前 i 个物品所能获得的最大价值。。i 表示第 i 个物品,w 表示包容量;

**第―种情况︰**当前物品的重量超过了包的承载量,显然装不上,那它当前的最大价值就是原有包中的价值(不装这个物品时的最大价值)。



**第二种情况︰**当前物品的重量没有包承载量大。则说明当前这个物品可以装进去。那我们就得考虑了︰装这个物品价值大还是不装这个物品价值大?﹑从两种情况中选最大的。

2021 年 6 月 22 日,vivo 2022 届提前批数据挖掘 面试题
右下角的 40,就是我们所能获得的最大价值

接着,我们还需要输出获得最大价值的时候,我们拿了什么物品。

2021 年 6 月 22 日,vivo 2022 届提前批数据挖掘 面试题

从右下角的 40 开始,背包容量为 11,由于 40 与上一行的 40 相等,说明我们没有装第五个物品(因为当背包容量为 11,装第四个物品的时候,价值已经到达了 40)。紧接着,在背包容量为 11 时,对应第三个物品,最大价值是 25,所以,我们装了第四个物品。此时,我们的背包容量变为 W-w4 即:11-6=5。所以,对于第三个物品,我们直接考虑在背包容量为 5 的时候,可以看出价值是 18,考虑有没有装第三个?因为背包容量为 5 时,第二个物品所对应的最大价值为 7.所以我们装了第三个物品。接在:W 剩– w3= 5-5 =0。我们就可以得出背包中装了第三个和第四个物品。

代码实现:

2021 年 6 月 22 日,vivo 2022 届提前批数据挖掘 面试题

七月在线 AI 充电季,开宝箱活动正在进行中 ,200 本 AI 纸质书、机械键盘、硬盘、VIP 会员,来就送~

活动截止时间:7 月 31 日 15:00

活动链接:https://www.julyedu.com/active/treasure


本文地址:https://www.6aiq.com/article/1627406355143
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出

更多内容请访问:IT源点

相关文章推荐

全部评论: 0

    我有话说: