算法进修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)是一种构建和运行应用程序的方法,这种方法充分利用了云计算的优势。云原生应用程序是为云环境设计的,通常是在容器中运行,并被设计为在微服务架构中运行,这使得它们能够快速扩展和…...
大数据领域中分布式计算的性能优化策略
大数据领域中分布式计算的性能优化策略:解锁大数据处理的高效密码 关键词:大数据、分布式计算、性能优化、数据分区、负载均衡、通信优化 摘要:在大数据时代,分布式计算成为处理海量数据的关键技术。然而,如何优化分布…...
Phi-4-mini-reasoning效果展示:国际奥赛风格数学题全自动分步求解演示
Phi-4-mini-reasoning效果展示:国际奥赛风格数学题全自动分步求解演示 1. 模型介绍 Phi-4-mini-reasoning是微软推出的3.8B参数轻量级开源模型,专为数学推理、逻辑推导和多步解题等强逻辑任务设计。这款模型主打"小参数、强推理、长上下文、低延迟…...
终极优化指南:NodeSource Node.js 二进制分发版的 Docker 镜像体积与启动速度革命
终极优化指南:NodeSource Node.js 二进制分发版的 Docker 镜像体积与启动速度革命 【免费下载链接】distributions NodeSource Node.js Binary Distributions 项目地址: https://gitcode.com/gh_mirrors/di/distributions NodeSource Node.js 二进制分发版为…...
GHelper工具:解决华硕笔记本性能控制难题的轻量化方案
GHelper工具:解决华硕笔记本性能控制难题的轻量化方案 【免费下载链接】g-helper Lightweight, open-source control tool for ASUS laptops and ROG Ally. Manage performance modes, fans, GPU, battery, and RGB lighting across Zephyrus, Flow, TUF, Strix, Sc…...
如何快速掌握时空聚类:面向数据分析师的ST-DBSCAN终极指南
如何快速掌握时空聚类:面向数据分析师的ST-DBSCAN终极指南 【免费下载链接】st_dbscan ST-DBSCAN: Simple and effective tool for spatial-temporal clustering 项目地址: https://gitcode.com/gh_mirrors/st/st_dbscan 时空数据分析正成为现代数据科学的重…...
暗黑破坏神2存档编辑器终极指南:5分钟解放你的游戏体验
暗黑破坏神2存档编辑器终极指南:5分钟解放你的游戏体验 【免费下载链接】d2s-editor 项目地址: https://gitcode.com/gh_mirrors/d2/d2s-editor 还在为暗黑破坏神2中反复刷装备而烦恼吗?想快速体验不同职业build却不想从头练级?d2s-e…...
【限时开源】我们刚在GitHub归档的Python MCP生产模板——含自动证书轮换、配置热重载、灰度指令通道(仅开放72小时)
第一章:Python MCP服务器开发模板概览与核心设计哲学Python MCP(Model-Controller-Protocol)服务器开发模板是一个面向协议驱动、可插拔架构的轻量级服务框架,专为构建高内聚、低耦合的远程控制与设备交互服务而设计。它并非传统W…...
OpenClaw+Qwen3.5-9B低成本方案:自建接口替代OpenAI API
OpenClawQwen3.5-9B低成本方案:自建接口替代OpenAI API 1. 为什么选择Qwen3.5-9B作为OpenClaw的本地大脑 去年冬天,当我第一次尝试用OpenClaw自动化处理周报时,被OpenAI API的账单吓了一跳——简单的文件整理和摘要生成,一周竟消…...
拆解RTX4090 24G GPU服务器,一文摸清硬件搭配逻辑
RTX4090 24G GPU凭借NVIDIA Ada Lovelace架构优势,以16384个CUDA核心、24GB GDDR6X显存、1008GB/s显存带宽的核心参数,成为个人开发者、中小企业、科研机构的首选算力核心,广泛应用于大模型训练、AI推理、工业仿真、视频渲染等场景。据IDC 20…...
Phi-4-mini-reasoning效果对比:与Qwen-Math、DeepSeek-Math在逻辑题上的表现差异
Phi-4-mini-reasoning效果对比:与Qwen-Math、DeepSeek-Math在逻辑题上的表现差异 1. 模型介绍与测试背景 1.1 参测模型概览 本次对比测试聚焦三个专门针对数学和逻辑推理优化的模型: Phi-4-mini-reasoning:微软推出的轻量级推理专用模型&…...
