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

二刷代码随想录|Java版|回溯算法3|子集问题

习题

2.3 子集问题

就是组合过程收集path。就像是代码随想录里说得那样,组合和分割问题就是收集叶子结点,子集问题就是收集每一个节点。
有涉及到同层重复元素的问题。
先排序,后再for循环里处理相同数值跳过。
设置函数内的used。
还可以用HashSet,Map
HashSet:

//创建
HashSet<Integer> hs = new HashSet<>();
//判断
|| hs.contains(nums[i])
//修改
hs.add(nums[i]);

Map:

//创建
HashMap<Integer,Integer> map = new HashMap<>();
//判断
if ( map.getOrDefault( nums[i],0 ) >=1 ){//返回 key 相映射的的 value,如果给定的 key 在映射关系中找不到,则返回指定的默认值。continue;
}            
//修改
map.put(nums[i],map.getOrDefault( nums[i],0 )+1);

2.3.1 78. 子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
还是要画回溯树比较快,需要startIdx,结束条件就是与length比较。

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> path = new ArrayList<Integer>();private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList<>(path));for(int i=startIdx; i<nums.length; i++){path.add(nums[i]);Backtracing(nums, i+1);path.removeLast();}       }public List<List<Integer>> subsets(int[] nums) {ans.clear();path.clear();Backtracing(nums, 0);return ans;}
}

2.3.2 90. 子集 II

涉及同层重复元素的排除。
还是要画回溯树比较好理解。
还记得就是先排序,后再for循环里处理相同数值跳过。

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> path = new ArrayList<Integer>();private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList<>(path));for(int i=startIdx; i<nums.length; i++){if(i!=startIdx&&nums[i]==nums[i-1]){continue;}path.add(nums[i]);Backtracing(nums, i+1);path.removeLast();}  }public List<List<Integer>> subsetsWithDup(int[] nums) {ans.clear();path.clear();Arrays.sort(nums);Backtracing(nums, 0);return ans;}
}
class Solution {List<List<Integer>> ans = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果boolean[] used;private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList<>(path));if (startIdx >= nums.length){return;}for (int i = startIdx; i < nums.length; i++){if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){continue;}path.add(nums[i]);used[i] = true;Backtracing(nums, i + 1);path.removeLast();used[i] = false;}}public List<List<Integer>> subsetsWithDup(int[] nums) {if (nums.length == 0){ans.add(path);return ans;}Arrays.sort(nums);used = new boolean[nums.length];Backtracing(nums, 0);return ans;}
}

2.3.3 491.递增子序列

示例 1:至少两个元素
输入:nums = [4,6,7,7]
输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
想要用used来,可是有负数,我该怎么处理?有说范围-100,100,所以可以用数组哦。

class Solution {List<List<Integer>> ans = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();private void Backtracing(int[] nums, int startIdx){if(path.size()>=2){ans.add(new ArrayList<>(path));}if (startIdx >= nums.length){return;}int[] used = new int[201];for (int i = startIdx; i < nums.length; i++){if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || (used[nums[i] + 100] == 1)) continue;used[nums[i] + 100] = 1;path.add(nums[i]);Backtracing(nums, i + 1);path.removeLast();}}public List<List<Integer>> findSubsequences(int[] nums) {if (nums.length == 0){ans.add(path);return ans;}Backtracing(nums, 0);return ans;}
}

还可以用HashSet,Map
HashSet:

//创建
HashSet<Integer> hs = new HashSet<>();
//判断
|| hs.contains(nums[i])
//修改
hs.add(nums[i]);

Map:

//创建
HashMap<Integer,Integer> map = new HashMap<>();
//判断
if ( map.getOrDefault( nums[i],0 ) >=1 ){continue;
}            
//修改
map.put(nums[i],map.getOrDefault( nums[i],0 )+1);

相关文章:

二刷代码随想录|Java版|回溯算法3|子集问题

习题 2.3 子集问题 就是组合过程收集path。就像是代码随想录里说得那样&#xff0c;组合和分割问题就是收集叶子结点&#xff0c;子集问题就是收集每一个节点。 有涉及到同层重复元素的问题。 先排序&#xff0c;后再for循环里处理相同数值跳过。 设置函数内的used。 还可以用…...

mongodb config

windows&#xff1a; 1.同级bin&#xff0c;data&#xff0c;log创建mongo.config文件 dbpathD:\Program\mongodb\data\db logpathD:\Program\mongodb\log\mongo.log logappendtrue #默认启用日志 journaltrue #过滤无用日志信息&#xff0c;调试设置为false quiettrue port2…...

pytorch 实现中文文本分类

&#x1f368; 本文为[&#x1f517;365天深度学习训练营学习记录博客&#x1f366; 参考文章&#xff1a;365天深度学习训练营&#x1f356; 原作者&#xff1a;[K同学啊 | 接辅导、项目定制]\n&#x1f680; 文章来源&#xff1a;[K同学的学习圈子](https://www.yuque.com/mi…...

【MySQL】聚合函数和内置函数

文章目录 1 :peach:聚合函数:peach:2 :peach:group by子句的使用:peach:3 :peach:内置函数:peach:3.1 :apple:日期函数:apple:3.2 :apple:字符串函数:apple:3.3 :apple:数学函数:apple: 4 :peach:其它函数:peach: 1 &#x1f351;聚合函数&#x1f351; 函数说明COUNT([DISTIN…...

python第五节:集合set(4)

集合其他方法&#xff1a; len(s) set 的长度 x in s x 是否是 s 的成员 x not in s x 是否不是 s 的成员 s.issubset(t) 是否 s 中的每一个元素都在 t 中 s.issuperset(t) 是否 t 中的每一个元素都在 s s.union(t) 返回一个新的 set 包含 s 和 t 中的每一个元素 …...

知识笔记(一百)———什么是okhttp?

OkHttp简介&#xff1a; OkHttp 是一个开源的、高效的 HTTP 客户端库&#xff0c;由 Square 公司开发和维护。它为 Android 和 Java 应用程序提供了简单、强大、灵活的 HTTP 请求和响应的处理方式。OkHttp 的设计目标是使网络请求变得更加简单、快速、高效&#xff0c;并且支持…...

Electron桌面应用实战:Element UI 导航栏橙色轮廓之谜与Bootstrap样式冲突解决方案

目录 引言 问题现象及排查过程 描述问题 深入探索 查明原因 解决方案与策略探讨 重写样式 禁用 Bootstrap 样式片段 深度定制 Element UI 组件 隔离样式作用域 结语 引言 在基于 Electron 开发桌面应用的过程中&#xff0c;我们可能时常遇到各种意想不到的问题…...

Nuget包缓存存放位置迁移

一、背景 默认情况下&#xff0c;NuGet会将项目中使用的包缓存到C盘&#xff0c;随着项目开发积累nuget包越来越多&#xff0c;这会逐渐挤占大量C盘空间&#xff0c;所以我们可以将nuget包缓存位置指定到其他盘中存放。 二、软件环境 win10、vs2022 三、查看当前缓存存放位…...

键盘上Ins键的作用

前几天编写文档时&#xff0c;发现一个问题&#xff1a;插入内容时&#xff0c;输入的字符将会覆盖光标位置后的字符。原来是按到了键盘上的 Ins键&#xff0c;解决方法是&#xff1a;再按一次 Ins键&#xff08;Ins键如果独立作为一键时&#xff0c;否则使用 “Fn Ins”组合键…...

css display 左右对齐 技巧

.list_number{ display: flex; } .list_name_number{ width:100px; } //左边固定width .list_name_type{ //右边给flex:2 自动撑开 flex:2; }...

【Linux操作系统】:Linux开发工具编辑器vim

目录 Linux 软件包管理器 yum 什么是软件包 注意事项 查看软件包 如何安装软件 如何卸载软件 Linux 开发工具 Linux编辑器-vim使用 vim的基本概念 vim的基本操作 vim正常模式命令集 插入模式 插入模式切换为命令模式 移动光标 删除文字 复制 替换 撤销 跳至指…...

Good Trip Codeforces Round 921 (Div. 2) 1925D

Problem - D - Codeforces 题目大意&#xff1a;有n个数&#xff0c;其中有m个匹配对&#xff0c;对于一个匹配对&#xff08;x,y&#xff09;&#xff0c;他们的除湿贡献为z&#xff0c;一共有k轮行动&#xff0c;每一轮从n个数中独立等概率的选出两个数&#xff0c;如果这两…...

推荐一款Linux、数据库、Redis、MongoDB统一管理平台!

官方演示 状态查看 ssh 终端 文件操作 数据库操作 sql 编辑器 在线增删改查数据 Redis 操作 Mongo 操作 系统管理 账号管理 角色管理 资源管理 一.安装 1.下载安装包 cd /opt wget https://gitee.com/dromara/mayfly-go/releases/download/v1.7.1/mayfly-go-linux-amd64.zi…...

TensorFlow2实战-系列教程6:迁移学习实战

&#x1f9e1;&#x1f49b;&#x1f49a;TensorFlow2实战-系列教程 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Jupyter Notebook中进行 本篇文章配套的代码资源已经上传 1、迁移学习 用已经训练好模型的权重参数当做自己任务的模型权重初始化一般全连接层需…...

怎样开发adobe indesign插件,具体流程?

文章目录 第一.流程步骤第二.如何调试indesign插件第三.相关资源第四.总结 第一.流程步骤 开发Adobe InDesign插件通常涉及以下步骤&#xff1a; 获取SDK和工具&#xff1a; 从Adobe官方网站下载最新的Adobe InDesign SDK&#xff08;Software Development Kit&#xff09;&am…...

Docker 安装与基本操作

目录 一、Docker 概述 1、Docker 简述 2、Docker 的优势 3、Docker与虚拟机的区别 4、Docker 的核心概念 1&#xff09;镜像 2&#xff09;容器 3&#xff09;仓库 二、Docker 安装 1、命令&#xff1a; 2、实操&#xff1a; 三、Docker 镜像操作 1、命令&#xff1…...

译文带你理解Python的dataclass装饰器

dataclass 是 Python dataclasses 模块中的一个 decorator。当使用 dataclass 装饰器时&#xff0c;它会自动生成一些特殊方法&#xff0c;包括&#xff1a; _ _ init _ _&#xff1a;用于初始化字段的构造函数_ _ repr _ _&#xff1a;对象的字符串表示_ _ eq _ _&#xff1a…...

【C语言】实现程序的暂停

编写程序时&#xff0c;有时候需要让程序在某些地方暂停执行&#xff0c;等待用户输入或者观察程序执行结果。在 C 语言中&#xff0c;有多种方法可以实现程序的暂停&#xff0c;包括 system("pause")、getchar() 和 while ((c getchar()) ! \n && c ! EOF)…...

Hana SQL+正则表达式

目录 一、Pre 前言 二、知识点拆解 1&#xff09;case when…then…else 2&#xff09;json_value 函数 拓展资料 3&#xff09;CAST 函数 拓展资料 4) ROUND 函数 5&#xff09;occurences_regexpr 函数 拓展资料 6&#xff09;正则表达式 拓展资料 三、整合分析…...

【笔记】顺利通过EMC试验(16-41)-视频笔记

目录 视频链接 P1:电子设备中有哪些主要骚扰源 P2:怎样减小DC模块的骚扰 P3:PCB上的辐射源究竟在哪里 P4:怎样控制PCB板的电磁辐射 P5:多层线路板是解决电磁兼容问题的简单方法 P6:怎样处理地线上的裂缝 P7:怎样降低时钟信号的辐射 P8:为什么IO接口的处理特别重要 P9…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...