代码随想录第二十三天

39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates = [2], target = 1
输出: []

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

思路:

这道题跟昨天的思路很像,但是要注意的是我们要添加合适的退出条件,比如当总和大于目标值时,我们要直接返回,结束递归,同时我们要加上相应的start来寻找元素的正确位置,以免找到重复元素,以及从题目所给数组取元素的所对元素要把它按所取元素的最大元素个数来创造,以免超出数组的界限。

解答:

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
void travelback(int* candidates,int candidatesSize,int target,int* returnSize,int** returnColumnSizes,int*** result,int sum,int combinesize,int* num,int start)
{if(sum == target){(*returnSize)++;(*result) = realloc(*result,sizeof(int*)*(*returnSize));(*result)[(*returnSize)-1] = malloc(sizeof(int)*combinesize);for(int i = 0;i < combinesize;i++){(*result)[(*returnSize)-1][i] = num[i];}*returnColumnSizes = realloc(*returnColumnSizes,sizeof(int*)*(*returnSize));(*returnColumnSizes)[(*returnSize)-1] = combinesize;return;}if(sum > target){return;}for(int i = start;i < candidatesSize;i++){sum += candidates[i];num[combinesize] = candidates[i];travelback(candidates,candidatesSize,target,returnSize,returnColumnSizes,result,sum,combinesize+1,num,i);sum -= candidates[i];}
}
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int sum = 0;int** result = NULL;int combinesize = 0;*returnColumnSizes = NULL;int* num = malloc(sizeof(int)*target);travelback(candidates,candidatesSize,target,returnSize,returnColumnSizes,&result,sum,combinesize,num,0);return result;
}

40.组合总和||

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次

注意:解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

思路:

这道题的思路跟前面都差不多,但是这里最重要的是去重,所以在这里我用了一个qsort函数,把整个数组进行了重新排序,当后一个数组元素和前一个数组元素一样时,我们跳过后一个数组元素,后面就是之前的回溯方法。

解答:

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int compare(const void* a,const void* b)
{return (*(int*)a - *(int*)b);
}
void travelback(int* candidates,int candidatesSize,int target,int* returnSize,int** returnColumnSizes,int*** result,int combinsize,int* num,int start,int sum)
{if(sum == target){(*returnSize)++;*result = realloc(*result,(*returnSize)*sizeof(int*));(*result)[(*returnSize)-1] = malloc(sizeof(int)*combinsize);for(int i = 0;i < combinsize;i++){(*result)[(*returnSize)-1][i] = num[i];}*returnColumnSizes = realloc(*returnColumnSizes,(*returnSize)*sizeof(int));(*returnColumnSizes)[(*returnSize)-1] = combinsize;return;}if(sum > target){return;}for(int i = start;i < candidatesSize;i++){if(i > start && candidates[i] == candidates[i-1]){continue;}sum += candidates[i];num[combinsize] = candidates[i];travelback(candidates,candidatesSize,target,returnSize,returnColumnSizes,result,combinsize+1,num,i+1,sum);sum -= candidates[i];}
}
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int sum = 0;int start = 0;int combinsize = 0;*returnColumnSizes = NULL;int** result = NULL;int* num = malloc(sizeof(int)*target);qsort(candidates,candidatesSize,sizeof(int),compare);travelback(candidates,candidatesSize,target,returnSize,returnColumnSizes,&result,combinsize,num,start,sum);return result;
}

131.分割回文串

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文串。返回 s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

思路:

跟之前的题目一样,只不过我们在判断条件中需要加上一条判断这个字符串数组是否为回文串,如果是,我们就把字符串加进去,如果不是我们继续向下寻找。但是第一次使用跟之前相似的方法时,最终判了超出内存限制。第二种方法则是运用动态规划和创建一个大数组来减少对realloc的使用,同时清理相应的数组来减少内存的使用,最终内存不在超出限制,但是太复杂了,我也不知道怎么做的了。

解答:

第一种方法(超出内存限制)

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
bool isnot(char* s,int start,int end)
{for(int i = start,j = end;i < j;i++,j--){if(s[i] != s[j]){return false;}}return true;
}
void travelback(char* s,int* returnSize,int** returnColumnSizes,char**** result,int start,char** num,int combinesize)
{if(start == strlen(s)){(*returnSize)++;*result = realloc(*result,sizeof(char**)*(*returnSize));(*result)[(*returnSize)-1] = malloc(sizeof(char*)*(combinesize));for(int i = 0;i < combinesize;i++){(*result)[(*returnSize)-1][i] = strdup(num[i]);}*returnColumnSizes = realloc(*returnColumnSizes,sizeof(int)*(*returnSize));(*returnColumnSizes)[(*returnSize)-1] = combinesize;return;}for(int i = start;i < strlen(s);i++){if(isnot(s,start,i)){num[combinesize] = strndup(s+start,i-start+1);travelback(s,returnSize,returnColumnSizes,result,i+1,num,combinesize+1);}}
}
char*** partition(char* s, int* returnSize, int** returnColumnSizes) {*returnSize = 0;*returnColumnSizes = NULL;char*** result = NULL;int start = 0;char** num = malloc(sizeof(char*)*strlen(s));int combinesize = 0;travelback(s,returnSize,returnColumnSizes,&result,start,num,combinesize);return result;
}

第二种方法(gpt)

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
void backtrack(char* s, int len, int start, int* returnSize, int** returnColumnSizes, char**** result, char** path, int pathSize, bool** isPalindrome, int* resultCapacity) {if (start == len) {if (*returnSize >= *resultCapacity) {*resultCapacity *= 2;*result = realloc(*result, sizeof(char**) * (*resultCapacity));*returnColumnSizes = realloc(*returnColumnSizes, sizeof(int) * (*resultCapacity));}(*result)[*returnSize] = malloc(sizeof(char*) * pathSize);for (int i = 0; i < pathSize; i++) {(*result)[*returnSize][i] = strdup(path[i]);}(*returnColumnSizes)[*returnSize] = pathSize;(*returnSize)++;return;}for (int end = start; end < len; end++) {if (isPalindrome[start][end]) {path[pathSize] = strndup(s + start, end - start + 1);backtrack(s, len, end + 1, returnSize, returnColumnSizes, result, path, pathSize + 1, isPalindrome, resultCapacity);free(path[pathSize]);}}
}
char*** partition(char* s, int* returnSize, int** returnColumnSizes) {*returnSize = 0;*returnColumnSizes = NULL;int len = strlen(s);int resultCapacity = 128;char*** result = malloc(sizeof(char**) * resultCapacity);*returnColumnSizes = malloc(sizeof(int) * resultCapacity);bool** isPalindrome = malloc(len * sizeof(bool*));for (int i = 0; i < len; i++) {isPalindrome[i] = malloc(len * sizeof(bool));memset(isPalindrome[i], false, len * sizeof(bool));}for (int end = 0; end < len; end++) {for (int start = 0; start <= end; start++) {if (s[start] == s[end] && (end - start <= 2 || isPalindrome[start + 1][end - 1])) {isPalindrome[start][end] = true;}}}char** path = malloc(len * sizeof(char*));backtrack(s, len, 0, returnSize, returnColumnSizes, &result, path, 0, isPalindrome, &resultCapacity);for (int i = 0; i < len; i++) {free(isPalindrome[i]);}free(isPalindrome);free(path);return result;
}

反思

这个跟昨天的题相差不大,但是分割回文串最开始的思路还好,但是容易超出内存限制,下次做的时候就不用C语言了,用C++。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/466205.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【原创】java+ssm+mysql收纳培训网系统设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…

这款神器,运维绝杀 !!!

项目简介 CrowdSec 是一款开源的、基于社区协作的网络安全防护工具&#xff0c;它通过分析和共享IP信誉数据来对抗恶意行为。该软件不仅支持IPv6&#xff0c;而且相较于传统的Python实现&#xff0c;其采用Go语言编写&#xff0c;运行速度提升了60倍。CrowdSec 利用Grok模式解析…

推荐一款业内领先的建模工具:SAP PowerDesigner

SAP PowerDesigner是一款业内领先的建模工具&#xff0c;帮助您改进商务智能&#xff0c;打造更卓越的信息架构。通过该软件的元数据管理功能&#xff0c;可以构建关键信息资产的 360 度全方位视图&#xff0c;从而使数据管理、BI、数据集成和数据整合工作大获裨益。其分析功能…

Linux(CentOS)运行 jar 包

1、在本地终端运行&#xff0c;关闭终端&#xff0c;程序就会终止 java -jar tlias-0.0.1-SNAPSHOT.jar 发送请求&#xff0c;成功 关闭终端&#xff08;程序也会终止&#xff09; 发送请求&#xff0c;失败 2、在远程终端运行&#xff0c;关闭终端&#xff0c;程序就会终止 …

【JS学习】08. web API-事件进阶

Web APIs - 第3天 进一步学习 事件进阶&#xff0c;实现更多交互的网页特效&#xff0c;结合事件流的特征优化事件执行的效率 掌握阻止事件冒泡的方法理解事件委托的实现原理 事件流 事件流是对事件执行过程的描述&#xff0c;了解事件的执行过程有助于加深对事件的理解&…

Docker + Jenkins + gitee 实现CICD环境搭建

目录 前言 关于Jenkins 安装Jenkins docker中运行Jenkins注意事项 通过容器中的Jenkins&#xff0c;把服务打包到docker进行部署 启动Jenkins 创建第一个任务 前言 CI/CD&#xff08;持续集成和持续交付/持续部署&#xff09;&#xff0c;它可以实现自动化的构建、测试和部署…

150道MySQL高频面试题,学完吊打面试官--关于索引的五道大厂面试题,跳槽面试很重要

前言 本专栏为150道MySQL大厂高频面试题讲解分析&#xff0c;这些面试题都是通过MySQL8.0官方文档和阿里巴巴官方手册还有一些大厂面试官提供的资料。 MySQL应用广泛&#xff0c;在多个开发语言中都处于重要地位&#xff0c;所以最好都要掌握MySQL的精华面试题&#xff0c;这也…

在培训班学网络安全有用吗

在当今数字化时代&#xff0c;网络安全问题日益凸显&#xff0c;成为了企业和个人关注的焦点。随着对网络安全人才需求的不断增长&#xff0c;各种网络安全培训班也如雨后春笋般涌现。然而&#xff0c;在培训班学网络安全真的有用吗? 一、网络安全的重要性与挑战 1. 信息时代的…

SQL Server 2008 R2 详细安装教程及错误解决教程

SQL Server 2008 R2 详细安装教程及错误解决教程 文章目录 SQL Server 2008 R2 详细安装教程及错误解决教程1.装载或解压ISO文件2. 运行setup程序3. 下载并安装.NET Framework3.54.选择全新安装或向现有安装添加功能5.输入秘钥同意条款6.选择安装类型7.设置角色8.功能选择9.实例…

HT32201 2x15W+30W免电感2.1声道D类音频功放

1 特性 ● 输出功率 2x12W24W(VDD14.5V, RL2x8Ω4Ω&#xff0c;THDN1%) 2x15W30W(VDD14.5V,RL2x8Ω4Ω&#xff0c;THDN10%) 2x8W16W(VDD12V,RL2x8Ω4Ω,THDN1%) 2x10W20W(VDD12V,RL2x8Ω4Ω&#xff0c;THDN10%) ● 单电源系统&#xff0c;4.5V-18V宽电压输入范围 ● 超过90…

Unreal5从入门到精通之如何在指定的显示器上运行UE程序

前言 我们有一个设备,是一个带双显示器的机柜,主显示器是一个小竖屏,可以触屏操作,大显示器是一个普通的横屏显示器。我们用这个机柜的原因就是可以摆脱鼠标和键盘,直接使用触屏操作,又可以在大屏观看,非常适合用于教学。 然后我们为这款机柜做了很多个VR项目,包括Uni…

揭秘全向轮运动学:机动艺术与上下位机通信的智慧桥梁

✨✨ Rqtz 个人主页 : 点击✨✨ &#x1f308;Qt系列专栏:点击 &#x1f388;Qt智能车上位机专栏: 点击&#x1f388; 本篇文章介绍的是有关于全向轮运动学分析&#xff0c;单片机与上位机通信C代码以及ROS里程计解算的内容。 目录 大纲 ROS&#xff08;机器人操作系统&…

动态规划理论基础和习题【力扣】【算法学习day.22】

前言 ###我做这类文档一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非常非常高滴&am…

HTTP、WebSocket、gRPC 或 WebRTC:各种协议的区别

在为您的应用程序选择通信协议时&#xff0c;有很多不同的选择。 本文将了解四种流行的解决方案&#xff1a;HTTP、WebSocket、gRPC 和 WebRTC。 我们将通过深入学习其背后原理、最佳用途及其优缺点来探索每个协议。 通信方式在不断改进&#xff1a;变得更快、更方便、更可靠&…

大模型微调技术 --> LoRA 系列之 QLoRA (省资源能手)

QLoRA 1.摘要 作者提出了QLoRA&#xff0c;一种有效的微调方法&#xff0c;可以减少内存使用&#xff0c;足以在单个48 GB GPU上微调 65B 参数模型&#xff0c;同时保留完整的 16位 微调任务性能。 QLoRA 通过冻结的4位量化预训练语言模型将梯度反向传播到低秩适配器&#x…

一种ESB的设计

系统架构 ESB包括&#xff1a; ESB总控服务、业务应用集群、业务消息WEB服务、业务消息日志服务、运维管理平台、业务设计器。如下图所示 ESB总控服务 ESB总控服务承载了各项业务的运维和管理。主要包括&#xff1a; 业务流程的管理ESB内部不同模块间的通讯ESB系统设置和管理…

06 网络编程基础

目录 1.通信三要素 1. IP地址&#xff08;Internet Protocol Address&#xff09; 2. 端口号&#xff08;Port Number&#xff09; 3. 协议&#xff08;Protocol&#xff09; 2.TCP与UDP协议 三次握手&#xff08;Three-Way Handshake&#xff09; 四次挥手&#xff08;…

使用sealos部署的集群在部署metrics-server时日志x509

1、下载文件并进行部署 wget https://github.com/kubernetes-sigs/metrics-server/releases/latest/download/components.yaml2、进行部署 kubectl apply -f components.yaml3、发现问题 pod容器已经启动但是健康检查没有通过 kubectl get pod -n kube-system metrics-server…

定海 - 利用Coraza引擎开发一个防火墙

1. 介绍: Coraza有大量的内置安全规则,包括 OWASP Top 10&#xff0c;同时将错误警报降至最低。CRS保护免受许多常见攻击类别的攻击&#xff0c;包括SQL注入&#xff08;SQLi&#xff09;、跨站点脚本&#xff08;XSS&#xff09;、PHP和Java代码注入、HTTPoxy、Shellshock、脚…

【Linux】冯诺依曼体系、再谈操作系统

目录 一、冯诺依曼体系结构&#xff1a; 1、产生&#xff1a; 2、介绍&#xff1a; 二、再谈操作系统&#xff1a; 1、为什么要管理软硬件资源&#xff1a; 2、操作系统如何进行管理&#xff1a; 3、库函数&#xff1a; 4、学习操作系统的意义&#xff1a; 一、冯诺依曼…