但是双指针算法虽然是看起来是双重循环,但是实际上每个指针移动的次数是不超过O(n)的,两个指针的总次数不超过O(2n)。将之前的朴素算法优化到O(n)。
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
题目链接:https://leetcode-cn.com/problems/palindrome-partitioning/
数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。 样例: 给出数组[−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就是最大的那个元素。 这样的话代码也是很简洁了:
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
东哥带你手把手撕力扣~ 作者:labuladong 公众号:labuladong 若已授权白名单也必须保留以上来源信息 我有预感本文要火,所以先罗列一下我们号的所有算法套路集锦文章: 数据结构和算法学习指南 动态规划框架套路详解 回溯算法框架套路详解 BFS算法框架套路详解 二分搜索框架套路详解 双指针技巧套路汇总 滑动窗口框架套路详解(本文) 目前来说,以上几篇文章属于我们的镇号之宝,一直被其他人模仿,然而从未被超越。🤔 言归正传,鉴于前文 我作了首诗,保你闭着眼睛也能写对二分查找 的那
题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
一、 A LeetCode Grinding Guide (C++ Version) 作者:谷歌的高畅 背景:作者在美国卡内基梅隆大学攻读硕士学位时,为准备实习秋招,整理 Leetcode 上的题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
力扣题目链接:https://leetcode-cn.com/problems/palindrome-partitioning/
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
这里使用最经典的快慢指针解法,两个指针同时前进,慢指针一次走一步,快指针一次走两步,若链表存在环,则二者一定会有相遇的机会。若不存在环,则由于快指针走的比较快则会先到达空指针。
事实上,当下标 i 可以被 n 整除时,那么有下标 n / i 也可以被 n 整除,因此我们只需要检查 [0, \sqrt(n)] 的范围。
https://leetcode-cn.com/problems/valid-palindrome/description/
双指针是一种思想或一种技巧并不是特别具体的算法。具体就是用两个变量动态存储两个结点,来方便我们进行一些操作。通常用在线性的数据结构中。
链接: https://leetcode.cn/problems/move-zeroes
力扣题目链接:https://leetcode-cn.com/problems/move-zeroes/
这是力扣的 206 题,难度为简单,解题方案有很多种,本文讲解我认为最奇妙的一种。
在思考两数之和解决方法的时候,我们使用了两层循环把所有的结果给求出来,相信读者很快就想到三数之和我就用三个循环,很棒,思路是一样,只是之前的a+b=0,现在的b=c+d了。好了代码呈上。
相信大家已经对双指针法很熟悉了,但是双指针法并不隶属于某一种数据结构,我们在讲解数组,链表,字符串都用到了双指针法,所有有必要针对双指针法做一个总结。
链表的题目,首先考虑使用双指针来解决。根据题目描述,保证了链表中节点互不相同,因此遍历节点,当遇到指定值时,进行删除处理。同时暂存链表的头部节点,方便最后返回。
其实我们已经学习了十天的字符串了,从字符串的定义到库函数的使用原则,从各种反转到KMP算法,相信大家应该对字符串有比较深刻的认识了。
给出一个数组,在数组中找到两个数,使得它们的和最接近目标值但不超过目标值,返回它们的和。
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。
给定一个长度为 n 的整数序列,请找出最长的不包含重复数字的连续子序列,输出它的长度。
示例 1: 输入:s = "ab-cd" 输出:"dc-ba" 示例 2: 输入:s = "a-bC-dEf-ghIj" 输出:"j-Ih-gfE-dCba" 示例 3: 输入:s = "Test1ng-Leet=code-Q!" 输出:"Qedo1ct-eeLg=ntse-T!"
各位,C语言中的指针大家经常会见到用到,C++中由于框架和引用的存在,指针的应用比C少很多,二级指针更是少见,但是今天看到一道面试题,就是有关C++二级指针的,拿出来与大家分享一下,希望对大家的C++学习有帮助。
解题思路: 使用双指针解法,遍历整个字符串,查看当前字符是否是数字? 1、如果当前字符不是数字,则直接加到结果字符串中,继续下一个字符判断 2、如果当前字符是数字,则继续遍历后续字符,直至不是数字字符为止,记录连续数字的起止为止[i,j),然后在[i,j]前后加上*,然后将i = j; 具体的C++实现代码如下:
通常,这种情况下,我们不希望修改原链表的结构。返回一个反序的链表,这就是经典的“后进先出”,我们可以使用栈实现这种顺序。每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,给一个新的链表结构,这样链表就实现了反转。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。
链接: https://leetcode.cn/problems/container-with-most-water/
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9. 示例 2:
读到这道题,最先在脑海中呈现的是字符串的replace方法,毕竟这是一个常用的方法,如方法1的实现。
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 – 1 – 9.
最近两年C用得多了,C++有些生疏,又常常用Python,或者阅读些Java的代码,感觉C的开发者们由于C语言在软件工程上的先天缺陷,导致开发效率不高,所以决定拿出C++来看看用用,准备把libevent封装出一个类ACE的C++实现,首先来复读下C++对象模型吧。要了解new一个object的成本,最主要的就是知道,编译器会给对象分配多少内存,知道C++的对象模型无疑就了解这一点了。
我看到本题的第一想法是双指针法,但是我所构想的逻辑无法达到目的,具体来说我采用前后指针,依次前进,然后满足条件就跳过,这样就导致会忽略许多满足的结构,就让我十分头疼,调试了半天还是不行,甚至想要使用三指针,四指针…服啦!结果表明都是不行的。下面来一起看看正确解法吧
如果某个连续子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。
今天给大家介绍一位我的朋友,他是中科大软件学院的硕士,在去年秋招中斩获了多个互联网大厂的offer,后来他将自己从实习到秋招参加的一百多轮面试进行了总结,希望对即将找工作的大家有所帮助,以下为正文。
给你 n 个非负整数 a1,a2,...,a``n,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
这是力扣的 1679 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。
大家好,我是帅吴,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。
彻底理解C++指针.pdf 推荐阅读pdf版本,原因是从WPS复制粘贴到ChinaUnix后格式有些丢了。
在线提交网址: https://leetcode.com/problems/3sum/
领取专属 10元无门槛券
手把手带您无忧上云