当前位置: 首页 > 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…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...