大家好,我是袁厨。就是那个酷爱做饭自己考取了厨师资格证的程序员,文章中喜欢放动图的袁厨。
数据范围:节点总数 0≤n≤5000,每个节点的val满足 ∣val∣<=1000
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
今天和大家讲讲,在做算法题时常用的一些技巧。对于平时没用过这些技巧的人,或许你可以考虑试着去看看在实践中能否用的上这些技巧来优化问题的解。
数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些字母作为下标,在遍历的时候,如果字母a遍历到,则arr[a]就可以加1了,即 arr[a]++;
合并两个有序链表,使得合并后的结果仍然是有序的,直观的做法就是从两个链表的首节点开始比较,将其中小的那个链接到新链表之中,(如果不想破坏原链表,那么需要将该节点拷贝一份,然后链接到新链表之中。)然后将该节点对应的原链表的遍历指针向后移动(p = p->next)一直这样比较下去,直到其中某个被遍历完,这时将剩余的那个链表直接链接到新链表后面即可。
这是力扣的 2095 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。
本文为经典算法OJ题练习,大部分题型都有多种思路,每种思路的解法博主都试过了(去网站那里验证)是正确的,大家可以参考!!
数组想必大家都很熟悉,几乎我们每天都会操作它。那么我们就来对比数组来学习链表,首先要明确的是,链表和数组的底层存储结构不同,数组要求存储在一块连续的内存中,而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求降低了,但是随机访问的性能就没有数组好了,需要 O(n) 的时间复杂度。
说起,「链表」在前端领域,可能有些许的陌生。但是,它作为一个传统的数据结构,在一些高阶领域还是有用武之地的。
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
3,需要熟练掌握String/StringBuffer/StringBuilder。
对于算法技巧,之前的文章也写过一些算法技巧,不过相对零散一些,今天我把之前的很多文章总结了下,并且通过增删查改,给大家总结一些常用的算法解题技巧,当然,这些也不是多牛逼的技巧,不过可以让你的代码看起来更加短小精悍,如果你能够充分掌握这些技巧,能够混合运用起来,那么写出来的代码,必然可以让别人拍案叫绝。
数组的排序几乎所有人都很熟悉了,常用的算法插入、冒泡、归并以及快排等都会或多或少依赖于数组可以在O(1)时间随机访问的特点。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。
题中写到数字是按照逆序的方式存储,从进位的角度看,两两节点相加我们是可以直接将进位传递到下一组两两节点相加。
链表存储有序的元素集合,但不同于数组,链表中每个元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的节点(也称为指针或链接)组成,下图展示了一个链表的结构。
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的引用。也可以称之为数据域和指针域。
https://leetcode-cn.com/problems/reverse-linked-list/
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
在链表:听说用虚拟头节点会方便很多?中,我们讲解了链表操作中一个非常总要的技巧:虚拟头节点。
无论是插入,删除,还是翻转等等操作,先把 next 指针用临时变量保存起来,这可以解决 90% 重组链表中指向出错的问题,
本关任务:已知顺序表L中的数据元素递增有序,数据元素类型为int。相关定义如下: #define LIST_INIT_SIZE 20 #define LISTINCREMENT 10 typedef int ElemType; typedef struct { ElemType *elem; int length; int listsize; } SqList; 试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。 函数原型:int insert(SqList &L,ElemType x);
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
好家伙,平时也不推文了,写了技术类文章都不闻不问,写点心理活动都看的起劲。讲真,我通宵加完班那天,做了个实现弹幕的梦,我的天,没把我累屎,最近的研究一下这个
按照题目要求,是将两个有序的链表合并为一个有序的链表。考虑使用双指针的方法进行求解。
链表反转是⼀个出现频率特别⾼的算法题,笔者过去这些年⾯试,⾄少遇到过七⼋次。其中更夸张的是曾经两天写 了三次,上午YY,下午⾦⼭云,第⼆天快⼿。链表反转在各⼤⾼频题排名⽹站也⻓期占领前三。⽐如⽜客⽹上这个 No 1 好像已经很久了。所以链表反转是我们学习链表最重要的问题,没有之⼀。 那为什么反转这么重要呢?因为反转链表涉及结点的增加、删除等多种操作,能⾮常有效考察对指针的驾驭能⼒和 思维能⼒。 另外很多题⽬也都要⽤它来做基础, 例如指定区间反转、链表K个⼀组翻转。还有⼀些在内部的某个过程⽤到了反 转,例如两个链表⽣成相加链表。还有⼀种是链表排序的,也是需要移动元素之间的指针,难度与此差不多。接下 来我们就具体看⼀下每个题⽬。
有的小伙伴说没有学过数据结构,对链表不是特别了解,所以今天我们就来对链表进行一个系统的总结,另外大家如果想提高算法思想的话,我建议还是要系统的学一下数据结构的。
https://leetcode.cn/problems/remove-linked-list-elements/
又精心筛选了一个题目,本来想写一下删除节点的题目,然后发现这个题目更符合目前的节奏,所以先写一下这个题目,明天再给大家写删除节点的题目。大家先不要看我的题解,先自己想一下怎么做。这个这个题目是想让我们找出中间节点,昨天的题目是让我们倒数第K个节点,想一下这两个题目有什么联系呢?
关注公众号【程序员小熊】,后台回复【算法】、【python】或【1024】,即可获取高清无码的经典算法、 python 电子书或三份来自 BAT 大佬的 Leetcode 刷题手册~
来源:力扣(LeetCode) 题目链接:https://leetcode-cn.com/problems/sort-list
这里我们可以使用双指针算法,不妨设为指针 A 和 指针 B。指针 A 先移动 n 次, 指针 B 再开始移动。当 A 到达 null 的时候, 指针 B 的位置正好是倒数第 n。这个时候将 B 的指针指向 B 的下下个指针即可完成删除工作。
滑动窗口算法是较为入门题目的算法,一般是一些有规律数组问题的最优解,也就是说,如果一个数组问题可以用动态规划解,但又可以使用滑动窗口解决,那么往往滑动窗口的效率更高。
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
假如我们定义链表长度为l,则倒数第 n 项,正数第 l-n+1 项,其前一项为第 l-n 项;
下面是程序锅自己对网上发布的 200 道高频面试题进行分类之后的结果。这 200 道,程序锅大概花了 7 个月刷完了,并且差不多每道题都过了好几遍。
作为线性表的两种存储方式 —— 链表和数组,这对相爱相杀的好基友有着各自的优缺点。接下来,我们梳理一下这两种方式。
采取双重遍历肯定是可以解决问题的,但题目要求我们一次遍历解决问题,那我们的思路得发散一下。
👨💻个人主页: 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 🙇♂️ 📒 本文来自专栏: 算法 🌈 算法类型:Hot100题 🌈 每日三题 两数相加 反转链表 回文链表 两数相加 📷 解法一 使用双指针 每次l1、l2指针都向后移动,但是可能存在一个进位然后保存下来 所以当前值每次都是(l1.val+l2.val+进位)%10,而进位值就是(l1.val+l2.val+进位 )/10 class Solution { public ListNo
https://leetcode-cn.com/problems/linked-list-cycle-ii/
给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。
关注下方公众号,分享满满的干货 61. 旋转链表 描述 给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。 解题思路 思考 考虑以下几种情况: 特殊情况 链表为空或只有
这是本公号的第127篇原创。 近期看到一个数据结构题目,翻转链表。动手写了下代码,手生了不少,发现好铁不用也会生锈,大脑也如此。 于是就整体回顾了一下链表的常见操作和数据结构题,整理下分享出来,万一对读者有帮助呢?想必那是极好的!目录如下~
总的来说,双指针技巧在解决单链表相关问题时非常实用,它能够高效地解决许多常见问题,包括合并、分解、寻找节点、判断是否存在环等等。
相信大家已经对双指针法很熟悉了,但是双指针法并不隶属于某一种数据结构,我们在讲解数组,链表,字符串都用到了双指针法,所有有必要针对双指针法做一个总结。
领取专属 10元无门槛券
手把手带您无忧上云