菜鸟刷题Day6

⭐作者:别动我的饭
⭐专栏:菜鸟刷题
⭐标语:悟已往之不谏,知来者之可追
在这里插入图片描述

一.链表内指定区间反转:链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)

描述

将一个节点数为 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;
}

其实就是拥有左括号数的最大值


最近铃芽之旅上线了不知道各位有没有去看(又有多少老铁是一个人去看的,斜眼笑),昨天我可是特意给你们放了假(好吧,其实是昨天课太多了,而我又被某些题目卡了三个小时所以才没来得及,菜鸡流泪)。

人们总是高估短期努力能够带来的提升,却忽略长期坚持能带来的改变。今天是第六天了,你还有坚持吗?

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何用深度强化学习做单元测试代码生成

设计一个用强化学习来生成单元测试代码的系统需要考虑以下几个方面&#xff1a; Agent&#xff1a;强化学习算法中的智能体&#xff0c;它需要接收当前环境状态&#xff0c;根据策略选择相应的动作并执行。 State&#xff1a;描述当前环境状态的特征。在这个问题中&#xff0c…

电脑长按电源键强行关机,对SSD有伤害吗?SSD 掉盘之殇

说到“按住电源键强制关机”的操作&#xff0c;想必大家都不会陌生&#xff0c;毕竟在电脑蓝屏或者电脑死机的时候&#xff0c;我们总是束手无策。而且&#xff0c;身边的人在遇到同样的情况时&#xff0c;往往都是选择长按电源键强制关机&#xff0c;所以当我们遇到同样的情况…

【算法】回溯法详解

一、概述 回溯法在包含的所有可能解的解空间树中&#xff0c;从根节点出发&#xff0c;按照深度有限的策略进行搜索&#xff0c;对于解空间树的某个结点&#xff0c;如果该节点满足问题的约束条件&#xff0c;则进入该子树继续进行搜索&#xff0c;否则将以该节点为根节点进行…

【算法】一文详解贪心法

一、概述 贪心法将一个复杂问题分解为一系列较为简单的局部最优解&#xff0c;每一步都是对当前解的一个扩展&#xff0c;直到获得问题的完全解。贪心法的典型应用时求解最优化问题&#xff0c;而且即使是非最优解&#xff0c;最终得出的解也和最优解比较近似 1.1 贪心法设计…

【多线程】常见的锁策略

✨个人主页&#xff1a;bit me&#x1f447; ✨当前专栏&#xff1a;Java EE初阶&#x1f447; ✨每日一语&#xff1a;老当益壮&#xff0c;宁移白首之心&#xff1b;穷且益坚&#xff0c;不坠青云之志。 目 录&#x1f3f3;️一. 乐观锁 vs 悲观锁&#x1f3f4;二. 普通的互斥…

清晰概括:进程与线程间的区别的联系

相关阅读&#xff1a; &#x1f517;通俗简介&#xff1a;操作系统之进程的管理与调度&#x1f517;如何使用 jconsole 查看Java进程中线程的详细信息&#xff1f; 目录 一、进程与线程 1、进程 2、线程 二、进程与线程之间的区别和联系 1、区别 2、联系 一、进程与线程 …

程序员接私活一定要知道的事情,我走的弯路你们都别走了

文章目录前言一、程序员私活的种类1.兼职职位众包2.自由职业者驻场3.项目整包二、这3种私活可以接1.有熟人2.七分熟的项目3.需求明确的项目三、这3种私活不要接1.主动找上门的中介单2.一味强调项目简单好做3.外行人给你拉的项目四、接单的渠道1.线下渠道2.线上渠道3.比较靠谱的…

计网之HTTP协议和Fiddler的使用

文章目录一. HTTP概述和fidder的使用1. 什么是HTTP2. 抓包工具fidder的使用2.1 注意事项2.2 fidder的使用二. HTTP协议格式1. HTTP请求格式1.1 基本格式1.2 认识URL1.3 方法2. 请求报头关键字段3. HTTP响应格式3.1 基本格式3.2 状态码一. HTTP概述和fidder的使用 1. 什么是HTT…

cpu中缓存简介

一级缓存是什么&#xff1a; 一级缓存都内置在CPU内部并与CPU同速运行&#xff0c;可以有效的提高CPU的运行效率。一级缓存越大&#xff0c;CPU的运行效率越高&#xff0c;但受到CPU内部结构的限制&#xff0c;一级缓存的容量都很小。 CPU缓存&#xff08;Cache Memory&#xf…

【设计模式】23种设计模式之七大原则

【设计模式】23种设计模式之七大原则什么是设计模式的原则1、单一职责原则基本介绍案例分析注意事项2、接口隔离原则基本介绍案例分析代码实现3、依赖倒转原则基本介绍案例分析依赖传递的三种方式注意事项4、里氏替换原则关于继承性的思考和说明基本介绍案例分析5、开闭原则ocp…

冲击蓝桥杯-并查集,前缀和,字符串

目录 前言 一、并查集 1、并查集的合并&#xff08;带路径压缩&#xff09; 2、询问是否为同一个集合 3、例题 二、前缀和 1 、前缀和是什么 2、经典题目 三- 字符串处理 1、字符串的插入 2、字符串转化为int类型 3、字符反转 前言 并查集合前缀&#xff0c;字符串…

Python让ChatGPT全自动改写生成文章教程

ChatGPT是一个在自然语言处理领域非常先进的文本生成模型&#xff0c;它能够产生高质量、连贯的文章。它受到了广泛的关注&#xff0c;因为它可以自动生成大量的文本&#xff0c;从而减轻了人工写作的负担。怎么使用chatgpt批量改写文章&#xff1f;最简单的方式就是找到一家接…

「Vue面试题」vue要做权限管理该怎么做?如果控制到按钮级别的权限怎么做?

文章目录一、是什么二、如何做接口权限路由权限控制菜单权限方案一方案二按钮权限方案一方案二小结参考文章一、是什么 权限是对特定资源的访问许可&#xff0c;所谓权限控制&#xff0c;也就是确保用户只能访问到被分配的资源 而前端权限归根结底是请求的发起权&#xff0c;…

刷题之最长公共/上升子序列问题

目录 一、最长公共子序列问题&#xff08;LCS&#xff09; 1、题目 2、题目解读 ​编辑 3、代码 四、多写一题 五、应用 二、最长上升子序列问题&#xff08;LIS&#xff09; 1、题目 2、题目解读 3、代码 四、多写一道 Ⅰ、题目解读 Ⅱ、代码 一、最长公共子序列问题&…

刷题训练营之栈与队列

文章目录前言一、用队列实现栈1.题目介绍2.思路3.代码二、用栈实现队列1.题目介绍2.思路3.代码前言 本题是在栈与队列的基础上&#xff0c;为巩固两者而出的题&#xff0c;所以基本是在实现了栈与队列的基础上做的&#xff0c;如果没有栈与队列的基础&#xff0c;请看我之前的…

Nginx的漏洞浮现

本文参考https://vulhub.org/#/environments/nginx/nginx_parsing_vulnerability/环境搭建均是采用docker拉取环境请移步到参考。一、Nginx的配置错误案列1. CRLF注入漏洞配置错误文件error1.confrootubuntu-virtual-machine:/vulhub/vulhub-master/nginx/insecure-configurati…

数据结构中的堆

一、树的重要知识点 节点的度&#xff1a;一个节点含有的子树的个数称为该节点的度&#xff08;有几个孩子&#xff09;叶节点或终端节点:度为0的节点称为叶节点&#xff1b;如上图&#xff1a;B、C、H、I...等节点为叶节点&#xff08;0个孩子&#xff09;非终端节点或分支节点…

css实现炫酷充电动画

先绘制一个电池&#xff0c;电池头部和电池的身体 这里其实就是两个div&#xff0c;使用z-index改变层级&#xff0c;电池的身体盖住头部&#xff0c;圆角使用border-radius完成 html部分,完整的css部分在最后 <div class"chargerBox"><div class"ch…

.NET Core 实现Excel的导入导出

.NET Core 使用NPOI实现Excel的导入导出前言NPOI简介一、安装相对应的程序包1.1、在 “管理NuGet程序包” 中的浏览搜索&#xff1a;“NPOI”二、新建Excel帮助类三、调用3.1、增加一个“keywords”模型类&#xff0c;用作导出3.2、添加一个控制器3.3、编写导入导出的控制器代码…

一本通 3.2.1 队列的基本应用

1332&#xff1a;【例2-1】周末舞会 【题目描述】 假设在周末舞会上&#xff0c;男士们和女士们进入舞厅时&#xff0c;各自排成一队。跳舞开始时&#xff0c;依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同&#xff0c;则较长…