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

算法进修Day-38

算法进修Day-38

77. 组合

难度:中等
题目要求:
给定两个整数 nk,返回范围 [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. 组合 难度&#xff1a;中等 题目要求&#xff1a; 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 示例1 输入&#xff1a;n 4, k 2 输出&#xff1a; [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 示例2 输入&#…...

8.MySQL内外连接

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 目录 表的内连和外连 内连接 外连接 左外连接 右外连接 我们进行演示的表结构是这样的&#xff1a; 表的内连和外连 内连接 内连接实际上就是利用where子句对两种表形成的笛卡儿积进行筛选&#xff0c;我们前面学习的…...

使用.NET设计一个Epub电子书生成工具

1. 背景 可能我们接触到更多的小说文件都是普普通通的TXT格式&#xff0c;用于分享的文档更多的是PDF。TXT虽然轻巧&#xff0c;但是不如PDF丰富和强大。而 Epub 电子书格式因为其丰富的展示效果和较小的文件大小&#xff0c;这样一个微妙的平衡就刚刚好。作为一个喜欢看小说的…...

2023-10-26 用C语言实现一个大整数加法

点击 <C 语言编程核心突破> 快速C语言入门 用C语言实现一个大整数加法 前言一、思路和代码设计数字对齐:字符对齐: 二、代码总结 前言 要解决问题: 实现大整数加法 想到的思路: 用字符代替数字, 逐个计算, 过10进位. 其它的补充: 同样思路可以解决减法, 乘法, 但除法…...

[hive] 窗口函数 ROW_NUMBER()

文章目录 ROW_NUMBER() 示例窗口函数 ROW_NUMBER() 在 Hive SQL 中&#xff0c;ROW_NUMBER()是一个用于生成行号的窗口函数。 它可以为查询结果集中的每一行分配一个唯一的行号。 以下是 ROW_NUMBER() 函数的基本语法&#xff1a; ROW_NUMBER() OVER (PARTITION BY column…...

TensorFlow和Pytorch两种机器学习框架的比较及优缺点

TensorFlow是一个开源的机器学习框架&#xff0c;由Google开发并发布&#xff0c;它被用来构建各种类型的机器学习模型&#xff0c;例如图像识别、语音识别、自然语言处理等。TensorFlow主要有以下几个基本概念&#xff1a; Tensor&#xff1a;TensorFlow中最基本的数据结构&am…...

“Can‘t open workbook - unsupported file type: XML“

java开发&#xff0c;增删改查&#xff0c;涉及到导入excel时&#xff0c;有的excel导入失败提示"Cant open workbook - unsupported file type: XML"。着急赶工期&#xff0c;告诉客户先把excel另存为xls格式&#xff0c;再重新导入。现在有点空余时间&#xff0c;好…...

达芬奇MacOS最新中文版 DaVinci Resolve Studio 18中文注册秘钥

DaVinci Resolve Studio 18是一款专业的视频编辑软件&#xff0c;它具有多种强大的功能。首先&#xff0c;它提供了丰富的视频剪辑工具&#xff0c;如剪切、复制、粘贴、剪辑、缩放和移动等&#xff0c;使用户可以轻松地剪辑和组合视频素材。其次&#xff0c;该软件还支持多个轨…...

电脑扬声器未插入?4个方法帮你恢复声音!

“太奇怪了吧&#xff0c;我的电脑扬声器一直显示未插入&#xff0c;我使用电脑的时候也是一直都没有声音。这是为什么呢&#xff1f;我应该怎么解决这个问题呀&#xff1f;” 我们使用电脑播放音频或视频时&#xff0c;都需要用到电脑扬声器。如果扬声器无法播放声音&#xff…...

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详细步骤&#xff08;Ubuntu22.04.1&#xff0c;Anaconda3-2023.03&#xff09;-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) -- 每隔一天执行一次&#xff0c;开始执行时间为明天凌晨1点整 …...

如何用MFI确定波浪理论第一浪,anzo capital实操演示

通过上文投资者学会了如何确定波浪理论第一浪&#xff0c;但在后台有投资者咨询 &#xff1a;如何用MFI确定波浪理论第一浪&#xff0c;anzo capital昂首资本秉承着有求必应的态度&#xff0c;今天实操进行演示。 在图中&#xff0c;发散用蓝色标注&#xff0c;收敛用绿色。价…...

vscode推送gitee方法

有一套uni-app代码需要修改&#xff0c;版本控制使用vscode的git功能&#xff0c;远程库在gitee上。 1、设置vscode中git.exe路径 由于git使用了绿色便携版&#xff08;PortableGit-2.42.0.2-64-bit.7z.exe&#xff09;&#xff0c;vscode未识别到git安装路径&#xff0c;需要…...

R语言与作物模型(以DSSAT模型为例)融合应用

随着基于过程的作物生长模型&#xff08;Process-based Crop Growth Simulation Model&#xff09;的发展&#xff0c;R语言在作物生长模型和数据分析、挖掘和可视化中发挥着越来越重要的作用。想要成为一名优秀的作物模型使用者与科研团队不可或缺的人才&#xff0c;除了掌握对…...

MFC Windows 程序设计[336]之历史记录编辑框(附源码)

MFC Windows 程序设计[336]之历史记录编辑框 程序之美前言主体运行效果核心代码逻辑分析结束语程序之美 前言 MFC是微软公司提供的一个类库(class libraries),以C++类的形式封装了Windows API,并且包含一个应用程序框架,以减少应用程序开发人员的工作量。其中包含大量Wi…...

基于单片机的IC卡门禁系统设计

收藏和点赞&#xff0c;您的关注是我创作的动力 文章目录 概要 一、主要研究内容及总体设计方案1.1 系统方案设计1.2系统工作原理 二、硬件设计2.1 主控电路 三、软件设计3.2主程序设计实物附录1 原理图附录2 源程序清单 四、 结论五、 文章目录 概要 本论文重点通过对射频技术…...

大模型 | NEFTune之引入随机噪声对大模型训练的收益

大模型 | NEFTune之引入随机噪声对大模型训练的收益 paper中提到&#xff0c;在模型foward过程中&#xff0c;对inputs_embedding增加适度的随机噪声&#xff0c;会带来显著的收益。 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 实时信息表 四、系…...

什么是云原生?土生土长?

“云原生”&#xff08;Cloud Native&#xff09;是一种构建和运行应用程序的方法&#xff0c;这种方法充分利用了云计算的优势。云原生应用程序是为云环境设计的&#xff0c;通常是在容器中运行&#xff0c;并被设计为在微服务架构中运行&#xff0c;这使得它们能够快速扩展和…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...