当前位置: 首页 > 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 - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

【iOS】 Block再学习

iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...

简单介绍C++中 string与wstring

在C中&#xff0c;string和wstring是两种用于处理不同字符编码的字符串类型&#xff0c;分别基于char和wchar_t字符类型。以下是它们的详细说明和对比&#xff1a; 1. 基础定义 string 类型&#xff1a;std::string 字符类型&#xff1a;char&#xff08;通常为8位&#xff09…...

用 FFmpeg 实现 RTMP 推流直播

RTMP&#xff08;Real-Time Messaging Protocol&#xff09; 是直播行业中常用的传输协议。 一般来说&#xff0c;直播服务商会给你&#xff1a; ✅ 一个 RTMP 推流地址&#xff08;你推视频上去&#xff09; ✅ 一个 HLS 或 FLV 拉流地址&#xff08;观众观看用&#xff09;…...