【每日算法Day 101】字节跳动 AI Lab 精选面试编程题

【每日算法Day 101】字节跳动 AI Lab 精选面试编程题

今天字节三面结束了，超越妹妹保佑我通过吧！今天更新两道同学之前面试 AI Lab 时遇到的题。

0-1 背包问题（浮点数）

0-1 背包问题，一共 ​​n < 20​​​ 个物品，每个物品价格 ​​p[i]​​​ （浮点数），重量 ​​w[i]​​​ （浮点数），背包容量 ​​M​​ （浮点数）。求最大能装的价值是多少？

输入：20 678.9123.56 51.5631.45 23.5662.54 45.6215.32 42.2312.32 65.3265.12 32.4515.65 45.7862.15 98.3232.15 45.6215.44 95.3245.65 99.4532.15 22.4823.56 51.5631.45 23.5662.54 45.6215.32 42.2312.32 65.3265.12 32.4515.65 45.7862.15 98.32输出：1050.07

题解

因为这里全部都是浮点数，所以没有办法直接用普通的动态规划来做，这里我提供几个思路。

方法1：如果小数点只有两位的话，很简单，所有数字统一乘以 100 ，那么就都变成整数了。然后就可以直接用普通的 0-1 背包方法来做。

方法2：

因为 ​​n < 20​​ ，所以直接二进制枚举所有物品可能，然后取出重量小于背包容量，且价格最高的那一种就行了。时间复杂度

，勉强可以接受。

方法3：将 ​​​n​​​ 个物品平均分成两份，对每一份做二进制枚举，然后保存所有可能的总重量和对应的总价格。保存在两个数组中，记为 ​​a​​​ 和 ​​b​​ ，分别表示两份的所有可能情况。

预处理出 ​​b​​​ 中重量小于等于 ​​b[j].w​​​ 的最大价格，保存在 ​​maxp[j]​​ 中。

分别按照 ​​w​​​ 排序，然后用双指针，从重量小的开始遍历 ​​a​​​ 中每个元素 ​​a[i]​​​ ，在 ​​b​​​ 中找出重量最高的那个满足 ​​a[i].w + b[j].w​​​ 不超过背包容量的 ​​j​​ 。

然后 ​​i​​​ 移动到 ​​i+1​​​ ，也就是重量增加了，那么 ​​j​​​ 只能减小了，直到减小到 ​​a[i].w + b[j].w​​​ 再次不超过背包容量。然后直接取预处理好的 ​​maxp[j]+a[i].p​​ 和最优答案比较就行了。

最终时间复杂度是

，相比上面直接二进制枚举所有情况，大大降低了呀。

代码

#include using namespace std;typedef long long ll;const int mod = 1e9 + 7;const int N = 22;struct node { double w, p; bool operator < (const node& rhs) const { return w < rhs.w; }} a[1< w(n, 0), p(n, 0); for (int i = 0; i < n; ++i) { scanf("%lf%lf", &w[i], &p[i]); } printf("%f\n", tmp); int ca = 0, cb = 0; for (int s = 0; s < (1<<(n/2)); ++s) { double tot_w = 0, tot_p = 0; for (int i = 0; i < n/2; ++i) { if (s&(1< M) break; } } if (tot_w <= M) { a[ca].w = tot_w; a[ca].p = tot_p; ca++; } } for (int s = 0; s < (1<<(n-n/2)); ++s) { double tot_w = 0, tot_p = 0; for (int i = 0; i < n-n/2; ++i) { if (s&(1< M) break; } } if (tot_w <= M) { b[cb].w = tot_w; b[cb].p = tot_p; cb++; } } sort(a, a+ca); sort(b, b+cb); vector maxp(cb, 0); maxp[0] = b[0].p; for (int i = 1; i < cb; ++i) { maxp[i] = max(maxp[i-1], b[i].p); } int j = cb-1; double res = 0; for (int i = 0; i < ca; ++i) { while (j >= 0 && a[i].w+b[j].w > M) --j; if (j < 0) break; res = max(res, a[i].p+maxp[j]); } printf("%f\n", res); return 0;}

最小长度子数组

给一个正数数组，找出最小长度连续子数组，其和大于等于 ​​m​​。

题解

这题还是用双指针，首先用 ​​i​​​ 遍历每一个位置，然后维护 ​​a[j] ~ a[i]​​​ 之间的元素和。如果发现和大于等于 ​​m​​​ ，那就更新最小长度，同时增大 ​​j​​​ 直到区间和小于 ​​m​​ 。最终时间复杂度是

的。

代码

#include using namespace std;int main() { int n, m; scanf("%d%d", &n, &m); vector a(n, 0); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } int j = 0, sum = 0, res = INT_MAX; for (int i = 0; i < n; ++i) { sum += a[i]; while (sum >= m) { res = min(res, i-j+1); sum -= a[j++]; } } printf("%d\n", res); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。