政务网站建设 紧急通知,织梦模板首页修改教程,建筑企业资质查询系统,邯郸做网站熊掌号⭐作者#xff1a;别动我的饭 ⭐专栏#xff1a;菜鸟刷题 ⭐标语#xff1a;悟已往之不谏#xff0c;知来者之可追 一.链表内指定区间反转#xff1a;链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)
描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转… ⭐作者别动我的饭 ⭐专栏菜鸟刷题 ⭐标语悟已往之不谏知来者之可追 一.链表内指定区间反转链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)
描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转要求时间复杂度 O(n),空间复杂度O(1) 例如给出的链表为1→2→3→4→5→NULL m2,n4, 返回 1→4→3→2→5→NULL 解题思路
如果只有一个节点或者mn那就直接返回head因为不用反转。如果有多个节点那就需要建立一个哨兵位标记住头节点后续需要移动头节点。然后找到反转位置的前驱节点再将反转位置赋值给head将m到n之间的节点取下来头插就可以达到反转链表的效果。head会随着不断头插向后挪动需要用一个next指针记住head的下一个节点此外要注意好区间范围的控制。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZB1Dlp1l-1679744040656)(C:\Users\羽北冥\AppData\Roaming\Typora\typora-user-images\image-20230325131417710.png)]
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {// write code here//如果只有一个节点或者没有节点就直接返回if(headNULL||head-nextNULL||mn)return head;//如果有多个节点就建立一个哨兵位节点,找到反转位置拿下来头插struct ListNode*tmp(struct ListNode*)malloc(sizeof(struct ListNode));tmp-nexthead;struct ListNode*prevtmp;for(int i1;im;i){prevprev-next;}//将需要反转链表的头部搞给headheadprev-next;for(int jm;jn;j){//将节点取下来头插struct ListNode*nexthead-next;head-nextnext-next;next-nextprev-next;prev-nextnext;}headtmp-next;free(tmp);
return head;}二.从链表中删去总和值为零的连续节点1171. 从链表中删去总和值为零的连续节点 - 力扣LeetCode
描述
给你一个链表的头节点 head请你编写代码反复删去链表中由 总和 值为 0 的连续节点组成的序列直到不存在这样的序列为止。
删除完毕后请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案注意下面示例中的所有序列都是对 ListNode 对象序列化的表示。
示例 1
输入head [1,2,-3,3,1]
输出[3,1]
提示答案 [1,2,1] 也是正确的。解题思路
首先要明确一点这个数组不是绝对有序的因为我当时考虑了哈哈。
核心就是只要前面的数值相加结果等于零那么前面所有的节点都可以舍弃。但是你直接从零位置开始累加的话不一定会得到前缀和能为零所以这里可以考虑使用嵌套循环也就是说如果从第一个位置累加不能为零那么就从第二个位置再累加一次。直接走完所有的节点都不能累加为零就说明所有的数都是正数。
struct ListNode* removeZeroSumSublists(struct ListNode* head){struct ListNode*phead(struct ListNode*)malloc(sizeof(struct ListNode));phead-nexthead;//用双指针嵌套循环struct ListNode*curphead;struct ListNode*currcur-next;int sum0;while(cur){sum0;//这里必须在更新一下保证第二次循环不被影响currcur-next;//这里怎么能不更新currwhile(curr){sumcurr-val;if(sum0){cur-nextcurr-next;//不释放节点直接更新cur位置 }currcurr-next;}curcur-next;}return phead-next;
}三.链表求和面试题 02.05. 链表求和 - 力扣LeetCode
描述
给定两个用链表表示的整数每个节点包含一个数位。这些数位是反向存放的也就是个位排在链表首部。编写函数对这两个整数求和并用链表形式返回结果。
示例
输入(7 - 1 - 6) (5 - 9 - 2)即617 295
输出2 - 1 - 9即912解题思路
我最开始想着设定两个变量然后分别循环遍历两个链表将两个链表中得到的值存储给变量n1n2最后两者相加得到sum再对sum做文章。但是这样要走两次循环后面我有思考了一下发现可以直接相加。
除n1和n2以外在设定一个carry变量用来保存进位对于加法来说如果这两个数相加大于十则要往前进一位再将这一位加给十位相加得到的结果可以直接将这三个变量相加的结果存放到链表中。需要注意的是链表最后的节点相加可能超过十所以出了循环以后要对carry判断一下如果carry不为零则还要开一个节点存放carry
此外设置一个head和一个tail指针在第一次插入的时候初始化head后续只动tail指针最后用head做返回值。
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{int n1,n20;int carry0,sum0;struct ListNode*headNULL,*tailNULL;while(l1||l2)//如果两个都是空就没有意义了{n1l1?l1-val:0;//如果l1不是空就返回它的值否则返回0n2l2?l2-val:0;sumn1n2carry;if(headNULL){headtail(struct ListNode*)malloc(sizeof(struct ListNode));tail-valsum%10;//sum的值可能超过十我们只需要存sum的个位就行tail-nextNULL;}else{//不是第一次插入,只动尾节点tail-next(struct ListNode*)malloc(sizeof(struct ListNode));tail-next-valsum%10;tailtail-next;tail-nextNULL;}carrysum/10;//更新carry//如果了l1和l2不为空就继续往下走if(l1)l1l1-next;if(l2)l2l2-next;}if(carry0){tail-next(struct ListNode*)malloc(sizeof(struct ListNode));tail-next-valcarry;tail-next-nextNULL;}
return head;
}四.括号的最大嵌套深度1614. 括号的最大嵌套深度 - 力扣LeetCode
描述
如果字符串满足以下条件之一则可以称之为 有效括号字符串valid parentheses string可以简写为 VPS
字符串是一个空字符串 “”或者是一个不为 “(” 或 “)” 的单字符。 字符串可以写为 ABA 与 B 字符串连接其中 A 和 B 都是 有效括号字符串 。 字符串可以写为 (A)其中 A 是一个 有效括号字符串 。 类似地可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)
depth(“”) 0 depth© 0其中 C 是单个字符的字符串且该字符不是 “(” 或者 “)” depth(A B) max(depth(A), depth(B))其中 A 和 B 都是 有效括号字符串 depth(“(” A “)”) 1 depth(A)其中 A 是一个 有效括号字符串 例如“”、“()()”、“()(()())” 都是 有效括号字符串嵌套深度分别为 0、1、2而 “)(” 、“(()” 都不是 有效括号字符串 。
给你一个 有效括号字符串 s返回该字符串的 s 嵌套深度 。
示例 1
输入s (1(2*3)((8)/4))1
输出3
解释数字 8 在嵌套的 3 层括号中。解题思路
这类题目用栈会比较好处理但是C语言如果要使用栈的话又要徒手写一个这样太耗费时间了。所以这里可以采用一个数组通过下标的控制来达到模拟栈的效果。
如果是左括号就将其入栈如果是右括号就将左括号出栈。也就是说如果是 “ ”则size–如果是 “ ”则size以此来表示栈内容量的变化。在不断入栈出栈的过程中size的最大值就是括号的最大嵌套深度因为s是一个有效的括号字符串。
#define MAX(a,b) ((a)(b)?(a):(b))int maxDepth(char * s)
{int lenstrlen(s);int size0;for(int i0;ilen;i){if(s[i]()size;ansMAX(size,ans);if(s[i]))size--;}return ans;
}其实就是拥有左括号数的最大值 最近铃芽之旅上线了不知道各位有没有去看又有多少老铁是一个人去看的斜眼笑昨天我可是特意给你们放了假好吧其实是昨天课太多了而我又被某些题目卡了三个小时所以才没来得及菜鸡流泪。
人们总是高估短期努力能够带来的提升却忽略长期坚持能带来的改变。今天是第六天了你还有坚持吗
