Leecode刷题C语言之组合总和②
执行结果:通过
执行用时和内存消耗如下:
int** ans;
int* ansColumnSizes;
int ansSize;int* sequence;
int sequenceSize;int** freq;
int freqSize;void dfs(int pos, int rest) {if (rest == 0) {int* tmp = malloc(sizeof(int) * sequenceSize);memcpy(tmp, sequence, sizeof(int) * sequenceSize);ans[ansSize] = tmp;ansColumnSizes[ansSize++] = sequenceSize;return;}if (pos == freqSize || rest < freq[pos][0]) {return;}dfs(pos + 1, rest);int most = fmin(rest / freq[pos][0], freq[pos][1]);for (int i = 1; i <= most; ++i) {sequence[sequenceSize++] = freq[pos][0];dfs(pos + 1, rest - i * freq[pos][0]);}sequenceSize -= most;
}int comp(const void* a, const void* b) {return *(int*)a - *(int*)b;
}int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {ans = malloc(sizeof(int*) * 2001);ansColumnSizes = malloc(sizeof(int) * 2001);sequence = malloc(sizeof(int) * 2001);freq = malloc(sizeof(int*) * 2001);ansSize = sequenceSize = freqSize = 0;qsort(candidates, candidatesSize, sizeof(int), comp);for (int i = 0; i < candidatesSize; ++i) {if (freqSize == 0 || candidates[i] != freq[freqSize - 1][0]) {freq[freqSize] = malloc(sizeof(int) * 2);freq[freqSize][0] = candidates[i];freq[freqSize++][1] = 1;} else {++freq[freqSize - 1][1];}}dfs(0, target);*returnSize = ansSize;*returnColumnSizes = ansColumnSizes;return ans;
}
解题思路:
- 初始化变量:
ans
:一个二维数组,用于存储所有符合条件的组合。ansColumnSizes
:一个一维数组,用于存储每个组合中元素的数量。ansSize
:一个整数,记录当前找到的符合条件的组合数量。sequence
:一个一维数组,用于在深度优先搜索(DFS)过程中临时存储当前的组合。sequenceSize
:一个整数,记录当前sequence
数组中的元素数量。freq
:一个二维数组,用于存储每个候选数字及其出现的次数。freqSize
:一个整数,记录freq
数组中的元素数量。
- 排序候选数组:
- 使用
qsort
函数对候选数组candidates
进行排序,这是为了确保相同的数字相邻,从而方便后续处理。
- 使用
- 处理频率:
- 遍历排序后的候选数组,将每个不同的数字及其出现次数存储在
freq
数组中。如果当前数字与前一个数字不同,则在freq
中添加一个新的条目;如果相同,则增加前一个条目的计数。
- 遍历排序后的候选数组,将每个不同的数字及其出现次数存储在
- 深度优先搜索(DFS):
dfs
函数是递归函数,用于构建所有符合条件的组合。- 参数
pos
表示当前在freq
数组中处理的位置。 - 参数
rest
表示当前还需要多少数字之和才能达到目标数target
。 - 如果
rest
为 0,表示找到了一个符合条件的组合,将其复制到ans
数组中,并记录该组合的大小。 - 如果
pos
等于freqSize
或rest
小于当前freq[pos]
的数字,则回溯。 - 首先尝试不选择当前数字(即,递归调用
dfs(pos + 1, rest)
)。 - 然后计算最多可以选择当前数字的次数(即,
rest / freq[pos][0]
的整数部分,但不能超过freq[pos][1]
),并尝试选择这些次数中的每一种(通过循环)。 - 每次选择一个数字后,递归调用
dfs
,同时减少rest
的值,并更新sequence
和sequenceSize
。 - 回溯时,需要恢复
sequenceSize
的值。
- 返回结果:
- 将找到的组合数量
ansSize
赋值给returnSize
。 - 将
ansColumnSizes
赋值给returnColumnSizes
。 - 返回
ans
数组。
- 将找到的组合数量
这个算法通过排序和频率处理,以及深度优先搜索中的剪枝(如当 rest
小于当前数字时直接回溯),有效地减少了不必要的搜索,从而提高了效率。
相关文章:

Leecode刷题C语言之组合总和②
执行结果:通过 执行用时和内存消耗如下: int** ans; int* ansColumnSizes; int ansSize;int* sequence; int sequenceSize;int** freq; int freqSize;void dfs(int pos, int rest) {if (rest 0) {int* tmp malloc(sizeof(int) * sequenceSize);memcpy(tmp, seque…...

YOLOv8改进,YOLOv8检测头融合DynamicHead,并添加小目标检测层(四头检测),适合目标检测、分割等,全网独发
摘要 作者提出一种新的检测头,称为“动态头”,旨在将尺度感知、空间感知和任务感知统一在一起。如果我们将骨干网络的输出(即检测头的输入)视为一个三维张量,其维度为级别 空间 通道,这样的统一检测头可以看作是一个注意力学习问题,直观的解决方案是对该张量进行全自…...
【PyQt】QThread快速创建多线程任务
pyqt通过QThread快速创建多线程任务 在 PyQt5 中使用多线程时,需要注意 GUI 线程(主线程) 和 工作线程 的分离。PyQt5 的主线程负责处理 GUI 事件,如果在主线程中执行耗时任务,会导致界面卡顿甚至无响应。因此&#x…...
智能码二维码的成本效益分析
以下是智能码二维码的成本效益分析: 成本方面 硬件成本 标签成本:二维码标签本身价格低廉,即使进行大规模应用,成本也相对较低。如在智能仓储中,塑料托盘加二维码方案的标签成本几乎可以忽略不计4。扫描设备成本&…...

企业财务管理系统的需求设计和实现
该作者的原创文章目录: 生产制造执行MES系统的需求设计和实现 企业后勤管理系统的需求设计和实现 行政办公管理系统的需求设计和实现 人力资源管理HR系统的需求设计和实现 企业财务管理系统的需求设计和实现 董事会办公管理系统的需求设计和实现 公司组织架构…...

Springboot集成Swagger和Springdoc详解
Springboot2.x集成Swagger21. Springboot匹配版本2.7.0~2.7.18(其它版本需要自己去调试匹配)2. 首先导入Swagger2匹配的依赖项3. 导入依赖后创建配置文件SwaggerConfig4. Swagger集成完后,接下来接口的配置Springboot3.x集成Springdoc1. Springboot3.x依赖Springdoc配置2. 在…...

类和对象(4)——多态:方法重写与动态绑定、向上转型和向下转型、多态的实现条件
目录 1. 向上转型和向下转型 1.1 向上转型 1.2 向下转型 1.3 instanceof关键字 2. 重写(overidde) 2.1 方法重写的规则 2.1.1 基础规则 2.1.2 深层规则 2.2 三种不能重写的方法 final修饰 private修饰 static修饰 3. 动态绑定 3.1 动态绑…...

ui-automator定位官网文档下载及使用
一、ui-automator定位官网文档简介及下载 AndroidUiAutomator:移动端特有的定位方式,uiautomator是java实现的,定位类型必须写成java类型 官方地址:https://developer.android.com/training/testing/ui-automator.html#ui-autom…...

董事会办公管理系统的需求设计和实现
该作者的原创文章目录: 生产制造执行MES系统的需求设计和实现 企业后勤管理系统的需求设计和实现 行政办公管理系统的需求设计和实现 人力资源管理HR系统的需求设计和实现 企业财务管理系统的需求设计和实现 董事会办公管理系统的需求设计和实现 公司组织架构…...
ESP32和STM32在处理中断方面的区别
为了通俗地讲解ESP32和STM32在处理中断方面的区别,我们可以把它们想象成两个不同的“智能管家”系统,各自负责管理一个家庭(即嵌入式项目)的各种任务。我们将重点放在如何处理突发事件(即中断)上。 ESP32 …...

零售业革命:改变行业的顶级物联网用例
mpro5 产品负责人Ruby Whipp表示,技术进步持续重塑零售业,其中物联网(IoT)正引领这一变革潮流。 研究表明,零售商们正在采用物联网解决方案,以提升运营效率并改善顾客体验。这些技术能够监控运营的各个方面…...
字符串算法笔记
字符串笔记 说到字符串,首先我们要注意的就是字符串的输入以及输出,因为字符串的输入格式以及要求也分为很多种,我们就来说几个比较常见的格式 g e t s gets gets 我们先来说这个函数的含义...
在Ubuntu上用Llama Factory命令行微调Qwen2.5的简单过程
半年多之前写过一个教程:在Windows上用Llama Factory微调Llama 3的基本操作_llama-factory windows-CSDN博客 如果用命令行做的话,前面的步骤可以参考上面这个博客。安装好环境后, 用自我认知数据集微调Lora模块:data/identity.j…...

ThinkPhp伪静态设置后,访问静态资源也提示找不到Controller
ThinkPhp没有配置伪静态时,除了默认的IndexController能访问,其他路由Controller都访问不到,提示404错误。配置了伪静态后就解决了这个问题。 但是当我的ThinkPhp后台项目中有静态资源放在public目录(或子目录)中需要…...

JavaScript赋能智能网页设计
构建AI驱动的实时风格迁移系统 案例概述 本案例将实现一个基于深度学习的实时图像风格迁移系统,通过浏览器端神经网络推理实现以下高级特性: WebAssembly加速的ONNX模型推理 WebGL Shader实现的风格混合算法 WebRTC实时视频流处理 基于Web Workers的…...

基于STM32的阿里云智能农业大棚
目录 前言: 项目效果演示: 一、简介 二、硬件需求准备 三、硬件框图 四、CubeMX配置 4.1、按键、蜂鸣器GPIO口配置 4.2、ADC输入配置 4.3、IIC——驱动OLED 4.4、DHT11温湿度读取 4.5、PWM配置——光照灯、水泵、风扇 4.6、串口——esp8266模…...

80,【4】BUUCTF WEB [SUCTF 2018]MultiSQL
53,【3】BUUCTF WEB october 2019 Twice SQLinjection-CSDN博客 上面这个链接是我第一次接触二次注入 这道题也涉及了 对二次注入不熟悉的可以看看 BUUCTF出了点问题,打不开,以下面这两篇wp作为学习对象 [SUCTF 2018]MultiSQL-CSDN博客 …...
深入探索imi框架:PHP Swoole的高性能协程应用实践
摘要 本文将介绍 imi 框架,这是一个基于 PHP Swoole 的高性能协程应用开发框架。imi 支持 HttpApi、WebSocket、TCP 和 UDP 等多种服务类型,利用 Swoole 的优化技术,使得在处理请求时响应速度远超传统的 php-fpm 方式。通过丰富的代码示例&a…...
【算法篇·更新中】C++秒入门(附练习用题目)
一.二分 1.二分查找 我们来看这样一道题: 有一个保证有序的数组a,它的长度为n。现在我们需要知道这个序列是否含有x。 数据范围:保证n<1e9 我们看到这道题之后,第一时间想到的就是暴力枚举了,可是我们发现直接枚举…...
对神经网络基础的理解
目录 一、《python神经网络编程》 二、一些粗浅的认识 1) 神经网络也是一种拟合 2)神经网络不是真的大脑 3)网络构建需要反复迭代 三、数字图像识别的实现思路 1)建立一个神经网络类 2)权重更新的具体实现 3&am…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...