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

每日刷题(回溯法经典问题之子集)

                                        食用指南:本文为作者刷题中认为有必要记录的题目

                                        前置知识回溯法经典问题之组合

                                       ♈️今日夜电波:想着你—郭顶

                                                                1:09 ━━━━━━️💟──────── 4:15
                                                                    🔄   ◀️   ⏸   ▶️    ☰ 

                                      💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍 


目录

回溯法的理解

💮 一、子集

🌺二、子集II


回溯法的理解

 本文参考了一位大佬的题解,详细的介绍了回溯法:链接

上一篇刷题文: 回溯法经典问题之组合

        记住一句话:for循环横向遍历,递归纵向遍历,回溯不断调整结果集。 这句话将从始至终贯穿我们对于以上问题的回溯解决办法。 


💮 一、子集

题目链接:78. 子集

题目描述:

        给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

本题思路:

        采用经典的“回溯三部曲”:

        1、定义两个全局变量,一个用来存放符合条件单一结果(path),一个用来存放符合条件结果的集合(result)。注意要记得用一个变量来记录遍历的位置。

        2、回溯的主体,回溯终止条件。path保存一组数据,每次遍历到叶子节点,再插入到result中,并且回溯到上一个节点。

        3、单层搜索的过程。for循环用来横向遍历,递归的过程是纵向遍历。

      特别注意: 本题虽然同之前的组合问题差不多,但是还是需要做一定的变化的,依据题意,我们都知道任何一个子集都是包涵空集的,并且子集中一个元素也算子集。

         于是根据题意写出以下题解:

class Solution {
private:
vector<int> path;
vector<vector<int>> result;void backtrack(vector<int>& nums,int index)
{result.push_back(path);   if(index==nums.size()){return;}for(int i=index;i<nums.size();i++){path.push_back(nums[i]);backtrack(nums,i+1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {path.clear();result.clear();sort(nums.begin(),nums.end());backtrack(nums,0);return result;}
};


🌺二、子集II

题目链接:90. 子集 II

题目描述:

        给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

示例 1:

输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

  本题思路:

        同样采用经典的“回溯三部曲”,但是由于此题中的元素是可以重复的,那这样必然会出现重复的子集,因此我们需要进行剪枝操作。此时可以参考 回溯法经典问题之组合 中最后一题。我们也建立一个used,用于标记是否使用过使用过元素。

         特别注意: 本题虽然同之前的题差不多,但是还是需要做一定的变化的。比如插入的操作。

        一图了解题解 ~(以{1,2,2}为例)

class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtrack(vector<int>& nums,int index,vector<bool>& used)
{result.push_back(path);if(index==nums.size()){return;}for(int i=index;i<nums.size();i++){if(i>0&&nums[i-1]==nums[i]&&used[i-1]==0)continue;path.push_back(nums[i]);used[i]=1;backtrack(nums,i+1,used);used[i]=0;path.pop_back();}
}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {path.clear();result.clear();vector<bool> used;used.resize(nums.size());sort(nums.begin(),nums.end());backtrack(nums,0,used);return result;}
};


                感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o!  

                                 

                                                                 给个三连再走嘛~      

相关文章:

每日刷题(回溯法经典问题之子集)

食用指南&#xff1a;本文为作者刷题中认为有必要记录的题目 前置知识&#xff1a;回溯法经典问题之组合 ♈️今日夜电波&#xff1a;想着你—郭顶 1:09 ━━━━━━️&#x1f49f;──────── 4:15 …...

PostgreSQL在进行除法时要注意

背景 整型除以整型&#xff0c;正常情况下当然得到的应该也是整型。数据库也是这么干的。 但是在数据库应用中&#xff0c;通常业务的需求是得到NUMERIC&#xff0c;不能直接把小数干掉。 数据库的行为给用户带来了诸多不便&#xff0c;例如1除以2&#xff0c;如果是整型除法会…...

开开心心带你学习MySQL数据库之第五篇

&#x1f63a;欢迎来到我的博客, 记得点赞&#x1f44d;收藏⭐️留言✍️&#x1f431; &#x1f409;做为一个怪兽&#xff0c;我的目标是少消灭一个奥特曼&#x1f409; &#x1f4d6;希望我写的博客对你有所帮助,如有不足,请指正&#x1f4d6; chatgpt 是否能够代替程序猿?…...

Geotools对geojson的解析

在 GeoTools 中&#xff0c;对 GeoJSON 的支持是通过一个插件来完成的&#xff0c;用户同样可以在 Maven 的 pom.xml 配置文件中添加下述的依赖。 <dependency><groupId>org.geotools</groupId><artifactId>gt-geojson</artifactId><version&…...

【博客701】shell实现保留网络现场:ping失败时执行mtr

shell实现保留网络现场&#xff1a;ping失败时执行mtr 场景 当我们网络出现抖动&#xff0c;到某个目的地ping不通时&#xff0c;我们想知道路径上哪里出现问题时可以在那时候执行mtr并保留下现场以供排查 实现&#xff1a;ping_and_mtr.sh #!/bin/bash# 定义要ping的IP地址列…...

放弃手写代码吧!用低代码你能生成各种源码

很多同学不知道为什么要用Low-code做开发&#xff0c;传统IT开发不行么&#xff1f;当然可以。 传统IT自研软件开发&#xff0c;通过编程去写代码&#xff0c;还有数据库、API、第三方基础架构等。这个方式很好&#xff0c;但不可避免的会带来开发周期长、难度大&#xff0c;技…...

什么程度才算精通 Linux?

前言 Linux 的优秀之处自然不必多说。 如果将操作系统比作一辆汽车&#xff0c;那 Linux 就是一辆性能出色的多功能越野车&#xff0c;上山下海飞天无所不能。 如果你拥有了它&#xff0c;一定不会只满足于驾驶它上下班&#xff0c;不能只会挂挡、踩油门和控制方向之类的基本…...

jmeter中的__setProperty用法

__setProperty 是一个用于设置 JMeter 属性的函数&#xff0c;基本语法&#xff1a; __setProperty(property, value)** property : 是要设置的属性的名称 ** value : 是要设置的属性的值在 JMeter中&#xff0c;可以使用 __setProperty 函数的元素&#xff1a; BeanShell …...

vue基础知识六:v-show和v-if有什么区别?使用场景分别是什么?

一、v-show与v-if的共同点 我们都知道在 vue 中 v-show 与 v-if 的作用效果是相同的(不含v-else)&#xff0c;都能控制元素在页面是否显示 在用法上也是相同的 <Model v-show"isShow" /> <Model v-if"isShow" />当表达式为true的时候&#…...

SpringBoot几个常用的注解

&#xff08;1&#xff09;RestController和Controller指定一个类&#xff0c;作为控制器的注解 &#xff08;2&#xff09;RequestMapping方法级别的映射注解&#xff0c;这一个用过Spring MVC的小伙伴相信都很熟悉 &#xff08;3&#xff09;EnableAutoConfiguration和Spri…...

腾讯JAVA后端秋招面试总结

腾讯秋招的面经,岗位是 java 后端开发。 说一下BIO、NIO和AIO 答: BIO是阻塞IO。在上一个线程的任务执行完之前,该线程必须阻塞等待上一个线程执行完毕。 NIO是非阻塞IO。一旦是响应事件发生了,该线程就会将对应的响应事件交给对应的事件处理器进行处理。 AIO是异步IO。主…...

随着iPhone 15降临,是时候扔掉所有的Lightning充电器了

自从苹果推出Lightning端口&#xff08;一直追溯到iPhone 5&#xff09;十多年后&#xff0c;你可能已经积累了相当多的Lightning电缆和配件。好吧&#xff0c;在下周的苹果活动之前&#xff0c;所有关于iPhone 15的传言都表明你不再需要它们了。 与最好的iPad和最好的MacBook…...

huggingface 使用入门笔记

概念 Hugging Face Hub​​和 Github 类似&#xff0c;都是Hub(社区)。Hugging Face可以说的上是机器学习界的Github。Hugging Face为用户提供了以下主要功能&#xff1a; ​模型仓库&#xff08;Model Repository&#xff09;​​&#xff1a;Git仓库可以让你管理代码版本、…...

ASP.NET Core 中的 Razor Pages

Razor Pages Razor Pages 是基于页面的 ASP.NET Core Web App 架构。 相比 MVC 模式&#xff0c;Razor Pages的生产效率更快。 Razer Pages 需要两个中间件&#xff1a; builder…Services.AddRazorPages 添加 Razor Pages servicesapp.MapRazorPages 添加 Razor Pages endpo…...

C语言入门 Day_14 for循环

目录​​​​​​​ 1.for循环 2.循环执行顺序 3.易错点 4.思维导图 前言 我们定义了一个数组以后&#xff0c;要使用&#xff08;读取或者修改&#xff09;数组元素的话&#xff0c;可以一个一个的读取&#xff0c;就前两课学的那样&#xff0c;代码类似这个结构。 int …...

深入解析 Socks5 代理与网络安全

作为网络工程师和网络文章主编&#xff0c;我们时刻关注着网络世界中的新趋势和技术发展。本文将探讨 Socks5 代理、代理IP、网络安全以及与之相关的 HTTP 协议&#xff0c;为您呈现一个深入的技术洞察。 引言 在今天的互联网时代&#xff0c;网络安全是至关重要的话题。攻击…...

Vue + Element UI 前端篇(十二):用户管理模块

Vue Element UI 实现权限管理系统 前端篇&#xff08;十二&#xff09;&#xff1a;用户管理模块 用户管理模块 添加接口 在 http/moduls/user.js 中添加用户管理相关接口。 import axios from ../axios/* * 用户管理模块*/// 保存 export const save (params) > {ret…...

C# 设计保存文件

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System...

Leetcode 1486.数组异或操作

给你两个整数&#xff0c;n 和 start 。 数组 nums 定义为&#xff1a;nums[i] start 2*i&#xff08;下标从 0 开始&#xff09;且 n nums.length 。 请返回 nums 中所有元素按位异或&#xff08;XOR&#xff09;后得到的结果。 示例 1&#xff1a; 输入&#xff1a;n 5, …...

【Java】Java核心API概述

Java核心API是Java编程语言的基础&#xff0c;包含了Java应用程序中常用的类和接口。本文将介绍Java核心API中的一些重要部分&#xff0c;包括输入输出流、异常处理、集合框架、多线程和网络编程等。 1、输入输出流 Java的输入输出流API是Java IO&#xff0c;它提供了处理输入…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...