菜鸟刷题Day6
一.链表内指定区间反转：链表内指定区间反转_牛客题霸_牛客网
描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n),空间复杂度O(1) 例如：给出的链表为1→2→3→4→5→NULL m=2,n=4, 返回 1→4→3→2→5→NULL
解题思路
如果只有一个节点或者m==n，那就直接返回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(head==NULL||head->next==NULL||m==n)
return head;
//如果有多个节点，就建立一个哨兵位节点,找到反转位置拿下来头插
struct ListNode*tmp=(struct ListNode*)malloc(sizeof(struct ListNode));
tmp->next=head;
struct ListNode*prev=tmp;
for(int i=1;i<m;i++)
{
prev=prev->next;
}
//将需要反转链表的头部搞给head
head=prev->next;
for(int j=m;j<n;j++)
{
//将节点取下来头插
struct ListNode*next=head->next;
head->next=next->next;
next->next=prev->next;
prev->next=next;
}
head=tmp->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->next=head;
//用双指针嵌套循环
struct ListNode*cur=phead;
struct ListNode*curr=cur->next;
int sum=0;
while(cur)
{
sum=0;//这里必须在更新一下保证第二次循环不被影响
curr=cur->next;//这里怎么能不更新curr
while(curr)
{
sum+=curr->val;
if(sum==0)
{
cur->next=curr->next;//不释放节点，直接更新cur位置
}
curr=curr->next;
}
cur=cur->next;
}
return phead->next;
}三.链表求和：面试题 02.05. 链表求和 - 力扣（LeetCode）
描述
给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912解题思路
我最开始想着设定两个变量然后分别循环遍历两个链表，将两个链表中得到的值存储给变量n1，n2，最后两者相加得到sum，再对sum做文章。但是这样要走两次循环，后面我有思考了一下发现可以直接相加。
除n1和n2以外，在设定一个carry变量用来保存进位（对于加法来说如果这两个数相加大于十，则要往前进一位，再将这一位加给十位相加得到的结果），可以直接将这三个变量相加的结果存放到链表中。需要注意的是链表最后的节点相加可能超过十，所以出了循环以后要对carry判断一下，如果carry不为零，则还要开一个节点存放carry
此外设置一个head和一个tail指针，在第一次插入的时候初始化head，后续只动tail指针，最后用head做返回值。
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
int n1,n2=0;
int carry=0,sum=0;
struct ListNode*head=NULL,*tail=NULL;
while(l1||l2)//如果两个都是空就没有意义了
{
n1=l1?l1->val:0;//如果l1不是空，就返回它的值否则返回0
n2=l2?l2->val:0;
sum=n1+n2+carry;
if(head==NULL)
{
head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
tail->val=sum%10;//sum的值可能超过十，我们只需要存sum的个位就行
tail->next=NULL;
}
else
{
//不是第一次插入,只动尾节点
tail->next=(struct ListNode*)malloc(sizeof(struct ListNode));
tail->next->val=sum%10;
tail=tail->next;
tail->next=NULL;
}
carry=sum/10;//更新carry
//如果了l1和l2不为空就继续往下走
if(l1)
l1=l1->next;
if(l2)
l2=l2->next;
}
if(carry>0)
{
tail->next=(struct ListNode*)malloc(sizeof(struct ListNode));
tail->next->val=carry;
tail->next->next=NULL;
}
return head;
}四.括号的最大嵌套深度：1614. 括号的最大嵌套深度 - 力扣（LeetCode）
描述
如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
字符串是一个空字符串 “”，或者是一个不为 “(” 或 “)” 的单字符。 字符串可以写为 AB（A 与 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 len=strlen(s);
int size=0;
for(int i=0;i<len;i++)
{
if(s[i]=="(")
size++;
ans=MAX(size,ans);
if(s[i]==")")
size--;
}
return ans;
}其实就是拥有左括号数的最大值
最近铃芽之旅上线了不知道各位有没有去看（又有多少老铁是一个人去看的，斜眼笑），昨天我可是特意给你们放了假（好吧，其实是昨天课太多了，而我又被某些题目卡了三个小时所以才没来得及，菜鸡流泪）。
人们总是高估短期努力能够带来的提升，却忽略长期坚持能带来的改变。今天是第六天了，你还有坚持吗？
腾讯云开发者
