[模版总结] - 集合划分类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;}
}
时间复杂度:, 每一个数字有k个选择方式;空间复杂度:
,如果忽略递归占用的额外占空间。
给每一个子集合加入数(通过) - 相当于给每一个子集合选择一套数字,如果这个子集合塞满了,则继续下一个子集合直到所有的“桶”都塞完了“球”。思路和球选桶类似,但是需要开额外空间加入标记位来确认当前球被选过没有。
代码如下:
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;}
}
时间复杂度:, 比球选桶的思路快了不少, 每一个桶在选球时有
个选法;空间复杂度:
,需要开额外空间进行去重。
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;}
}
时间复杂度:最坏, 具体复杂度很难估计;空间复杂度:
,如果忽略递归占用的额外占空间。
给每一个子集合加入数(通过) - 给桶塞球的思路我们可能会给两个桶塞入相同组合的球,那么可以设置一个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;}
}
时间复杂度:最坏, 比球选桶的思路快了不少, 每一个桶在选球时有
个选法;空间复杂度:
,虽然省去了visited的空间,但是需要开额外空间进行路径去重。
相关文章:
[模版总结] - 集合划分类DFS模版
题目描述 给定一个数组,给定一个数字k, 问能不能讲数组内数等分成k份,使得每一个集合中数和相等。 题目链接 下面两道题问题及其类似,可作为同一类题目思考 Leetcode 698 Leetcode 473 题目思路 这道题是一道经典集合划分类问题&#…...
JavaScript中复制新的数组与原数组删除某个值——不影响新复制的数组的方法详解
系列文章目录 文章目录 系列文章目录前言一、使用slice()方法复制数组二、使用concat()方法复制数组三、使用扩展运算符(...)复制数组总结 前言 在JavaScript中,我们经常需要处理数组的复制和修改。本文将详细介绍如何在JavaScript中复制一个新的数组,并…...
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 中的第一个启动的容器,其他所有的用户容器都是其子进程当 Pod 被从节点中删除时,与之关联的 emptyDir 中的数据也将被永久删除。持久存储用PV,PVCService 资源定义了如何访问应用,但实际的网络流量管理和路由是由…...
C#,中国福利彩票《刮刮乐》的数学算法(02)——时来运转
1 中国福利彩票 中国福利彩票始于1987年7月27日,以“团结各界热心社会福利事业的人士,发扬社会主义人道主义精神,筹集社会福利资金,兴办残疾人、老年人、孤儿福利事业和帮助有困难的人”、即“扶老、助残、救孤、济困”为宗旨。随…...
我的观影记录表【个人向】
目录 前言电影评分标准闪电侠(2023)银河护卫队3(2023) 前言 这里是我本人的观影记录,这个想法2年前就有了,但是一直比较懒,现在(上班摸鱼)准备重新开始,评价…...
网络安全策略应包含哪些?
网络安全策略是保护组织免受网络威胁的关键措施。良好的网络安全策略可以确保数据和系统的保密性、完整性和可用性。以下是一个典型的网络安全策略应包含的几个重要方面: 1. 强化密码策略:采用强密码,要求定期更换密码,并使用多因…...
【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语言(C)和C语言(C)是两种编程语言,它们之间有许多区别和联系。以下是它们之间的主要区别和联系: 区别: 历史和起源: C语言是由Dennis Ritchie于20世纪70年代初在贝尔实验室开发的。…...
springboot通过接口执行本地shell脚本
首先创建springboot项目 shell脚本 #!/bin/shecho Hello World!然后编写执行shell脚本的util类 import java.io.BufferedInputStream; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List;pub…...
工欲善其事必先利其器,IT工作电脑更要维护好
目录 一:电脑的组成 二:维护措施 三:助力记忆 一:电脑的组成 当谈到电脑主机时,我们通常指的是电脑的中央处理器(CPU)、内存、主板、电源、硬盘、显卡、声卡、网卡等核心部件组成的整体。这些部件共同协作ÿ…...
移动端个人中心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 即面向服务架构, 简称SOA。 SOA的提出是在企业计算领域,就是要将紧耦合的系统,划分为面向业务的,粗粒度,松耦合,无状态的服务。服务发布出来供其他服务调用,一…...
zookeeper常用命令
zkClient 简介 zkClient是简易的客户端程序 进入zkClient 在bin目录下输入zkCli.sh 节点命令 增 create 路径 数据 -s:顺序节点 -e:临时节点 默认情况下,不添加-s或者-e参数的,创建的是持久节点改 set 路径 数据 版本…...
亚马逊水基灭火器UL8测试报告ISO17025实验室办理
在跨境电商平台上销售的境外电商,在美国市场中需要提供相关的安全规范报告。其中,美国相关部门要求,如果商家未能提交UL(Underwriters Laboratories)标准的检测报告,将会被责令停止销售。而为了在亚马逊、T…...
Shell学习脚本-if多分支结构
语法: if 条件then指令集 else指令集 fi特殊写法: if [ -f "$file1" ]; then echo 1; else echo 0; fi 相当于: [ -f "$file1" ] && echo 1 || echo 0 多分支结构: if 条件then指令 elif 条件th…...
[SQL挖掘机] - 窗口函数 - lead
介绍: lead() 是一种常用的窗口函数,它用于获取某一行之后的行的值。它可以用来在结果集中的当前行后面访问指定列的值。 用法: lead() 函数的语法如下: lead(列名, 偏移量, 默认值) over (partition by 列名1, 列名2, ... order by 列名 [asc|desc]…...
PyTorch Lightning教程四:超参数的使用
如果需要和命令行接口进行交互,可以使用Python中的argparse包,快捷方便,对于Lightning而言,可以利用它,在命令行窗口中,直接配置超参数等操作,但也可以使用LightningCLI的方法,更加轻…...
2023 蓝桥杯真题B组 C/C++
https://www.dotcpp.com/oj/train/1089/ 题目 3150: 蓝桥杯2023年第十四届省赛真题-冶炼金属 题目描述 小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V,V 是一个正整数,这意味着消耗 V 个普通金 属 O…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
