2023-08-19 20:57 门头沟学院 前端工程师
关注
美团笔试
给定a数组，求b数组的数量，规则为：
1. 对于任意的i， ai != bi
2. a数组的和等于b数组的和
各位大佬的思路是啥？
1. 对于任意的i， ai != bi
2. a数组的和等于b数组的和
各位大佬的思路是啥？
全部评论
感谢信收集桶
西安电子科技大学 C++
dfs3.33
三过大厂而不入
哈尔滨工业大学（深圳） Java
用的dp，测试用例都过了，一交0%😡
electronic
门头沟学院 前端工程师
递归做半天，0%
冬冬瓜皮
蚌埠坦克学院 测试开发
背包问题
xxx_yy
浙江科技学院 C++
乱写了一个记搜就过了
想到了是01背包问题，但还是用dfs做了，js简单优化了下3.33
在摸鱼的牛肉丸很讲原则
门头沟学院 C++
回溯3.33，超时
一个善良且老实的人
门头沟学院 Java
dp[i][j]：表示构建新数组来到i位置 此时数组的和还剩余j
==>dp[数组长度][0] = 1:
==>第一列，最后一行答案已知
==>需要知道：dp[0][sum]的值
==>dp[i][j] = dp[i + 1][j - k]的和 其中j-k>=0
但是我只能过6%，不知道哪的问题
我的代码，看看佬能看出来我哪有问题
// Scanner sc = new Scanner(System.in);
// int n = sc.nextInt();
// int[] resource = new int[n];
// for (int i = 0; i < n; i++) {
// resource[i] = sc.nextInt();
// }
// int sum = Arrays.stream(resource).sum();
// long[][] dp = new long[n + 1][sum + 1];
// dp[n][0] = 1;
// for(int i = n - 1;i >= 0;i--){
// for(int j = 1;j < dp[0].length;j++){
// long res = 0;
// for(int k = 1;j - k >= 0;k++){
// if(resource[i] == k)
// continue;
// res = res + dp[i + 1][j - k] % 1000000007;
// }
// res += dp[i + 1][j - 1];
// dp[i][j] = res;
// }
// }
// System.out.println(dp[0][sum]);
virtualx
中国科学技术大学 C++
维护长度为sum的数组做dp，dp[i]表示当前用i来满足自当前元素之后的所有元素的满足要求的数量，然后想办法从后到前遍历所有元素维护这个数组，最后输出dp[sum]
wuuuummm
门头沟学院 C++
蹲
小达qwq
中国科学技术大学 C++
dp背包，3ms 400KB
小牛414
西安交通大学 C++
我用的递归 测试用例都过了 提交为0
待失业选手
东南大学 Java
直接记忆化搜索就可以过
招聘爱好
吉林大学 引擎开发
这个线性dp,和京东的第二题一样
惜_叩
雅安职业技术学院 C++
超时了，原本想把递归换成栈的，时间不够了
相关推荐
07-29 16:49
门头沟学院 嵌入式软件开发 
RazerYang：其实也是幸存者偏差，你只关注草台班子的部分，所以觉得世界都是草台班子。实际上你每天能安全地从床上醒来，有稳定的天然气、自来水和电力供应，能让你吃上热乎的饭菜，能收到持续稳定的信号去刷手机，花几块钱就能坐地铁从城市的一端快速移动到另一端，花几百块就能在一天之内安全穿越整个国家，这都不是一个草台班子能实现的。燃气、水利、电力、通信、公交、民航，还有最重要的公安和国防，这些都不是草台班子能做的，有无数普通人构筑了你生活的方方面面，而你也将加入他们。 点赞 评论 收藏
分享