9.3 贝壳笔试 Java后端

100 100 100 40

第三题用例通过了，一提交0

我一直觉得第三题可以用贪心，本地IDE用例也能过，一提交直接百分之0😫

前三题全a，第四题骗了20%

害 就a了两题，第三题调了一个多小时

第三题换了三种思路就是通过不了，最后一种10%。思路是backtrack穷举然后选最优解，递归时保留一个track剪枝。真的心力憔悴。用例都能过，自己又试了一些，一提交就是0%。结果最后一种方法删掉track直接在原数列上修改（每次删除一个）还能通过10%，这就让我很迷惑了。。 void backtrack(vector<int>& nums, int remain, int val, int thres, int k) { //      // Base case     if (remain <= 0) {         res = max(val, res);         return ;     }     for (int i = 0; i < nums.size(); i++) {         int value = nums[i];         nums.erase(nums.begin() + i);         if (value > thres) {             backtrack(nums, remain - k - 1, val + value, thres, k);         } else {             backtrack(nums, remain - 1, val + value, thres, k);         }         nums.insert(nums.begin() + i, value);     } }

上次笔试A了2.2貌似没过，这次A了2...估计又没了hhh

有人用dp,但是我的做法是先把<=m的物品全取了，然后因为总共拿n次，所以在<=m的物品中填充价值=0的物品,使其总共有n个，然后我从大到小拿>m的物品去替换k个最小的<=m的物品，但是没a掉，不知道思路哪有问题。

第三题a的代码

全排列跑到90超时了🤣

考试的时候第三题没写，事后理了半天的逻辑，写了一个python的代码，有大佬帮忙看一下正确了没

求第三题AC代码

前两道20分钟，第三题写完在ide过了case看时间还有一个小时二十分钟，到了最后13分钟我还在第三题。。。。。第三题暴力dfs超时0%，求第三题代码

第三题贪心，第四题一点思路都没有。

第三题DP没爆，但是一直都是50%，看了四十分钟没找到啥别的改进方案。  k++;         for (int i = 1; i <= n; i++) {             if (values[i - 1] <= m) {                 for (int j = 1; j <= n; j++) {                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + values[i - 1]);                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);                 }             } else {                 for (int j = 1; j < k; j++) {                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);                 }                 for (int j = k; j <= n; j++) {                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + values[i - 1]);                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);                 }                 for (int j = k - 1; j > 0; j--) {                     dp[i][n] = Math.max(dp[i][n], dp[i - 1][n - j] + values[i - 1]);                 }                 dp[i][n] = Math.max(dp[i][n], dp[i - 1][n]);             }         } 有没有做出来的老哥给讲讲思路的。

做两题有面试机会吗😭

这个做几题能过阿？

有大佬展示一下各个题的代码吗

看来一大半人都是做一半。。。我前两题ac，后面一个多小时疯狂调第三题。。 然后疯狂数组越界，看了评论区感觉我思路是对的，唉😔

第三题dp或者回溯不能做吗，有没有大哥解释一下