给你 n 个非负整数 a1,a2,...,a``n,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。 样例: 给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为6 要求时间复杂度为O(n) 想了一会并没有特别好的方法,想了一个用双指针的方法,通过了大部分的数据测试,但是还是有不通过的,我也不知道错在哪里,待会贴在下面,先说正确的方法。 思路 先分析下这个问题啊,主要有三种情况: *1. 全部是负数,这就简单了,找到最大的负数就可以了。 *2. 全部是正数,也很简单,应该是把所有的数加起来就可以了。 *3. 有正也有负,最大子数组肯定是正的。 基于这三种情况分析,我们可以采用这样的思路,先设置一个max,把这个数设置为INT_MIN,设置sum作为变量来记录当前得到的字数组的和,一旦sum>max,就可以更新max,这样就能保证max是最大字数组的和,那么字数组如何更新呢,前面说了,如果有正数的话,最后的结果肯定是正的,那么我们遍历数组,把sum先初始化为第一个数,然后,从第二个数开始,如果发现前面的sum是负的,那么就可以把前面的字数组抛弃掉了,以当前的这个数作为新的字数组的起点,如果发现是正的,当前的这个数加入子数组,以此类推,这样就能找到最大字数组了。(每一次遍历的最后更新max)。 这样说来不是很直观,我们可以注意这样一个事实:我们要找的子数组的前面的几个数(不管是几个),和肯定不能是负的,如果是负的,那么去掉岂不是得到的和更大,这样就能理解为什么一旦发现前面的字数组为负的话,就丢掉,如果全负的话这种方式也是适合的,因为每次都会舍弃,sum的值就是当前元素,每次更新max,这样得到的max就是最大的那个元素。 这样的话代码也是很简洁了:
由于我们已经对数组进行了升序排序,所以右边数字大于等于左边数字;另外,我们找数是从数组中的某一点开始往右找,不会往左找,起点的位置也是依次往右走的。以上两条是大前提。
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。
Given two arrays, write a function to compute their intersection.
大家好,我是柒八九。这篇文章是我们算法探险系列的第三篇文章。是针对数据结构方面的第二篇。上一篇JS算法探险之整数中我们介绍了关于JS整数的一些基础知识和相关算法题。我们做一个简单的「前情回顾」。
由题意可知,保证所需的最小船数,意味着每一趟尽可能地搭载两个人,并且他们的重量最接近最大重量,以便后续趟次能够组成两个人。
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
直接按照题目的描述进行,对于数组中的每一个元素,我们找出下雨后水能达到的最高位置,等于两边最大高度较小值减去当前高度的值。
注意:这里要固定一个最左的指针K,可以理解为从[i,j]范围里面选出两个值相加为K指针指向值的相反数 K每次往后移动一次,[i,j]范围都会缩小一个单元 代码:
越刷题越觉得自己进度慢、且要补的知识点越多了,所以加快下刷题进度吧。恰好接下来的 15 和 16 题都与三数之和相关,放到一起来记录下。
滑动窗口算法是较为入门题目的算法,一般是一些有规律数组问题的最优解,也就是说,如果一个数组问题可以用动态规划解,但又可以使用滑动窗口解决,那么往往滑动窗口的效率更高。
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
数组(Array)应该是最基础的数据结构之一,它由相同类型的元素组成的集合,并按照一定的顺序存储在内存中。每个元素都有一个唯一的索引,可以用于访问该元素。
在题解一中存在很多无意义的比较,我们观察到配对的顺序是无关的,因此可以考虑利用有序性优化时间复杂度。
近期已经将python 的大部分内容讲完了, 接下来的一段时间会着重于算法和面试题相关的内容, 确保学有所用, 同时也为准备进入大厂的童靴们做个铺垫, 记得关注哦!!
这题是描述了一个魔法字符串,该字符串完全由数字1和2构成。这个字符串的魔法点在于,如果将该该字符串连续的数字数量进行统计并且构成一个新的字符串,会发现新的字符串与原来的字符串完全相同。 比如1 22 11 2 1 22 1 22 11 2 11 22字符串,经过统计后发现有1个1,2个2,2个1,1个2,1个1,2个2,1个1,2个2,2个1,1个2,2个1,2个2,将统计的数量合并为新的字符串,会发现新的字符串为1 22 11 2 1 22 1 22,和原字符串完全匹配。
之前在美国做访学,日子比较清闲。当时对数据结构和算法几乎一窍不通,便开始在Leetcode上刷算法题,也算是为找工作做准备,经过了一年多,也积累了很多Leetcode题解文章,并在CSDN上开了题解专栏。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
双指针是一种方法,一种思想一种技巧,也谈不上什么特别的算法,在二分查找中经常使用这个技巧,具体就是用两个变量动态的存储两个或者多个的结点,来方便我们进行一些操作,通常使用在线性结构中,比如说数组或者是链表。 在我们遇到像数组,链表这类数据结构的算法题目的时候,应该要想得到双指针的来解决问题。特别是链表类的题目,经常需要用到两个或多个指针配合来记忆链表上的节点,完成某些操作。链表这种数据结构也是树形结构和图的原型,所以有时候在关于图和树形结构的算法题目中也会用到双指针。
示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2]
这道题目初接触时,我能想到的只是穷举,但提交时超出时间限制。直到看到题解中的双指针法,不自觉感叹牛比。这是官方题解中给的说明:
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
基础算法篇——双指针算法 本次我们介绍基础算法中的双指针算法,我们会从下面几个角度来介绍: 双指针简介 双指针基本使用 最长连续不重复字符列 数组元素的目标和 判断子序列 双指针简介 首先我们先来简单介绍一下双指针: 双指针算法就是采用两个变量作为指针放在数组的某个部位来实现复杂度简化 我们来介绍一下双指针的使用场景: 双指针通常用于简化双for循环的场景,将复杂度为O(N^2)变为O(N) 双指针可以用于单个序列中,例如我们之前的快速排序所使用的双指针算法 双指针可以用于多个序列中,例如我们之前的归并排序
说起,「链表」在前端领域,可能有些许的陌生。但是,它作为一个传统的数据结构,在一些高阶领域还是有用武之地的。
本题如果采用暴力法进行破解的话,首先需要找到字符串中的所有子串,然后判断每个子串内的字符是否重复。上述过程需要的复杂度是O(n^3) 。复杂度过高,因此放弃。
今天的题目来源于 LeetCode 中第 42 题:接雨水,hard 级别,目前通过率 50.8% 。
链接:https://leetcode-cn.com/problems/container-with-most-water/
就相当于是数学集合求交集,很容易想到的就是双指针扫描比较判断是否存入结果。对于这样的方式就选择先排序再比较。
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
双指针算法通常不难,双指针算法是基于暴力解法的优化,它是很好的学习算法的入门问题。
清晨的时候,熟睡中的我被咯吱咯吱作响的窗子吵醒,起身一看,窗外正是狂风大作,不一会儿便下起了爆雨,来也快,去也快,不一会儿天亮便放晴了,院子被雨水洗刷得很干净,猛的吸一口气,灌入的是满鼻的泥土芳香。
双指针模式指使用两个一前一后的指针遍历数据结构,直到某个指针触发停止条件。该模式常用于在有序数组或链表中搜索元素对。使用双指针的好处在于和单指针相比,不用去连续遍历整个数组来找出答案,可以带来更好的时间或空间复杂度。
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
链表相比较顺序表,它并不会按照线性的顺序存储数据,而是在每个节点里存储到下一个节点的指针,在 JavaScript 中,我们可以这样描述链表中的节点:
在数组的左右各有一个指针,向中间遍历。指针指向的两数和为s,则s=nums[i]+nums[j],判断s和target的大小:
方法2.c=-(a+b): 确定了a和b,那就可以想两数之和一样,在map中寻找-(a+b),减少一层循环,时间复杂度O(n^2),空间复杂度O(n)。
关于 LeetCode 系列有段时间没有逐题更新了 ,还是想到一题一题的刷有些凌乱 。如前段时间的推文所说 ,准备系统的讲讲数据结构相关知识点 。
【字符串】最长回文子串 ( 蛮力算法 ) 【字符串】最长回文子串 ( 中心线枚举算法 ) 【字符串】最长回文子串 ( 动态规划算法 ) ★ 【字符串】字符串查找 ( 蛮力算法 ) 【字符串】字符串查找 ( Rabin-Karp 算法 )
链接:16. 最接近的三数之和 - 力扣(LeetCode) (leetcode-cn.com)
领取专属 10元无门槛券
手把手带您无忧上云