给定一个长度为 n 的数组,和一个目标组数 k ,请问能否把这个数组划分成 k 个非空子集,其和都相等。
数据范围: ,数组中的值都满足
public boolean candivide (ArrayList<Integer> nums, int k) { int sum = 0; for (Integer num : nums) { sum += num; } if (sum % k != 0) { return false; } int target = sum / k; int[] dp = new int[target + 1]; for (Integer num : nums) { if (num > target) { return false; } for (int j = target; j >= num; j--) { dp[j] = Math.max(dp[j], dp[j - num] + num); } //我题目理解的有问题,还是案例不够多呀 //nums = 2,6,3,10,8,4 k = 3时 不能凑出都是11的吧 但是还是返回的true if(dp[target] == target){ return true; } } return false; }这样子为什么能过呀,可是nums = 2,6,3,10,8,4 k = 3时 不能凑出都是11的吧 但是还是返回的true
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @param k int整型 # @return bool布尔型 # class Solution: """ 题目: https://www.nowcoder.com/practice/89ceab10d36140ce8f0d38c56e417f02?tpId=196&tqId=40516&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 算法: 1. 边界考虑: 设nums的长度为n,所有元素和为sum,最大值为maxNum,target = sum / k a)如果n < k,无法分割,返回False b)如果sum % k != 0,无法分割,返回False c) 如果maxNum > target,无法分割,返回False 2. 回溯函数dfs(k, target)表示当前剩余分割的序列数为k,当前分割区间剩余匹配的目标值为target 若k == 0,说明分割成功,返回True 若target == 0,需要分割的区间数-1,继续递归 枚举当前可选的有效元素,标记为已访问,继续递归;回溯 复杂度: 时间复杂度:??? 空间复杂度:O(n) """ def candivide(self, nums, k): # write code here def dfs(k, remain): if k == 0: # 分割序列成功 return True if remain == 0: # if dfs(k - 1, target): return True for i in range(n): if nums[i] > remain&nbs***bsp;visited[i]: # 当前元素大于剩余匹配值 或者 已被选取 continue visited[i] = True if dfs(k, remain - nums[i]): return True visited[i] = False return False n, Sum = len(nums), sum(nums) if n < k&nbs***bsp;Sum % k != 0: return False nums.sort(reverse=True) target = Sum / k if nums[0] > target: return False visited = [False] * n return dfs(k, target) if __name__ == "__main__": sol = Solution() # nums, k = [5, 1, 3, 2, 4], 3 nums, k = [5, 1, 4, 2, 3, 2], 3 res = sol.candivide(nums, k) print res
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param k int整型 * @return bool布尔型 */ #include <vector> bool candivide(vector<int>& nums, int k) { // write code here int sum=0; for(auto& n:nums) sum+=n; if(sum%k!=0) return false; sort(nums.rbegin(),nums.rend()); int target=sum/k; vector<int> buckets(k,target); return dfs(nums,buckets,0); } bool dfs(vector<int>& nums,vector<int>& buckets,int index){ if(index>=nums.size()) return true; for(int i=0;i<buckets.size();i++){ if(nums[index]>buckets[i]) continue; if(i>0&&buckets[i]==buckets[i-1]) continue; buckets[i]-=nums[index]; if(dfs(nums,buckets,index+1)) return true; buckets[i]+=nums[index]; } return false; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型ArrayList * @param k int整型 * @return bool布尔型 */ int originTarget = 0; public boolean candivide(ArrayList<Integer> nums, int k) { // write code here int max = 0; int sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums.get(i); if (nums.get(i) > max) { max = nums.get(i); } } if (sum % k != 0) { return false; } // 一个和是多少 originTarget = sum / k; // 最大的大于一个和,肯定不行 if (max > originTarget) { return false; } // visited数组,标记已访问元素 boolean[] visited = new boolean[nums.size()]; return cal(nums, originTarget, visited, k); } private boolean cal(ArrayList<Integer> nums, int target, boolean[] visited, int k) { if (k == 0) { return true; } if (target < 0) { return false; } else if (target == 0) { // 递归k-1,继续访问 return cal(nums, originTarget, visited, k - 1); } // target大于0,可以继续回溯 for (int i = 0; i < nums.size(); i++) { if (nums.get(i) > target) { continue; } if (visited[i]) { continue; } visited[i] = true; boolean cal = cal(nums, target - nums.get(i), visited, k); if (cal) { return true; } visited[i] = false; } return false; } }