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

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;
}

解题思路:

  1. 初始化变量
    • ans:一个二维数组,用于存储所有符合条件的组合。
    • ansColumnSizes:一个一维数组,用于存储每个组合中元素的数量。
    • ansSize:一个整数,记录当前找到的符合条件的组合数量。
    • sequence:一个一维数组,用于在深度优先搜索(DFS)过程中临时存储当前的组合。
    • sequenceSize:一个整数,记录当前 sequence 数组中的元素数量。
    • freq:一个二维数组,用于存储每个候选数字及其出现的次数。
    • freqSize:一个整数,记录 freq 数组中的元素数量。
  2. 排序候选数组
    • 使用 qsort 函数对候选数组 candidates 进行排序,这是为了确保相同的数字相邻,从而方便后续处理。
  3. 处理频率
    • 遍历排序后的候选数组,将每个不同的数字及其出现次数存储在 freq 数组中。如果当前数字与前一个数字不同,则在 freq 中添加一个新的条目;如果相同,则增加前一个条目的计数。
  4. 深度优先搜索(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 的值。
  5. 返回结果
    • 将找到的组合数量 ansSize 赋值给 returnSize
    • 将 ansColumnSizes 赋值给 returnColumnSizes
    • 返回 ans 数组。

这个算法通过排序和频率处理,以及深度优先搜索中的剪枝(如当 rest 小于当前数字时直接回溯),有效地减少了不必要的搜索,从而提高了效率。

相关文章:

Leecode刷题C语言之组合总和②

执行结果:通过 执行用时和内存消耗如下&#xff1a; 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 中使用多线程时&#xff0c;需要注意 GUI 线程&#xff08;主线程&#xff09; 和 工作线程 的分离。PyQt5 的主线程负责处理 GUI 事件&#xff0c;如果在主线程中执行耗时任务&#xff0c;会导致界面卡顿甚至无响应。因此&#x…...

智能码二维码的成本效益分析

以下是智能码二维码的成本效益分析&#xff1a; 成本方面 硬件成本 标签成本&#xff1a;二维码标签本身价格低廉&#xff0c;即使进行大规模应用&#xff0c;成本也相对较低。如在智能仓储中&#xff0c;塑料托盘加二维码方案的标签成本几乎可以忽略不计4。扫描设备成本&…...

企业财务管理系统的需求设计和实现

该作者的原创文章目录&#xff1a; 生产制造执行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. 重写&#xff08;overidde&#xff09; 2.1 方法重写的规则 2.1.1 基础规则 2.1.2 深层规则 2.2 三种不能重写的方法 final修饰 private修饰 static修饰 3. 动态绑定 3.1 动态绑…...

ui-automator定位官网文档下载及使用

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

董事会办公管理系统的需求设计和实现

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

ESP32和STM32在处理中断方面的区别

为了通俗地讲解ESP32和STM32在处理中断方面的区别&#xff0c;我们可以把它们想象成两个不同的“智能管家”系统&#xff0c;各自负责管理一个家庭&#xff08;即嵌入式项目&#xff09;的各种任务。我们将重点放在如何处理突发事件&#xff08;即中断&#xff09;上。 ESP32 …...

零售业革命:改变行业的顶级物联网用例

mpro5 产品负责人Ruby Whipp表示&#xff0c;技术进步持续重塑零售业&#xff0c;其中物联网&#xff08;IoT&#xff09;正引领这一变革潮流。 研究表明&#xff0c;零售商们正在采用物联网解决方案&#xff0c;以提升运营效率并改善顾客体验。这些技术能够监控运营的各个方面…...

字符串算法笔记

字符串笔记 说到字符串,首先我们要注意的就是字符串的输入以及输出,因为字符串的输入格式以及要求也分为很多种,我们就来说几个比较常见的格式 g e t s gets gets 我们先来说这个函数的含义...

在Ubuntu上用Llama Factory命令行微调Qwen2.5的简单过程

半年多之前写过一个教程&#xff1a;在Windows上用Llama Factory微调Llama 3的基本操作_llama-factory windows-CSDN博客 如果用命令行做的话&#xff0c;前面的步骤可以参考上面这个博客。安装好环境后&#xff0c; 用自我认知数据集微调Lora模块&#xff1a;data/identity.j…...

ThinkPhp伪静态设置后,访问静态资源也提示找不到Controller

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

JavaScript赋能智能网页设计

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

基于STM32的阿里云智能农业大棚

目录 前言&#xff1a; 项目效果演示&#xff1a; 一、简介 二、硬件需求准备 三、硬件框图 四、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&#xff0c;【3】BUUCTF WEB october 2019 Twice SQLinjection-CSDN博客 上面这个链接是我第一次接触二次注入 这道题也涉及了 对二次注入不熟悉的可以看看 BUUCTF出了点问题&#xff0c;打不开&#xff0c;以下面这两篇wp作为学习对象 [SUCTF 2018]MultiSQL-CSDN博客 …...

深入探索imi框架:PHP Swoole的高性能协程应用实践

摘要 本文将介绍 imi 框架&#xff0c;这是一个基于 PHP Swoole 的高性能协程应用开发框架。imi 支持 HttpApi、WebSocket、TCP 和 UDP 等多种服务类型&#xff0c;利用 Swoole 的优化技术&#xff0c;使得在处理请求时响应速度远超传统的 php-fpm 方式。通过丰富的代码示例&a…...

【算法篇·更新中】C++秒入门(附练习用题目)

一.二分 1.二分查找 我们来看这样一道题&#xff1a; 有一个保证有序的数组a&#xff0c;它的长度为n。现在我们需要知道这个序列是否含有x。 数据范围&#xff1a;保证n<1e9 我们看到这道题之后&#xff0c;第一时间想到的就是暴力枚举了&#xff0c;可是我们发现直接枚举…...

对神经网络基础的理解

目录 一、《python神经网络编程》 二、一些粗浅的认识 1&#xff09; 神经网络也是一种拟合 2&#xff09;神经网络不是真的大脑 3&#xff09;网络构建需要反复迭代 三、数字图像识别的实现思路 1&#xff09;建立一个神经网络类 2&#xff09;权重更新的具体实现 3&am…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

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

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

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

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;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 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(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出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...