算法进修Day-38
算法进修Day-38
77. 组合
难度:中等
题目要求:
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
示例1
输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例2
输入:n = 1, k = 1
输出:[[1]]
题解
利用 D F S DFS DFS 算法可解
用 n u m num num 表示当前遍历到的数字,初始时 n u m = 1 num=1 num=1。回溯过程中,以下两种情况可以直接返回。
如果当前组合中有 k k k 个数,则得到一个 k k k 个数的组合,将其添加到答案中,不需要继续遍历更多的数字。
如果当前组合中的数字过少,即使将 [ n u m , n ] [num,n] [num,n] 范围中的所有整数都加入当前组合都无法使组合中的数字个数达到 k k k,则在当前组合的情况下一定不可能得到 k k k 个数的组合。
其余情况下,对于当前遍历到的数字 n u m num num,分别考虑将其加入组合与不加入组合两种情况,并执行回溯。
使用剪枝的情况下,可以排除不可能的组合,需要遍历的组合数从 2 n 2^n 2n 减少到 C n k C_n^k Cnk
想法代码
class Solution
{public static void Main(String[] args){Solution solution = new Solution();int n = 4;int k = 2;IList<IList<int>> res = solution.Combine(n, k);foreach (var i in res){foreach (var j in i){Console.Write(j + " ");}Console.WriteLine();}}public IList<IList<int>> Combine(int n, int k){IList<IList<int>> res = new List<IList<int>>();List<int> list = new List<int>();if (n < k || k <= 0){return(IList<IList<int>>)(list);}DFS(n, k, 1, list, res);return res;}public void DFS(int n, int k, int begin, IList<int> list, IList<IList<int>> res){IList<int> path = new List<int>();if (list.Count == k){for (int i = 0; i < list.Count; i++){path.Add(list[i]);}res.Add(path);return;}for (int i = begin; i <= n; i++){list.Add(i);DFS(n,k,i+1,list,res);list.RemoveAt(list.Count-1);}}
}
78. 子集
难度:中等
题目要求
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例1
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例2
输入:nums = [0]
输出:[[],[0]]
题解
利用回溯算法可解
每个结果都需要存储,不需要约束条件
由于每个都需要存储,所以不需要剪枝
注意,这个算法依旧需要回头
想法代码
public class Solution
{public static void Main(string[] args){Solution solution = new Solution();int[] nums = { 1, 2, 3 };IList<IList<int>> res = solution.Subsets(nums);foreach (var i in res){foreach (var j in i){Console.Write(j + " ");}Console.WriteLine();}}public IList<IList<int>> Subsets(int[] nums){IList<IList<int>> ans = new List<IList<int>>();if (nums == null || nums.Length == 0){return ans;}DFS(nums, new List<int>(), 0, ans);return ans;}public void DFS(int[] nums, List<int> path, int start,IList<IList<int>> ans){ans.Add(new List<int>(path));for (int i = start; i < nums.Length; i++){path.Add(nums[i]);DFS(nums, path, i + 1,ans);path.Remove(nums[i]);}}
}
相关文章:
算法进修Day-38
算法进修Day-38 77. 组合 难度:中等 题目要求: 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 示例1 输入:n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 示例2 输入&#…...
8.MySQL内外连接
个人主页:Lei宝啊 愿所有美好如期而遇 目录 表的内连和外连 内连接 外连接 左外连接 右外连接 我们进行演示的表结构是这样的: 表的内连和外连 内连接 内连接实际上就是利用where子句对两种表形成的笛卡儿积进行筛选,我们前面学习的…...
使用.NET设计一个Epub电子书生成工具
1. 背景 可能我们接触到更多的小说文件都是普普通通的TXT格式,用于分享的文档更多的是PDF。TXT虽然轻巧,但是不如PDF丰富和强大。而 Epub 电子书格式因为其丰富的展示效果和较小的文件大小,这样一个微妙的平衡就刚刚好。作为一个喜欢看小说的…...
2023-10-26 用C语言实现一个大整数加法
点击 <C 语言编程核心突破> 快速C语言入门 用C语言实现一个大整数加法 前言一、思路和代码设计数字对齐:字符对齐: 二、代码总结 前言 要解决问题: 实现大整数加法 想到的思路: 用字符代替数字, 逐个计算, 过10进位. 其它的补充: 同样思路可以解决减法, 乘法, 但除法…...
[hive] 窗口函数 ROW_NUMBER()
文章目录 ROW_NUMBER() 示例窗口函数 ROW_NUMBER() 在 Hive SQL 中,ROW_NUMBER()是一个用于生成行号的窗口函数。 它可以为查询结果集中的每一行分配一个唯一的行号。 以下是 ROW_NUMBER() 函数的基本语法: ROW_NUMBER() OVER (PARTITION BY column…...
TensorFlow和Pytorch两种机器学习框架的比较及优缺点
TensorFlow是一个开源的机器学习框架,由Google开发并发布,它被用来构建各种类型的机器学习模型,例如图像识别、语音识别、自然语言处理等。TensorFlow主要有以下几个基本概念: Tensor:TensorFlow中最基本的数据结构&am…...
“Can‘t open workbook - unsupported file type: XML“
java开发,增删改查,涉及到导入excel时,有的excel导入失败提示"Cant open workbook - unsupported file type: XML"。着急赶工期,告诉客户先把excel另存为xls格式,再重新导入。现在有点空余时间,好…...
达芬奇MacOS最新中文版 DaVinci Resolve Studio 18中文注册秘钥
DaVinci Resolve Studio 18是一款专业的视频编辑软件,它具有多种强大的功能。首先,它提供了丰富的视频剪辑工具,如剪切、复制、粘贴、剪辑、缩放和移动等,使用户可以轻松地剪辑和组合视频素材。其次,该软件还支持多个轨…...
电脑扬声器未插入?4个方法帮你恢复声音!
“太奇怪了吧,我的电脑扬声器一直显示未插入,我使用电脑的时候也是一直都没有声音。这是为什么呢?我应该怎么解决这个问题呀?” 我们使用电脑播放音频或视频时,都需要用到电脑扬声器。如果扬声器无法播放声音ÿ…...
Python - 通过/SSH 获取远程主机的 env 变量
Python - 通过/SSH 使用远程主机的 env 变量 - IT工具网 (coder.work) ssh.exec_command(. .profile ; cd /home/test/;$run ./test.sh)ssh.exec_command(. .profile ; cd /home/test/;echo $run )...
ubuntu 下的 使用anaconda 环境运行python 项目
pycharm部署django项目到云服务器的详细流程_编程网 anaconda 安装环境 Ubuntu安装Anaconda详细步骤(Ubuntu22.04.1,Anaconda3-2023.03)-CSDN博客 ubuntu下Anaconda安装与使用教程_ubuntu 运行anaconda_fakerth的博客-CSDN博客 Anaconda教…...
MySQL创建定时任务定时执行sql
#删除定时任务 DROP EVENT IF EXISTS user_event ; -- 创建名字为user_event的事件 CREATE EVENT user_event ON SCHEDULE EVERY 1 DAY STARTS DATE_ADD(DATE_ADD(CURDATE(), INTERVAL 1 DAY), INTERVAL 1 HOUR) -- 每隔一天执行一次,开始执行时间为明天凌晨1点整 …...
如何用MFI确定波浪理论第一浪,anzo capital实操演示
通过上文投资者学会了如何确定波浪理论第一浪,但在后台有投资者咨询 :如何用MFI确定波浪理论第一浪,anzo capital昂首资本秉承着有求必应的态度,今天实操进行演示。 在图中,发散用蓝色标注,收敛用绿色。价…...
vscode推送gitee方法
有一套uni-app代码需要修改,版本控制使用vscode的git功能,远程库在gitee上。 1、设置vscode中git.exe路径 由于git使用了绿色便携版(PortableGit-2.42.0.2-64-bit.7z.exe),vscode未识别到git安装路径,需要…...
R语言与作物模型(以DSSAT模型为例)融合应用
随着基于过程的作物生长模型(Process-based Crop Growth Simulation Model)的发展,R语言在作物生长模型和数据分析、挖掘和可视化中发挥着越来越重要的作用。想要成为一名优秀的作物模型使用者与科研团队不可或缺的人才,除了掌握对…...
MFC Windows 程序设计[336]之历史记录编辑框(附源码)
MFC Windows 程序设计[336]之历史记录编辑框 程序之美前言主体运行效果核心代码逻辑分析结束语程序之美 前言 MFC是微软公司提供的一个类库(class libraries),以C++类的形式封装了Windows API,并且包含一个应用程序框架,以减少应用程序开发人员的工作量。其中包含大量Wi…...
基于单片机的IC卡门禁系统设计
收藏和点赞,您的关注是我创作的动力 文章目录 概要 一、主要研究内容及总体设计方案1.1 系统方案设计1.2系统工作原理 二、硬件设计2.1 主控电路 三、软件设计3.2主程序设计实物附录1 原理图附录2 源程序清单 四、 结论五、 文章目录 概要 本论文重点通过对射频技术…...
大模型 | NEFTune之引入随机噪声对大模型训练的收益
大模型 | NEFTune之引入随机噪声对大模型训练的收益 paper中提到,在模型foward过程中,对inputs_embedding增加适度的随机噪声,会带来显著的收益。 Paper: https://arxiv.org/pdf/2310.05914.pdf Github: https://github.com/neelsjain/NEFT…...
【开源】基于SpringBoot的高校学院网站的设计和实现
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 学院院系模块2.2 竞赛报名模块2.3 教育教学模块2.4 招生就业模块2.5 实时信息模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 学院院系表3.2.2 竞赛报名表3.2.3 教育教学表3.2.4 招生就业表3.2.5 实时信息表 四、系…...
什么是云原生?土生土长?
“云原生”(Cloud Native)是一种构建和运行应用程序的方法,这种方法充分利用了云计算的优势。云原生应用程序是为云环境设计的,通常是在容器中运行,并被设计为在微服务架构中运行,这使得它们能够快速扩展和…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
