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

[模版总结] - 集合划分类DFS模版

题目描述

给定一个数组,给定一个数字k, 问能不能讲数组内数等分成k份,使得每一个集合中数和相等。

题目链接

下面两道题问题及其类似,可作为同一类题目思考

Leetcode 698

Leetcode 473

题目思路

这道题是一道经典集合划分类问题,这类问题问询通常是判读是否将一个集合里面的所有元素划分到不同满足一定条件的子集合中。

集合划分也是思路和排列组合类似,可以想象成给球分桶的问题,这种类型的题目通常有两个思考方式:给每一个球选桶,给每一个桶选球

1. 给每一个球选桶:我们每一层递归的是球,每一个球每层递归可以选择进入一个桶,以此类推。

2. 给每一个桶选球:我们每一层递归的是桶,相当于每一层给某一个桶塞球,当塞满了就开始进入下一个桶。

这里的球就是指集合中的每一个数,而桶则是指等分的每一个子集合。

1. 暴力DFS

给每一个数选择一个子集合(超时)- 思路很简单,每一层递归是给当前数字选择一个子集合,如果当前子集合超过等分值那么跳过,直到所有数字选完子集合后,比较子集合中是否相等即可。

代码如下:

class Solution {int[] arr;int avg;public boolean canPartitionKSubsets(int[] nums, int k) {int sum = 0;for (int i: nums) sum+=i;avg = sum/k;if (avg*k!=sum) return false;arr = nums;return dfs(0, new int[k]);}private boolean dfs(int idx, int[] bkts) {if (idx==arr.length) {// 所有球找完桶,这时确定每个桶里面的数字for (int i: bkts) {if (i!=avg) return false;}return true;}// 开始选桶for (int i=0; i<bkts.length; i++) {if (bkts[i]+arr[idx] > avg) continue;// 桶里还能加bkts[i]+=arr[idx];if (dfs(idx+1, bkts)) return true;bkts[i]-=arr[idx]; // 组合类题目要回溯}return false;}
}

时间复杂度:O(k^N), 每一个数字有k个选择方式;空间复杂度:O(1),如果忽略递归占用的额外占空间。

给每一个子集合加入数(通过) - 相当于给每一个子集合选择一套数字,如果这个子集合塞满了,则继续下一个子集合直到所有的“桶”都塞完了“球”。思路和球选桶类似,但是需要开额外空间加入标记位来确认当前球被选过没有。

代码如下:

class Solution {int[] arr;int avg;public boolean canPartitionKSubsets(int[] nums, int k) {int sum = 0;for (int i: nums) sum+=i;avg = sum/k;if (avg*k!=sum) return false;arr = nums;return dfs(0, 0, new int[k], new boolean[nums.length]);}private boolean dfs(int idx, int bkt, int[] bkts, boolean[] visited) {if (bkt==bkts.length) {for (int i: bkts) {if (i!=avg) return false;}return true;}if (bkts[bkt]==avg) {// 目前选满了,换下一个桶return dfs(0, bkt+1, bkts, visited);}// 当前桶塞球for (int i=idx; i<arr.length; i++) {if (visited[i]) continue; //球用过了if (bkts[bkt]+arr[i]>avg) continue;// 当前桶可以塞visited[i] = true;bkts[bkt]+=arr[i];if (dfs(i+1, bkt, bkts, visited)) return true;visited[i] = false;bkts[bkt]-=arr[i]; // 组合问题回溯}return false;}
}

时间复杂度:O(k\times 2^N), 比球选桶的思路快了不少, 每一个桶在选球时有2^N个选法;空间复杂度:O(N),需要开额外空间进行去重。

2. DFS + 剪枝优化

给每一个数选择一个子集合(通过) - 不难理解,在递归寻找解的过程中,有很多重复解的情况,比如桶1选择2,3,4号球,桶2选择5,6号球,这种情况和桶1选择5,6号球,桶2选择2,3,4号球是重复情况。我们只是需要知道组合数而不需要知道排序。

代码如下:

class Solution {int[] arr;int avg;public boolean canPartitionKSubsets(int[] nums, int k) {int sum = 0;for (int i: nums) sum+=i;avg = sum/k;if (avg*k!=sum) return false;arr = nums;return dfs(0, new int[k]);}private boolean dfs(int idx, int[] bkts) {if (idx==arr.length) {// 所有球找完桶,这时确定每个桶里面的数字for (int i: bkts) {if (i!=avg) return false;}return true;}// 开始选桶for (int i=0; i<bkts.length; i++) {if (bkts[i]+arr[idx] > avg) continue;// 相邻两个桶值相同,那么选了上一个就不需要选这个if (i>0 && bkts[i-1]==bkts[i]) continue;// 桶里还能加bkts[i]+=arr[idx];if (dfs(idx+1, bkts)) return true;bkts[i]-=arr[idx]; // 组合类题目要回溯}return false;}
}

时间复杂度:最坏O(k^N), 具体复杂度很难估计;空间复杂度:O(1),如果忽略递归占用的额外占空间。

给每一个子集合加入数(通过) - 给桶塞球的思路我们可能会给两个桶塞入相同组合的球,那么可以设置一个HashMap记录之前的球选择,如果球组合被选过那么直接返回结果而不在往后计算。

注:这里还有一个优化是对boolean[] visited数组进行空间优化,我们可以直接用一个N位 int 来保存访问信息,但你需要熟悉下面几个位操作 - 非常巧妙

1. ((int >> i) & 1) == 1: 判断第i个球是否用过 等价于 visited[i]==true

2. int |= 1<<i: 给第i个球标记为访问 等价于 visited[i] = true

3. int ^= 1<<i: 给第i个球回溯为未访问 等价于 visited[i] = false

代码如下:

class Solution {int[] arr;int limit;HashMap<Integer, Boolean> paths = new HashMap<>();public boolean canPartitionKSubsets(int[] nums, int k) {int sum = 0;for (int i: nums) sum+=i;boolean[] visited = new boolean[nums.length];int avg = sum/k;if (avg*k!=sum) return false;arr = nums;limit = avg;// 骚套路剪枝通过int来记录每一个元素使用与否int used = 0;return dfs(used, 0, new int[k], 0);}private boolean dfs(int used, int bkt, int[] bkts, int start) {// 以k个桶的角度选择候选if (bkt==bkts.length) return true;if (bkts[bkt]==limit) {boolean res =  dfs(used, bkt+1, bkts, 0);paths.put(used, res);return res;} if (paths.containsKey(used)) {return paths.get(used);}for (int i=start; i<arr.length; i++) {if (((used>>i) & 1)==1) continue;if (bkts[bkt]+arr[i]>limit) continue;used |= 1 << i;bkts[bkt]+=arr[i];if (dfs(used, bkt, bkts, start+1)) return true;bkts[bkt]-=arr[i];used ^= 1 << i;}return false;}
}

时间复杂度:最坏O(k\times 2^N), 比球选桶的思路快了不少, 每一个桶在选球时有2^N个选法;空间复杂度:O(N),虽然省去了visited的空间,但是需要开额外空间进行路径去重。

相关文章:

[模版总结] - 集合划分类DFS模版

题目描述 给定一个数组&#xff0c;给定一个数字k, 问能不能讲数组内数等分成k份&#xff0c;使得每一个集合中数和相等。 题目链接 下面两道题问题及其类似&#xff0c;可作为同一类题目思考 Leetcode 698 Leetcode 473 题目思路 这道题是一道经典集合划分类问题&#…...

JavaScript中复制新的数组与原数组删除某个值——不影响新复制的数组的方法详解

系列文章目录 文章目录 系列文章目录前言一、使用slice()方法复制数组二、使用concat()方法复制数组三、使用扩展运算符(...)复制数组总结 前言 在JavaScript中&#xff0c;我们经常需要处理数组的复制和修改。本文将详细介绍如何在JavaScript中复制一个新的数组&#xff0c;并…...

easyui主表子表维护页面

easyui主表子表维护页面 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>Title</title><!-- <#include "common.html"/> --><link rel"stylesheet" type&quo…...

k8s exam

Pause 容器是 Pod 中的第一个启动的容器&#xff0c;其他所有的用户容器都是其子进程当 Pod 被从节点中删除时&#xff0c;与之关联的 emptyDir 中的数据也将被永久删除。持久存储用PV&#xff0c;PVCService 资源定义了如何访问应用&#xff0c;但实际的网络流量管理和路由是由…...

C#,中国福利彩票《刮刮乐》的数学算法(02)——时来运转

1 中国福利彩票 中国福利彩票始于1987年7月27日&#xff0c;以“团结各界热心社会福利事业的人士&#xff0c;发扬社会主义人道主义精神&#xff0c;筹集社会福利资金&#xff0c;兴办残疾人、老年人、孤儿福利事业和帮助有困难的人”、即“扶老、助残、救孤、济困”为宗旨。随…...

我的观影记录表【个人向】

目录 前言电影评分标准闪电侠&#xff08;2023&#xff09;银河护卫队3&#xff08;2023&#xff09; 前言 这里是我本人的观影记录&#xff0c;这个想法2年前就有了&#xff0c;但是一直比较懒&#xff0c;现在&#xff08;上班摸鱼&#xff09;准备重新开始&#xff0c;评价…...

网络安全策略应包含哪些?

网络安全策略是保护组织免受网络威胁的关键措施。良好的网络安全策略可以确保数据和系统的保密性、完整性和可用性。以下是一个典型的网络安全策略应包含的几个重要方面&#xff1a; 1. 强化密码策略&#xff1a;采用强密码&#xff0c;要求定期更换密码&#xff0c;并使用多因…...

【Git】Git GitHub

1. Git1.1 Git基本操作1.2 Git版本回退1.3 Git分支操作 2. Git 配合GitHub2.1 生成密钥2.2 GitHub添加公钥2.3 Git连接GitHub2.4 本地仓库关联远程仓库2.5 本地代码push远程仓库2.6 本地clone远程仓库2.7 本地fetch和pull 1. Git 1.1 Git基本操作 touch test.py 工作区创建文…...

[STL]详解list模拟实现

[STL]list模拟实现 文章目录 [STL]list模拟实现1. 整体结构总览2. 成员变量解析3. 默认成员函数构造函数1迭代器区间构造函数拷贝构造函数赋值运算符重载析构函数 4. 迭代器及相关函数迭代器整体结构总览迭代器的模拟实现begin函数和end函数begin函数和end函数const版本 5. 数据…...

C和C++的区别与联系

C语言&#xff08;C&#xff09;和C语言&#xff08;C&#xff09;是两种编程语言&#xff0c;它们之间有许多区别和联系。以下是它们之间的主要区别和联系&#xff1a; 区别&#xff1a; 历史和起源&#xff1a; C语言是由Dennis Ritchie于20世纪70年代初在贝尔实验室开发的。…...

springboot通过接口执行本地shell脚本

首先创建springboot项目 shell脚本 #!/bin/shecho Hello World&#xff01;然后编写执行shell脚本的util类 import java.io.BufferedInputStream; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List;pub…...

工欲善其事必先利其器,IT工作电脑更要维护好

目录 一&#xff1a;电脑的组成 二&#xff1a;维护措施 三&#xff1a;助力记忆 一&#xff1a;电脑的组成 当谈到电脑主机时&#xff0c;我们通常指的是电脑的中央处理器(CPU)、内存、主板、电源、硬盘、显卡、声卡、网卡等核心部件组成的整体。这些部件共同协作&#xff…...

移动端个人中心UI设计

效果图 源码如下 页面设计 <template><div class"container"><!-- 顶部用户信息 start--><div class"header"><div class"user-info"><van-image class"user-img" round width"70" :sr…...

开发接口,你需要先搞懂这些概念!

SOA Service Oriented Ambiguity 即面向服务架构&#xff0c; 简称SOA。 SOA的提出是在企业计算领域&#xff0c;就是要将紧耦合的系统&#xff0c;划分为面向业务的&#xff0c;粗粒度&#xff0c;松耦合&#xff0c;无状态的服务。服务发布出来供其他服务调用&#xff0c;一…...

zookeeper常用命令

zkClient 简介 zkClient是简易的客户端程序 进入zkClient 在bin目录下输入zkCli.sh 节点命令 增 create 路径 数据 -s&#xff1a;顺序节点 -e&#xff1a;临时节点 默认情况下&#xff0c;不添加-s或者-e参数的&#xff0c;创建的是持久节点改 set 路径 数据 版本…...

亚马逊水基灭火器UL8测试报告ISO17025实验室办理

在跨境电商平台上销售的境外电商&#xff0c;在美国市场中需要提供相关的安全规范报告。其中&#xff0c;美国相关部门要求&#xff0c;如果商家未能提交UL&#xff08;Underwriters Laboratories&#xff09;标准的检测报告&#xff0c;将会被责令停止销售。而为了在亚马逊、T…...

Shell学习脚本-if多分支结构

语法&#xff1a; if 条件then指令集 else指令集 fi特殊写法&#xff1a; if [ -f "$file1" ]; then echo 1; else echo 0; fi 相当于&#xff1a; [ -f "$file1" ] && echo 1 || echo 0 多分支结构&#xff1a; if 条件then指令 elif 条件th…...

[SQL挖掘机] - 窗口函数 - lead

介绍: lead() 是一种常用的窗口函数&#xff0c;它用于获取某一行之后的行的值。它可以用来在结果集中的当前行后面访问指定列的值。 用法: lead() 函数的语法如下&#xff1a; lead(列名, 偏移量, 默认值) over (partition by 列名1, 列名2, ... order by 列名 [asc|desc]…...

PyTorch Lightning教程四:超参数的使用

如果需要和命令行接口进行交互&#xff0c;可以使用Python中的argparse包&#xff0c;快捷方便&#xff0c;对于Lightning而言&#xff0c;可以利用它&#xff0c;在命令行窗口中&#xff0c;直接配置超参数等操作&#xff0c;但也可以使用LightningCLI的方法&#xff0c;更加轻…...

2023 蓝桥杯真题B组 C/C++

https://www.dotcpp.com/oj/train/1089/ 题目 3150: 蓝桥杯2023年第十四届省赛真题-冶炼金属 题目描述 小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V&#xff0c;V 是一个正整数&#xff0c;这意味着消耗 V 个普通金 属 O…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...