【LeetCode】升级打怪之路 Day 26:回溯算法 — 集合划分问题

今日题目:

  • 698. 划分为k个相等的子集 | LeetCode
  • 473. 火柴拼正方形 | LeetCode

参考文章:

  • 经典回溯算法:集合划分问题

目录

      • LC 698. 划分为k个相等的子集 【classic,有难度】
        • 数据预处理:计算 target
        • 基本回溯
        • 优化 1:跳过某些 bucket 的选择
        • 优化 2:事先对 nums 排序
        • 最终代码事先
      • LC 473. 火柴拼正方形 【练习】

集合划分问题是使用回溯算法来解决的一类问题。这类问题的抽象描述是:给定 n 个数,让我们划分成 k 组,使得这 k 组的每组数的 sum 一样大。这类问题也有固定的套路思路,学会就行了。

LC 698. 划分为k个相等的子集 【classic,有难度】

698. 划分为k个相等的子集 | LeetCode

我们可以理解为有 k 个桶,我们需要尝试将各个数字分别放入所有桶中,使得每个桶的 sum 都相等。

基本思路就是采用回溯算法,在“做选择”这一步,就是将一个数字分别选择放入各个不同的桶中,这样回溯决策树的第 i 层就是决定将 nums[i] 放入哪个 bucket 中。

但这种基本的回溯就等同于暴力搜索了,在 LeetCode 中提交后会出现超时错误,解决方法就是优化某些步骤,尽可能地剪枝

数据预处理:计算 target

这一步很重要。因为我们是让每个 bucket 中的 sum 都相等,那自然每个 bucket 的 sum 就等于 所有数字的加和 / bucket 数量,所以我们先计算出 target,也就是最终每个 bucket 中的所有数字的累加需要达到的目标。

int sum = Arrays.stream(sum).sum();
// 如果 sum 不能平分,则直接可以判定找不到答案
if (sum % k != 0) {
	return false;
}
int target = sum / k;  // 每个 bucket 的累加需要达到的目标

通过上面我们计算出了 target,就可以在回溯时提前判断当 bucket 的数字累加超过了 target 时,就可以提前剪枝了

基本回溯

由此,我们可以写出如下的解决代码:

class Solution {

    private boolean backtrack(int[] buckets, int target, int[] nums, int k, int level) {
        if (level >= nums.length) {
            for (int bucket: buckets) {
                if (bucket != target) {
                    return false;
                }
            }
            return true;
        }

        int num = nums[level];
        for (int i = 0; i < k; i++) {  // 遍历各个 bucket
            int sum = buckets[i] + num;  // 如果做出选择后,这个 bucket 的累加和
            if (sum > target) {  // 如果超出了 target,就提前剪枝
                continue;
            }
            buckets[i] = sum;
            boolean ok = backtrack(buckets, target, nums, k, level + 1);
            if (ok) {
                return true;
            }
            buckets[i] -= num;
        }

        return false;
    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) {
            return false;
        }
        int target = sum / k;
        int[] buckets = new int[k];
        Arrays.fill(buckets, 0);
        return backtrack(buckets, target, nums, k, 0);
    }
}

这个思路是没问题了,但是很遗憾,还是复杂度过高,超时。

优化 1:跳过某些 bucket 的选择

这里存在一个重要优化:当你做选择想把某个 num 放入一个 bucket 时,如果这个 bucket 的累加和与上一个 bucket 的累加和相同,那把这个 num 放入当前这个 bucket 的结果与放入上一个 bucket 的结果是一样的,上一个选择没有让我们找出答案,那这一次选择也不会让我们找出答案,因此可以直接剪枝跳过

由此,在上面的代码中,我们可以加入这样一个优化:

优化
这个优化只需要让我们加一个小判断,就能剪掉很多枝。

优化 2:事先对 nums 排序

因为我们会判断当前 bucket 的和是否超过了 target 进而剪枝,那事先对 nums 逆序排序,将大的数字放在前面,就更快地出现剪枝,从而减小复杂度。所以,我们可以在一开始先对 nums 进行逆序排序

逆序排序

最终代码事先

在基本的回溯代码再加上上面两个优化后,就可以通过 LeetCode 的检测了。最终代码如下:

class Solution {

    private boolean backtrack(int[] buckets, int target, int[] nums, int k, int level) {
        if (level >= nums.length) {
            for (int bucket: buckets) {
                if (bucket != target) {
                    return false;
                }
            }
            return true;
        }

        int num = nums[level];
        // 遍历各个 bucket 做选择
        for (int i = 0; i < k; i++) {
            // 如果当前桶和上一个桶内的元素和相等,则跳过
            // 原因:如果元素和相等,那么 nums[index] 选择上一个桶和选择当前桶可以得到的结果是一致的
            if (i != 0 && buckets[i] == buckets[i - 1]) {
                continue;
            }
            int sum = buckets[i] + num;  // 如果做出选择后,这个 bucket 的累加和
            if (sum > target) {   // 如果超出了 target,就提前剪枝
                continue;
            }
            buckets[i] = sum;
            boolean ok = backtrack(buckets, target, nums, k, level + 1);
            if (ok) {
                return true;
            }
            buckets[i] -= num;
        }

        return false;
    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 逆序排序 nums
        Arrays.sort(nums);
        for (int low = 0, high = nums.length - 1; low < high; low++, high--) {
            int temp = nums[low];
            nums[low] = nums[high];
            nums[high] = temp;
        }
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) {
            return false;
        }
        int target = sum / k;
        int[] buckets = new int[k];
        Arrays.fill(buckets, 0);
        return backtrack(buckets, target, nums, k, 0);
    }
}

LC 473. 火柴拼正方形 【练习】

[473. 火柴拼正方形 | LeetCode]

这个题目本质上和上个题目一样,可以当作练习。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/482504.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Zero-Change Object Transmission for Distributed Big Data Analytics——论文泛读

ATC 2022 Paper 问题 分布式大数据分析在很大程度上依赖于Java和Scala等高级语言的可靠性和多功能性。然而&#xff0c;这些高级语言也为数据传输制造了障碍。要在Java虚拟机&#xff08;JVM&#xff09;之间传输数据&#xff0c;发送方应将对象转换为字节数组&#xff08;序…

校验注解@Length提示Length.class 类文件具有错误的版本 55.0, 应为 52.0

你们好&#xff0c;我是金金金。 场景 我正在学习参数校验&#xff0c;启动项目时报错如下 实体类 依赖版本 报错信息 排查 看报错信息提示类文件具有错误的版本 55.0, 应为 52.0&#xff0c;猜测可能是版本的问题。 可以确实就是版本的关系了&#xff0c;8.0版本的只能在jd…

2024年基于springboot+vue的10个最新选题推荐

前言 &#x1f497;博主介绍&#xff1a;✌专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb; 精彩专栏 推荐订阅&#x1f447;&#x1f3fb; 2024年Java精品实战案例《100套》 &#x1f345;文末获取源码联系&#x1f345; &#x1f31f…

VMware Fusion Pro 13:一站式虚拟化解决方案,满足多样化需求

VMware Fusion Pro 13是一款功能强大的虚拟机软件&#xff0c;专为Mac操作系统设计。它支持在Mac电脑上创建和管理多个虚拟计算机&#xff0c;允许用户在不同操作系统中进行软件测试、开发和部署&#xff0c;如Windows、Linux等。该软件采用了最新的虚拟化技术&#xff0c;能够…

逻辑 | 逻辑先修营

学习到更新日期逻辑先修营-3常见逻辑连词及逻辑表达2024-3-23 1.形式逻辑基础1 2.形式逻辑基础2 3.常见逻辑连词及逻辑表述 4.OR相关考点 5.AND相关考点 6.逻辑箭头基本考点1 7.逻辑箭头基本考点2 8.代入逻辑推理事实真1 9.代入逻辑推理事实真2 10.形式逻辑四大基本考点…

VUE3 Day12pinia

属性在解构时需要用到storeToRefs语法&#xff0c;而方法则不需要 官方文档&#xff1a;https://prazdevs.github.io/pinia-plugin-persistedstate/zh/ 如果不配将使用pinia的默认配置

用Kimichat学习王庆法老师关于Sora的文章

目录 一 引言:二 提示词方面:三 与Kimi的聊天记录我:假如你是一名大模型方面的专家,提取一下这篇文章的核心观点,用三列表格的形式,https://mp.weixin.qq.com/s/Y-vmxmPu4_-tHaeP35hDJg我:上述文章的一、Spacetime Latent Patches 潜变量时空碎片, 建构视觉语言系统部分…

设计模式及其在项目、框架中的应用

设计模式的作用&#xff1a; 1、类之间关系图&#xff0c;明确的角色及其关系、作用&#xff1b; 2、符合开闭原则&#xff0c;职责明确&#xff0c;并且开放的拓展点可以有效应对后期的变化。 &#xff08;一&#xff09;、责任链模式 适用场景&#xff1a; 在一个流程中&…

ArmSoM-Sige RK3588开发板产品简介

让我们在 5 分钟内了解 Sige7。 简介​ ArmSoM-Sige7采用Rockchip RK3588新一代旗舰级八核64位处理器&#xff0c;主频高达2.4GHz&#xff0c;6 TOPS算力NPU&#xff0c;最大可配32GB大内存。支持8K视频编解码&#xff0c;拥有丰富的接口&#xff0c;支持双2.5G网口、WiFi6 &…

Tomcat9.0.87闪退解决方案

运行Tomcat9.0.87闪退 报错&#xff1a;Neither the JAVA_HOME nor the JRE_HOME environment variable is defined At least one of these environment variable is needed to run this program 原因&#xff1a;使用了免安装的方法&#xff0c;直接运行bin目录下的startup.ba…

unity学习(68)——相机/模型的旋转/位置计算

这个比想象中要难&#xff0c;而且需要自己写。 1.相机可以转xy两个位置&#xff0c;可以点头和转圈。注意这里有一个if判断&#xff08;后面返回来发现了这些问题&#xff09; 2.角色不能点头&#xff0c;只能转圈。 难得是移动方向&#xff0c;因为移动方向(位置)和转向是相…

无人机三维建模过程中注意事项

无人机三维建模是指利用无人机技术进行三维建模&#xff0c;该方法通过无人机搭载的多种传感器&#xff0c;如摄像头、激光扫描仪等&#xff0c;获取建筑物的多角度影像数据&#xff0c;然后利用计算机视觉技术和三维重建算法&#xff0c;将这些影像数据转化为高精度的三维模型…

Redis基础命令集详解

目录 1.Redis基础命令 2.Redis的经典案例 2.1 缓存 2.2 计数器 2.3 发布订阅 Redis是一个开源、内存存储的数据结构服务器&#xff0c;它支持多种数据结构&#xff0c;如字符串、哈希表、列表、集合、有序集合等。在Redis中&#xff0c;使用一些基础的命令来操作这些数据结…

从零开始学习在VUE3中使用canvas(六):lineCap(线条端点样式)

一、简介 lineCap能够让我们设置线条的端点样式&#xff0c;例如 1. butt const ctx canvas.getContext("2d");ctx.lineCap "butt"; // 默认样式&#xff0c;也可以显式指定 2.round const ctx canvas.getContext("2d");//圆头ctx.lineCap …

BRAM底层原理详细解释(1)

目录 一、原语 二、端口简述 2.1 端口简介 2.2 SDP端口映射 三、端口信号含义补充说明 3.1 字节写使能&#xff08;Byte-Write Enable&#xff09;- WEA and WEBWE&#xff1a; 3.2 地址总线—ADDRARDADDR and ADDRBWRADDR 3.3 数据总线—DIADI, DIPADIP, DIBDI, and D…

SSL加密:保护数据传输的安全盾牌

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

是德科技keysight E5061B网络分析仪

181/2461/8938产品概述&#xff1a; Keysight(原Agilent) E5061B 是一款 ENA 系列网络分析仪&#xff0c;可以满足广泛的低频至高频电子元器件和电路测量需求。E5061B 现可提供新的 5 Hz 至 3 GHz 频域器件分析标准。 E5061B ENA系列网络分析仪从5Hz 至3GHz提供了广泛的频率范…

使用 ReclaiMe Pro 查找并恢复网络中的 SSH 服务器数据

天津鸿萌科贸发展有限公司是 ReclaiMe Pro 数据恢复软件的授权代理商。ReclaiMe Pro 数据恢复软件专注于恢复几乎所有文件系统及各种类型和复杂程度的 RAID 阵列。 在本文中&#xff0c;我们介绍 ReclaiMe Pro 对于采用 SSH 连接方式的网络服务器中数据的恢复方法。 ReclaiMe…

DataV 在HTML中使用

一&#xff1a;什么是DataV 介绍 | DataV (jiaminghi.com) 组件库基于Vue &#xff08;React版 (opens new window)&#xff09; &#xff0c;主要用于构建大屏&#xff08;全屏&#xff09;数据展示页面即数据可视化&#xff0c;具有多种类型组件可供使用&#xff1a;…

「渗透笔记」致远OA A8 status.jsp 信息泄露POC批量验证

前言部分 在本节中&#xff0c;我会分两部分来说明致远OA A8 status.jsp 信息泄露的验证问题&#xff0c;其实就是两种验证方式吧&#xff0c;都一样&#xff0c;都是批量验证&#xff0c;主要如下所示&#xff1a; 通过Python脚本进行批量验证&#xff0c;但是前提是你可以收…