java - 带有一些额外条件的子集和算法的复杂性
问题描述
- 必须包括所有 5 的倍数。
- 如果有一个 1 后跟一个 5 的倍数,那么它一定不能包含在内。
有一个
标准溶液
/*
* Given an array of ints, is it possible to choose a group of some of the ints,
* such that the group sums to the given target with these additional constraints:
* all multiples of 5 in the array must be included in the group.
* If the value immediately following a multiple of 5 is 1,
* it must not be chosen. (No loops needed.)
*
* groupSum5(0, {2, 5, 10, 4}, 19) → true
* groupSum5(0, {2, 5, 10, 4}, 17) → true
* groupSum5(0, {2, 5, 10, 4}, 12) → false
* groupSum5(0, {3, 5, 1}, 9) → false
* groupSum5(0, {2, 5, 4, 10}, 12) → false
* groupSum5(0, {3, 5, 1}, 5) → true
* groupSum5(0, {1, 3, 5}, 5) → true
* groupSum5(0, {1}, 1) → true
*/
public boolean groupSum5(int start, int[] nums, int target) {
if (start >= nums.length) return (target == 0);
if (nums[start] % 5 == 0) {
if (start < nums.length - 1 && nums[start + 1] == 1){
return groupSum5(start + 2, nums, target - nums[start]);
}
return groupSum5(start + 1, nums, target- nums[start]);
}
return groupSum5(start + 1, nums, target - nums[start])
|| groupSum5(start + 1, nums, target);
}
我的方法
public boolean groupSum5(int start, int[] nums, int target) {
final int len = nums.length;
if (start == len) {
return target == 0;
}
if (start > 0 && nums[start] == 1 && (nums[start- 1] % 5) == 0 ) {
return groupSum5(start + 1, nums, target);
}
if (groupSum5(start + 1, nums, target - nums[start])) {
return true;
} if ((nums[start] % 5) != 0
& groupSum5(start + 1, nums, target)) {
return true;
}
return false;
}
就时间复杂度而言,以上 2 个中哪一个更好?
如果我没有弄错标准解决方案或第一个解决方案的复杂性大于指数(3^n)?我想如果我们考虑递归调用,说复杂度是(4^n)是否正确?
解决方案
我认为你的代码是错误的。groupSum5(0, [0, 1, 1], 1) 使用您的代码返回 false,因为两个 1 都被排除在外。在最坏的情况下,正确的 groupSum5 和你的都是 O(2^n) 。尽管 groupSum5 在第一段代码中以文本形式出现了 4 次,但其中只有 2 次调用可以在单个堆栈帧中发生
推荐阅读
- laravel - Laravel mix 压缩插件
- azure - 在本地开发时,如何将 @azure/identity 与来自“az login”而不是服务帐户的 DefaultCredentials 一起使用?
- ruby - 为什么我们在 Ruby 中有 0.0 和 -0.0?
- api - 是否可以让 API 与 REST 和 gRPC 一起使用?
- node.js - Graphdb.js node.js 一个 server.repository 通过 Rest APIs 连接多个查询
- angular - Angular 无法匹配任何路由。网址段
- python - 如果用户帐户在登录期间未激活,如何显示一些消息?
- html - 在 Firefox 上,溢出:隐藏有效,但滚动条和空格仍然存在
- python - 如何组合通过交叉验证找到的深度学习模型?
- sql - 使用 Group By 在 Access 查询中运行 sum