代码随想录第二十三天(一刷C语言)|组合总数组合总数II分割回文串

创作目的:为了方便自己后续复习重点,以及养成写博客的习惯。

一、组合总数

思路:参考carl文档

        定义两个全局变量,二维数组result存放结果集,数组path存放符合条件的结果。(这两个变量可以作为函数参数传入)。题目中给出的参数,集合是candidates, 和目标值是target。终止只有两种情况,sum大于target和sum等于target。

ledcode题目:https://leetcode.cn/problems/combination-sum/

AC代码:

int* path;
int pathTop;
int** ans;
int ansTop;
//记录每一个和等于target的path数组长度
int* length;void backTracking(int target, int index, int* candidates, int candidatesSize, int sum) {//若sum>=target就应该终止遍历if(sum >= target) {//若sum等于target,将当前的组合放入ans数组中if(sum == target) {int* tempPath = (int*)malloc(sizeof(int) * pathTop);int j;for(j = 0; j < pathTop; j++) {tempPath[j] = path[j];}ans[ansTop] = tempPath;length[ansTop++] = pathTop;}return ;}int i;for(i = index; i < candidatesSize; i++) {//将当前数字大小加入sumsum+=candidates[i];path[pathTop++] = candidates[i];backTracking(target, i, candidates, candidatesSize, sum);sum-=candidates[i];pathTop--;}
}int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){//初始化变量path = (int*)malloc(sizeof(int) * 50);ans = (int**)malloc(sizeof(int*) * 200);length = (int*)malloc(sizeof(int) * 200);ansTop = pathTop = 0;backTracking(target, 0, candidates, candidatesSize, 0);//设置返回的数组大小*returnSize = ansTop;*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);int i;for(i = 0; i < ansTop; i++) {(*returnColumnSizes)[i] = length[i];}return ans;
}

二、组合总和II

思路:参考carl文档

        与组合总数的区别在于组合总和II中的candidates 每个数字在每个组合中只能使用一次,需要使用降重处理。

lecode题目:https://leetcode.cn/problems/combination-sum-ii/description/

AC代码:

int* path;
int pathTop;
int** ans;
int ansTop;
//记录ans中每一个一维数组的大小
int* length;
int cmp(const void* a1, const void* a2) {return *((int*)a1) - *((int*)a2);
}void backTracking(int* candidates, int candidatesSize,  int target, int sum, int startIndex) {if(sum >= target) {//若sum等于target,复制当前path进入if(sum == target) {int* tempPath = (int*)malloc(sizeof(int) * pathTop);int j;for(j = 0; j < pathTop; j++) {tempPath[j] = path[j];}length[ansTop] = pathTop;ans[ansTop++] = tempPath;}return ;}int i;for(i = startIndex; i < candidatesSize; i++) {//对同一层树中使用过的元素跳过if(i > startIndex && candidates[i] == candidates[i-1])continue;path[pathTop++] = candidates[i];sum += candidates[i];backTracking(candidates, candidatesSize, target, sum, i + 1);//回溯sum -= candidates[i];pathTop--;}
}int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){path = (int*)malloc(sizeof(int) * 50);ans = (int**)malloc(sizeof(int*) * 100);length = (int*)malloc(sizeof(int) * 100);pathTop = ansTop = 0;//快速排序candidates,让相同元素挨到一起qsort(candidates, candidatesSize, sizeof(int), cmp);backTracking(candidates, candidatesSize, target, 0, 0);*returnSize = ansTop;*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);int i;for(i = 0; i < ansTop; i++) {(*returnColumnSizes)[i] = length[i];}return ans;
}

三、分割回文串

思路:参考carl文档

        考虑切割并判断回文,递归用来纵向遍历,for循环用来横向遍历。切割问题的回溯搜索的过程和组合问题的回溯搜索类似。组合问题与切割问题的区别:

1、组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个.....。

2、切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段.....。

        全局变量数组path存放切割后回文的子串,二维数组result存放结果集。 递归函数参数还需要startIndex,切割过的地方,不能重复切割,和组合问题一样。递归参数需要传入startIndex,表示下一轮递归遍历的起始位置,而startIndex就是切割线。

ledcode题目:https://leetcode.cn/problems/palindrome-partitioning/description/

AC代码:

char** path;
int pathTop;
char*** ans;
int ansTop = 0;
int* ansSize;//将path中的字符串全部复制到ans中
void copy() {//创建一个临时tempPath保存path中的字符串char** tempPath = (char**)malloc(sizeof(char*) * pathTop);int i;for(i = 0; i < pathTop; i++) {tempPath[i] = path[i];}//保存tempPathans[ansTop] = tempPath;//将当前path的长度(pathTop)保存在ansSize中ansSize[ansTop++] = pathTop;
}//判断字符串是否为回文字符串
bool isPalindrome(char* str, int startIndex, int endIndex) {//双指针法:当endIndex(右指针)的值比startIndex(左指针)大时进行遍历while(endIndex >= startIndex) {//若左指针和右指针指向元素不一样,返回Falseif(str[endIndex--] != str[startIndex++])return 0;}return 1;
}//切割从startIndex到endIndex子字符串
char* cutString(char* str, int startIndex, int endIndex) {//开辟字符串的空间char* tempString = (char*)malloc(sizeof(char) * (endIndex - startIndex + 2));int i;int index = 0;//复制子字符串for(i = startIndex; i <= endIndex; i++)tempString[index++] = str[i];//用'\0'作为字符串结尾tempString[index] = '\0';return tempString;
}void backTracking(char* str, int strLen,  int startIndex) {if(startIndex >= strLen) {//将path拷贝到ans中copy();return ;}int i;for(i = startIndex; i < strLen; i++) {//若从subString到i的子串是回文字符串,将其放入path中if(isPalindrome(str, startIndex, i)) {path[pathTop++] = cutString(str, startIndex, i);}//若从startIndex到i的子串不为回文字符串,跳过这一层 else {continue;}//递归判断下一层backTracking(str, strLen, i + 1);//回溯,将path中最后一位元素弹出pathTop--;}
}char*** partition(char* s, int* returnSize, int** returnColumnSizes){int strLen = strlen(s);//因为path中的字符串最多为strLen个(即单个字符的回文字符串),所以开辟strLen个char*空间path = (char**)malloc(sizeof(char*) * strLen);//存放path中的数组结果ans = (char***)malloc(sizeof(char**) * 40000);//存放ans数组中每一个char**数组的长度ansSize = (int*)malloc(sizeof(int) * 40000);ansTop = pathTop = 0;//回溯函数backTracking(s, strLen, 0);//将ansTop设置为ans数组的长度*returnSize = ansTop;//设置ans数组中每一个数组的长度*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);int i;for(i = 0; i < ansTop; ++i) {(*returnColumnSizes)[i] = ansSize[i];}return ans;
}

全篇后记:

        一刷的话基本上做不出来什么题目,照着carl的文档进行理解然后几乎是照着文档将题目AC的,但是这些似乎都不重要,有时候坚持会更好。

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

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

相关文章

【电机控制】PMSM无感foc控制(五)相电流检测及重构 — 单电阻采样

0. 前言 相电流采样再FOC控制中是一个关键的环节&#xff0c;鉴于成本和易用性&#xff0c;目前应用较多的相电流采样方式是分流电阻采样&#xff0c;包括单电阻、双电阻以及三电阻采样法。 本章节先讲解单电阻采样相电流的检测及重构技术&#xff0c;在下一章讲解双电阻和三电…

使用postman请求x5接口

x5接口简介 1.接口样例 {"header"{"appid":"bpmnew_fanwei","sign":"C033162E86E4CADE80C7EB44D68A5AD2","sign_type":"md5","url":"https://oa.mioffice.cn/api/bpm/xm/app/show/tod…

预约按摩小程序有哪些功能特点?

随着科技的飞速发展&#xff0c;我们的生活方式发生了翻天覆地的变化。现在&#xff0c;只需动动手指&#xff0c;就能解决许多生活中的问题。同城预约上门按摩小程序&#xff0c;就是这样一个方便、快捷的解决方案。 在忙碌的生活中&#xff0c;身心疲惫的人们急需一种快速有效…

代码签名证书的作用

代码签名证书也是一种数字证书&#xff0c;它主要用于证明软件的来源和完整性。通过使用这种证书&#xff0c;开发者可以在发布软件时对其代码进行数字签名&#xff0c;以确保用户下载的是未经篡改的原始版本。 代码签名证书通过数字签名技术&#xff0c;为软件添加了一个数字签…

蓝桥杯每日一题2023.12.4

题目描述 竞赛中心 - 蓝桥云课 (lanqiao.cn) 题目分析 本题使用树型DP&#xff0c;蓝桥杯官网出现了一个点的错误&#xff0c;但实际答案是正确的 状态表示&#xff1a;f[u]&#xff1a;在以u为根的子树中包含u的所有联通块的权值的最大值 假设s1&#xff0c;s2,…sk 是u的…

动能资讯 | 智能音箱—万物物联新纽带

音箱市场在过去几年经历了显着的增长&#xff0c;这主要得益于数字音乐的普及和技术创新的推动。随着语音助手技术的发展&#xff0c;智能音箱如Amazon Echo、Google Home、Apple HomePod等逐渐成为市场中的热点。这些音箱不仅提供音频播放功能&#xff0c;还整合了语音识别和智…

【PyTorch】softmax回归

文章目录 1. 模型与代码实现1.1. 模型1.2. 代码实现 2. Q&A 1. 模型与代码实现 1.1. 模型 背景 在分类问题中&#xff0c;模型的输出层是全连接层&#xff0c;每个类别对应一个输出。我们希望模型的输出 y ^ j \hat{y}_j y^​j​可以视为属于类 j j j的概率&#xff0c;然…

关于你对 Zookeeper 的理解

看看普通人和高手是如何回答这个问题的&#xff1f; 普通人 Zookeeper 是一种开放源码的分布式应用程序协调服务 是一个分布式的小文件存储系统 一般对开发者屏蔽分布式应用开发过过程种的底层细节 用来解决分布式集群中应用系统的一致性问题 高手 对于 Zookeeper 的理解…

win10使用copilot(尝试中)

一、 Microsoft account | Sign In or Create Your Account Today – Microsoft 一路next全部点好【1】 二、 查看当前win10的版本&#xff0c;cmd输入命令winver 三、 修改区域为美国 四、更新和安全 Reference 【1】完美&#xff5c;在 Win10 强行开启 Win11 的独有功能…

IDEA2023找不到 Allow parallel run

我的idea版本&#xff1a;2023.1.4 第一步&#xff1a;点击Edit Configrations 第二步&#xff1a;点击Modify options 第三步&#xff1a;勾选Allow multiple instances 最后点击Apply应用一下 ok,问题解决&#xff01;

COMP4121Advanced Algorithms

COMP4121Advanced Algorithms WeChat&#xff1a;yj4399_ Sina Visitor System

使用凌鲨进行内网穿透

为了方便在本地进行开发和调试工作&#xff0c;有时候需要安全地连接内网或Kubernetes集群中的服务。 在net proxy server中可以限制访问用户&#xff0c;也可以设置端口转发的密码。 使用 连接端口转发服务 列出可转发端口 可转发端口是服务端设置的&#xff0c;不会暴露真…

开会做笔记的时候用什么软件比较好?

在工作生涯中&#xff0c;会经历很多大大小小的会议&#xff0c;而如何快速准确记录下会议上重要的内容&#xff0c;成了很多上班族的必修课。在会上做笔记&#xff0c;选择什么样的工具才能事半功倍&#xff0c;成了一个值得深思的问题。而经过一段时间的测评后&#xff0c;我…

策略梯度简明教程

策略梯度方法 (PG&#xff1a;Policy Gradient) 是强化学习 (RL&#xff1a;Reinforcement Learning) 中常用的算法。 1、从库里的本能开始 PG的原理很简单&#xff1a;我们观察&#xff0c;然后行动。人类根据观察采取行动。 引用斯蒂芬库里的一句话&#xff1a; 你必须依靠…

【C++初阶】六、类和对象(初始化列表、static成员、友元、内部类)

相关代码gitee自取&#xff1a; C语言学习日记: 加油努力 (gitee.com) 接上期&#xff1a; 【C初阶】五、类和对象 &#xff08;日期类的完善、流运算符重载函数、const成员、“&”取地址运算符重载&#xff09;-CSDN博客 目录 ​​​​​​​一 . 初始化列表 构造函数…

UiPath学习笔记

文章目录 前言RPA介绍UiPath下载安装组件内容 前言 最近有一个项目的采集调研涉及到了客户端的采集&#xff0c;就取了解了一下RPA和UIPATH&#xff0c;记录一下 RPA介绍 RPA&#xff08;Robotic Process Automation&#xff1a;机器人处理自动化&#xff09;&#xff0c;是…

Ubuntu systemd-analyze命令(系统启动性能分析工具:分析系统启动时间,找出可能导致启动缓慢的原因)

文章目录 Ubuntu systemd-analyze命令剖析目录简介systemd与systemd-analyze工作原理 安装和使用命令参数详解用例与示例显示启动时间&#xff08;systemd-analyze time&#xff09;返回信息解读 列出启动过程中各个服务的启动时间&#xff08;systemd-analyze blame&#xff0…

OpenCvSharp从入门到实践-(06)创建图像

目录 1、创建图像 1.1实例1-创建黑色图像 1.2实例2-创建白色图像 1.3实例3-创建随机像素的雪花点图像 2、图像拼接 2.1水平拼接图像 2.2垂直拼接图像 2.3实例4-垂直和水平两种方式拼接两张图像 在OpenCV中&#xff0c;黑白图像其实就是一个二维数组&#xff0c;彩色图像…

并发编程笔记

1、前言 这篇笔记是我花的20多天跟着⿊⻢的并发编程学习做的笔记&#xff0c;地址是b站 ⿊⻢ 并发编程 &#xff0c;也是我第⼀次 学习并发 编程&#xff0c;所以如果有很多原理讲不清楚的&#xff0c;知识点不全的&#xff0c;也请多多包涵 中间多数图都是直接截⽼师的笔记…

Fiddler抓包工具之fiddler的composer可以简单发送http协议的请求

一&#xff0c;composer的详解 右侧Composer区域&#xff0c;是测试接口的界面&#xff1a; 相关说明&#xff1a; 1.请求方式&#xff1a;点开可以勾选请求协议是get、post等 2.url地址栏&#xff1a;输入请求的url地址 3.请求头&#xff1a;第三块区域可以输入请求头信息…