当前位置: 首页 > 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;这使得它们能够快速扩展和…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

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

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

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...