一般情况下,遍历数组(或者字符串)操作,都是采用单指针从前往后或者从后往前依次访问数组(或者字符串)中的元素。
数组(Array)应该是最基础的数据结构之一,它由相同类型的元素组成的集合,并按照一定的顺序存储在内存中。每个元素都有一个唯一的索引,可以用于访问该元素。
数据范围:节点总数 0≤n≤5000,每个节点的val满足 ∣val∣<=1000
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
类似的题目都是由相同的数据去解决的,这说法到底对不对,可能要等多年看看是不是被打脸了。
本文首发于知乎专栏——前端面试题汇总,大家可以通过文章底部的阅读原来来访问原文地址
双指针是一种方法,一种思想一种技巧,也谈不上什么特别的算法,在二分查找中经常使用这个技巧,具体就是用两个变量动态的存储两个或者多个的结点,来方便我们进行一些操作,通常使用在线性结构中,比如说数组或者是链表。 在我们遇到像数组,链表这类数据结构的算法题目的时候,应该要想得到双指针的来解决问题。特别是链表类的题目,经常需要用到两个或多个指针配合来记忆链表上的节点,完成某些操作。链表这种数据结构也是树形结构和图的原型,所以有时候在关于图和树形结构的算法题目中也会用到双指针。
关于 LeetCode 系列有段时间没有逐题更新了 ,还是想到一题一题的刷有些凌乱 。如前段时间的推文所说 ,准备系统的讲讲数据结构相关知识点 。
链表相比较顺序表,它并不会按照线性的顺序存储数据,而是在每个节点里存储到下一个节点的指针,在 JavaScript 中,我们可以这样描述链表中的节点:
相信大家已经对双指针法很熟悉了,但是双指针法并不隶属于某一种数据结构,我们在讲解数组,链表,字符串都用到了双指针法,所有有必要针对双指针法做一个总结。
最最最简单的就是暴力解题,你说两个链表的第一个公共节点,那好,我就挨个遍历就完事了。
第4题号还有二分查找和分治算法,算法比较复杂。那我就接着做下一道题号,第11题号。
一开始,很容易想到用双指针去定位两个相同字符的最远区间,然后使用重叠区间合并的思维去得到最终片段。大方向双指针思路是对的,不过没有优化,所以复杂度较高,但能AC
双指针模式指使用两个一前一后的指针遍历数据结构,直到某个指针触发停止条件。该模式常用于在有序数组或链表中搜索元素对。使用双指针的好处在于和单指针相比,不用去连续遍历整个数组来找出答案,可以带来更好的时间或空间复杂度。
在数组的左右各有一个指针,向中间遍历。指针指向的两数和为s,则s=nums[i]+nums[j],判断s和target的大小:
有效回文串 : https://www.lintcode.com/problem/415/
该题的重要信息:1、不要在超过该数组的长度的位置写入元素(就是不要越界)2、就地修改(就是不能创建新数组)。3、不返回任何东西。
下面是程序锅自己对网上发布的 200 道高频面试题进行分类之后的结果。这 200 道,程序锅大概花了 7 个月刷完了,并且差不多每道题都过了好几遍。
大家好,我是柒八九。这篇文章是我们算法探险系列的第三篇文章。是针对数据结构方面的第二篇。上一篇JS算法探险之整数中我们介绍了关于JS整数的一些基础知识和相关算法题。我们做一个简单的「前情回顾」。
好家伙,平时也不推文了,写了技术类文章都不闻不问,写点心理活动都看的起劲。讲真,我通宵加完班那天,做了个实现弹幕的梦,我的天,没把我累屎,最近的研究一下这个
前一段时间,我们介绍了LeetCode上面的一个经典算法题【两数之和问题】。 这一次,我们把问题做一下扩展,尝试在数组中找到和为“特定值”的三个数。 题目的具体要求是什么呢?给定下面这样一个整型数组: 我们随意选择一个特定值,比如13,要求找出三数之和等于13的全部组合。 由于5+6+2=13, 5+1+7=13,3+9+1=13,所以最终的输出结果如下: 【5, 6,2】 【5, 1,7】 【3, 9,1】 小灰的思路,是把原本的“三数之和问题”,转化成求n次“两数之和问题”。 我们以上
双指针是我们做题中经常用到的思想,所以这个思想在刷题初期是一定要会的。其实我们早就学习过这个方法,那就是我们在学习数据结构的二分查找,下面我们通过二分查找来描述一下这个思想。
双指针算法通常不难,双指针算法是基于暴力解法的优化,它是很好的学习算法的入门问题。
1) 如果int* p,则“1”实际是sizeof(int),也就是p指向的类型大小;
给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。
因为链表一长一短,所以先让长的一方走到和短的一方开始的位置,然后用双指针同时进行遍历,出现第一个相同的节点时就返回对应指针
前言 前段时间我的一个朋友去面了airwallex,最后做了一道算法题,是个三数之和的变种问题,并且被要求把时间复杂度优化到O(n^2)。恰巧这个问题我之前面顺丰时也做过嘞~😉 题目大概是这样的:给定一个整数数组arr跟一个整数n,判断数组里是否存在三个整数加起来和等于整数n,存在的话返回true,不存在的话返回false。 这道题本身不难,我们可以稍微拿出来说一说。而且不用我们找到所有三个数之和等于给定整数n的情况,岂不是美滋滋? 方案一:直接暴力解决 拿到手我第一反应基本上都是先通过暴力循环解决这个问题
数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力
其实双指针算法,并不是一种具体的公式或者范式。而是一种思路。一种节省时间运算的思路。
• 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼
说起,「链表」在前端领域,可能有些许的陌生。但是,它作为一个传统的数据结构,在一些高阶领域还是有用武之地的。
但是双指针算法虽然是看起来是双重循环,但是实际上每个指针移动的次数是不超过O(n)的,两个指针的总次数不超过O(2n)。将之前的朴素算法优化到O(n)。
上一 part 刚写完二分和滑窗,他们都属于特殊的双指针方法,所以这一 part 直接汇总一下除了特殊的二分和滑窗外的其他双指针写法
TwoSum 作为 LeetCode 的第一题存在,想必大家应该对其并不陌生。如果仅仅是看这道题目本身,并不难,思想也特别的简单。
这题的解法有些独特,可能是我太久没接触几何相关的问题了,要是放在初中,应该还是能想出来。
滑动窗口算法是较为入门题目的算法,一般是一些有规律数组问题的最优解,也就是说,如果一个数组问题可以用动态规划解,但又可以使用滑动窗口解决,那么往往滑动窗口的效率更高。
由于12+1 = 13,6+7 = 13,所以最终的输出结果(输出的是下标)如下:
数组想必大家都很熟悉,几乎我们每天都会操作它。那么我们就来对比数组来学习链表,首先要明确的是,链表和数组的底层存储结构不同,数组要求存储在一块连续的内存中,而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求降低了,但是随机访问的性能就没有数组好了,需要 O(n) 的时间复杂度。
这里我们可以使用双指针算法,不妨设为指针 A 和 指针 B。指针 A 先移动 n 次, 指针 B 再开始移动。当 A 到达 null 的时候, 指针 B 的位置正好是倒数第 n。这个时候将 B 的指针指向 B 的下下个指针即可完成删除工作。
之前在美国做访学,日子比较清闲。当时对数据结构和算法几乎一窍不通,便开始在Leetcode上刷算法题,也算是为找工作做准备,经过了一年多,也积累了很多Leetcode题解文章,并在CSDN上开了题解专栏。
领取专属 10元无门槛券
手把手带您无忧上云