当前位置: 首页 > news >正文

贵阳房地产网站建设网络推广的平台

贵阳房地产网站建设,网络推广的平台,绍兴网站建设哪家好,房产cms给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。 示例 1: 输入: nums [4, 3, 2, 3, 5, 2, 1], k 4 输出: True 说明: 有可能将其分成 4 个子集&#…

给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。

示例 1:

输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出: True
说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。
示例 2:

输入: nums = [1,2,3,4], k = 3
输出: false

提示:

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内

题解(回溯法)

题解参考自LFool
把集合中数字想象成球,把子集想象成桶
遍历数组计算总和sum,如果sum%k!=0直接返回false
否则令target=sum/k,计算每个桶内球的值之和是否等于sum/k

法一、球选择桶

在这里插入图片描述

dfs(nums,target,idx,bucket)

  1. 递归终止:idx越界,已经处理完所有球(idx==nums.length)
  2. 本层操作:bucket[i]+=nums[idx];
    剪枝:nums[idx]+bucket[i]>target
  3. 向下递归:如果有一个路径为true则返回true
    if(dfs(nums,idx+1,bucket,k,target)) return true;
  4. 回溯:
    bucket[i]-=nums[idx]
class Solution {public boolean canPartitionKSubsets(int[] nums, int k) {int sum = 0;for (int i = 0; i < nums.length; i++) sum += nums[i];if (sum % k != 0) return false;int target = sum / k;int[] bucket = new int[k];return dfs(nums,0,bucket,k,target);}private boolean dfs(int[] nums, int idx, int[] bucket, int k, int target){// 递归终止:idx越过数组边界,此时已经处理完所有球if (idx == nums.length) {// 判断现在桶中的球是否符合要求 -> 路径是否满足要求for (int i = 0; i < k; i++) {if (bucket[i] != target) return false;}return true;}//遍历所有桶寻找当前球可以放置的位置for(int i=0;i<k;i++){if(nums[idx]+bucket[i]>target) continue;//本层操作bucket[i]+=nums[idx];//向下递归:如果有一个路径为true则返回trueif(dfs(nums,idx+1,bucket,k,target)) return true;//回溯bucket[i]-=nums[idx];}return false;}
}

法二 桶选择球

class Solution {public boolean canPartitionKSubsets(int[] nums, int k) {int sum = 0;for (int i = 0; i < nums.length; i++) sum += nums[i];if (sum % k != 0) return false;int target = sum / k;int[] bucket = new int[k];return dfs(nums,0,bucket,k,target);}private boolean dfs(int[] nums, int idx, int[] bucket, int k, int target){// 递归终止:idx越过数组边界,此时已经处理完所有球if (idx == nums.length) {// 判断现在桶中的球是否符合要求 -> 路径是否满足要求for (int i = 0; i < k; i++) {if (bucket[i] != target) return false;}return true;}//遍历所有桶寻找当前球可以放置的位置for(int i=0;i<k;i++){if(nums[idx]+bucket[i]>target) continue;//本层操作bucket[i]+=nums[idx];//向下递归:如果有一个路径为true则返回trueif(dfs(nums,idx+1,bucket,k,target)) return true;//回溯bucket[i]-=nums[idx];}return false;}
}
收起
http://www.cadmedia.cn/news/1562.html

相关文章:

  • 北京论坛建站模板山东疫情最新情况
  • 徐州城建吧惠州seo按天付费
  • 河北沧州网站建设信阳百度推广公司电话
  • 网站后台管理系统教程杭州网站优化流程
  • 网站建设织梦怎么样站长工具seo综合查询
  • 微信网站怎么写品牌营销和市场营销的区别
  • 我要做网站推广防止恶意点击软件管用吗
  • 浙江省住房和城乡建设厅网站 文件网站制作需要多少钱
  • 成都网站建设好多科技新媒体运营需要哪些技能
  • 如何免费网站建设厦门seo排名优化
  • 烟台教育网站建设企业培训师
  • 设计企业网站哪家好推广员是干什么的
  • html源码网站下载之家自己怎么优化网站排名
  • 宁波建网站需要什么怎么建立一个属于自己的网站
  • 惠州网站制作询问薇大连网站开发公司
  • 带空间二字的韩国视频网站找竞价托管公司
  • 贵州建设监理网站培训通知栏什么时候网络推广
  • 购物网站需求分析报告seo点击软件排名优化
  • 天津市建设监理协会网站潍坊百度网站排名
  • 2020年网站建设笔记本今日关键词
  • 浦东网站建设哪家好百度渠道开户哪里找
  • 菏泽市建设局网站电话号码产品推广方案范文500字
  • 水碓子网站建设深圳seo优化公司排名
  • 网站做订购网游推广
  • 江桥网站建设百度网址查询
  • 容易被百度收录的网站抖音权重查询工具
  • 中央农村工作会议2020原文网站优化 福州
  • 公众号开发用什么语言优化师是做什么的
  • 可以做黄金期权的网站创建自己的网站
  • 全网加速器小果seo实战培训课程