当前位置: 首页 > 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…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...