滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl + 1, …, numsr - 1, numsr] ,并返回其长度。 如果不存在符合条件的子数组,返回 0 。
LeetCode第3题,“无重复字符的最长子串”,曾经面试的过程中遇到过的一道算法题。通过这道题,我们能够学到算法中一个比较常见的解题方法:滑动窗口算法。
2021-03-30:给定一个整数组成的无序数组arr,值可能正、可能负、可能0。给定一个整数值K,找到arr的所有子数组里,哪个子数组的累加和<=K,并且是长度最大的。返回其长度。
给定一个数组 nums 和一个目标值 k,找到和等于 k 的最长子数组长度。 如果不存在任意一个符合要求的子数组,则返回 0。
本系列旨在介绍编程题中最常见的 16 种模式[1]。对于每一种模式会介绍其基本原理,应用场景以及经典的例题。
我们刷leetcode的时候,经常会遇到滑动窗口类型题目。滑动窗口问题非常经典,也很有技巧性,一般大厂也喜欢问。今天跟大家一起来学习滑动窗口的套路,文章如果有不正确的地方,欢迎大家指出哈,感谢感谢~
其实就是将 purchaseAmount 向最近的 10 的倍数四舍五入,再用 100 减去它。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
2021-03-31:给定一个数组arr,给定一个值v。求子数组平均值小于等于v的最长子数组长度。
经常会有人问,作为前端,你在实际工作中用到过哪些算法,之前我回答是,树和位运算,而最近在学习网络模块,发现了和前端,起码是和网络相关的一种算法,那就是 滑动窗口;
文章目录 1. 两数相加(2) 2. 无重复字符的最长子串(3) 3. 最长回文子串(5) 4. 盛最多水的容器(11) 5. 三数之和(15) 6. 电话号码的字母组合(17) 7. 删除链表的倒数第n个结点(19) 8. 括号生成(22) 9. 下一个排列(31) 10. 搜索旋转排序数组(33) 11. 排序数组中找元素的第一和末位位置(34) 12. 组合总和(39) 13. 全排列(46) 14. 旋转图像(48) 15. 字母异位词分组(49) 16. 跳跃游戏(55) 17. 合并区间(56)
动态规划并不是一种具体的算法,而是一种思想,个人觉得就是缓存+枚举,把求解的问题分成许多阶段或者多个子问题,然后按顺序求解各子问题。前一子问题的解为后一子问题提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
我花了几天时间,从力扣中精选了五道相同思想的题目,来帮助大家解套,如果觉得文章对你有用,记得点赞分享,让我看到你的认可,有动力继续做下去。
如果说如何用算法高效有趣的解决某些问题,那多指针和滑动算法绝对是算其中的佼佼者。这也是笔者最初接触算法时觉得最有意思的一点,因为解决的问题是熟悉的,但配方却完全不同,本章我们从一个简单的交集问题出发,一步步的认识到多指针及滑动窗口解决某些问题时的巧妙与高效,本章主要以解LeetCode里高频题为参考~
1. 两数相加(2)# 给你两个非空的链表,表示两个非负的整数。 它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0开头。 示例 1: 输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807. 示例 2: 输入:l1 = [0], l2 = [0] 输出:[0] 示例 3: 输入:l1 = [9,9,9,9,9,9
要设计一个 O(nlgn) 时间的算法来求一个 n 个数的序列的最长单调递增子序列,我们可以使用动态规划结合二分查找的方法,也就是经典的“最长递增子序列”(Longest Increasing Subsequence, LIS)问题。
这是 LeetCode 上的「395. 至少有K个重复字符的最长子串」,难度为 Medium。
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
给定一个数组和一个目标和,从数组中找两个数字相加等于目标和,输出这两个数字的下标。
上一 part 刚写完二分和滑窗,他们都属于特殊的双指针方法,所以这一 part 直接汇总一下除了特殊的二分和滑窗外的其他双指针写法
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 次。
有两种算法复杂度为O(n*logn)和O(n^2)。在上述算法中,若使用朴素的顺序查找在D1..Dlen查找,由于共有O(n)个元素需要计算,每次计算时的复杂度是O(n),则整个算法的时间复杂度为O(n^2),与原来算法相比没有任何进步。但是由于D的特点(2),在D中查找时,可以使用二分查找高效地完成,则整个算法时间复杂度下降为O(nlogn),有了非常显著的提高。需要注意的是,D在算法结束后记录的并不是一个符合题意的最长上升子序列!算法还可以扩展到整个最长子序列系列问题。 有两种算法复杂度为O(n*logn)和O(n^2) O(n^2)算法分析如下 (a[1]…a[n] 存的都是输入的数) 1、对于a[n]来说,由于它是最后一个数,所以当从a[n]开始查找时,只存在长度为1的不下降子序列; 2、若从a[n-1]开始查找,则存在下面的两种可能性: (1)若a[n-1] < a[n] 则存在长度为2的不下降子序列 a[n-1],a[n]. (2)若a[n-1] > a[n] 则存在长度为1的不下降子序列 a[n-1]或者a[n]。 3、一般若从a[t]开始,此时最长不下降子序列应该是按下列方法求出的: 在a[t+1],a[t+2],…a[n]中,找出一个比a[t]大的且最长的不下降子序列,作为它的后继。 4、为算法上的需要,定义一个数组: d:array [1..n,1..3] of integer; d[t,1]表示a[t] d[t,2]表示从i位置到达n的最长不下降子序列的长度 d[t,3]表示从i位置开始最长不下降子序列的下一个位置 最长不下降子序列的O(n*logn)算法 先回顾经典的O(n^2)的动态规划算法,设A[t]表示序列中的第t个数,F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度,初始时设F[t] = 0(t = 1, 2, …, len(A))。则有动态规划方程:F[t] = max{1, F[j] + 1} (j = 1, 2, …, t – 1, 且A[j] < A[t])。 现在,我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y],满足 (1)x < y < t (2)A[x] < A[y] < A[t] (3)F[x] = F[y] 此时,选择F[x]和选择F[y]都可以得到同样的F[t]值,那么,在最长上升子序列的这个位置中,应该选择A[x]还是应该选择A[y]呢? 很明显,选择A[x]比选择A[y]要好。因为由于条件(2),在A[x+1] … A[t-1]这一段中,如果存在A[z],A[x] < A[z] < a[y],则与选择A[y]相比,将会得到更长的上升子序列。 再根据条件(3),我们会得到一个启示:根据F[]的值进行分类。对于F[]的每一个取值k,我们只需要保留满足F[t] = k的所有A[t]中的最小值。设D[k]记录这个值,即D[k] = min{A[t]} (F[t] = k)。 注意到D[]的两个特点: (1) D[k]的值是在整个计算过程中是单调不上升的。 (2) D[]的值是有序的,即D[1] < D[2] < D[3] < … < D[n]。 利用D[],我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A[t] > D[len],则将A[t]接在D[len]后将得到一个更长的上升子序列,len = len + 1, D[len] = A[t];否则,在D[1]..D[len]中,找到最大的j,满足D[j] < A[t]。令k = j + 1,则有D[j] < A[t] <= D[k],将A[t]接在D[j]后将得到一个更长的上升子序列,同时更新D[k] = A[t]。最后,len即为所要求的最长上升子序列的长度。 在上述算法中,若使用朴素的顺序查找在D[1]..D[len]查找,由于共有O(n)个元素需要计算,每次计算时的复杂度是O(n),则整个算法的时间复杂度为O(n^2),与原来的算法相比没有任何进步。但是由于D[]的特点(2),我们在D[]中查找时,可以使用二分查找高效地完成,则整个算法的时间复杂度下降为O(nlogn),有了非常显著的提高。需要注意的是,D[]在算法结束后记录的并不是一个符合题意的最长上升子序列! 这个算法还可以扩展到整个最长子序列系列问题,整个算法的难点在于二分查找的设计,需要非常小心注意。
在题解一中,当子数组的满足条件时,我们不再需要扩展右指针 j,其实左指针 i 也类似。当存在子数组 [i, j] 满足条件时,我们可以收缩左指针到 [i+1, j],如果子数组依然满足条件,则可以继续记录子数组个数 n - j 个。
给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
在 精读《DOM diff 原理》 一文中,我们提到了 Vue 使用了一种贪心 + 二分的算法求出最长上升子序列,但并没有深究这个算法的原理,因此特别开辟一章详细说明。
面试锦囊系列一直有收到大家的反馈,包括后台内推成功的消息、朋友的同事从创业小公司成功跳到huawei等等,非常高兴小破号的这些整理分享能够真正地帮助到大家
空间复杂度为O(∣Σ∣),其中 Σ 表示字符集(即字符串中可以出现的字符),∣Σ∣ 表示字符集的大小。
无重复字符的最长字串是一道字符串处理算法的题目,在日常编程中,处理字符串是常见任务。用Python来实现leetcode这道算法题,该题目会涉及到一个概念“滑动窗口”。
滑动窗口算法的基本思想是使用双指针(有时也可能使用更多指针)来表示窗口的边界。在每一步中,我们可以根据特定条件来移动窗口的边界,并更新所需的统计信息。
滑动窗口协议(Sliding Window Protocol),属于TCP协议的一种应用,用于网络数据传输时的流量控制,以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认,因此该协议可以加速数据的传输,提高网络吞吐量。
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
他说对不起,说他是乱出的,他可不是乱出的啊,分明是有备而来,先是一个动态规划,再是一个二分答案,最后还搞个博弈论,这好吗?这不好!算法要以和为贵,不要搞窝里斗,谢谢朋友们!
尺取法,顾名思义像尺子那样一段一段取,该算法是滑动窗口的一种,其大思路为首先以某种策略移动右边界,再移动左边界。其效果很像毛毛虫蠕动过程,头先往前跑跑到一定位置,亦巴再往前跑。因此该算法又被称为毛毛虫算法。如下图小姐姐那样
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
这是 LeetCode 上的「1438. 绝对差不超过限制的最长连续子数组」,难度为 Medium。
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
这是力扣的 1004 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。
滑动窗口算法是较为入门题目的算法,一般是一些有规律数组问题的最优解,也就是说,如果一个数组问题可以用动态规划解,但又可以使用滑动窗口解决,那么往往滑动窗口的效率更高。
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2:
字母表的26个字母,每个字母(忽略大小写)按照他们在字母表的顺序,代表一个数,例如:a代表1,h代表8,z代表26
我们理一下思路,大小是由长度和高度决定,如果选 0 到 8 就保证了长度最长,此时大小是 0 号柱子的高度 1 乘以长度 8 。我们如果想面积更大怎么做呢,只能减小长度,增加高度。是左边的柱子向右移动变成 1 号柱子呢?还是右边的柱子向左移动变成 7 号柱子呢?当然是哪边的柱子短就改哪边的!只有这样,高度才有可能增加。
很多读者反应,就算看了前文 动态规划详解,了解了动态规划的套路,也不会写状态转移方程,没有思路,怎么办?本文就借助「最长递增子序列」来讲一种设计动态规划的通用技巧:数学归纳思想。
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2:
数据结构和算法 链表 链表,常见的面试题有写一个链表中删除一个节点的算法、单链表倒转、两个链表找相交的部分,这个一般必须得完全无误的情况下写出来; 给出两个链表的头结点,找出这两个链表的交点。 java 中数组和链表的区别,各自优势 如何设计拥有高效的随机读取能力的的链表(跳表) 设计跳表,跳表插入开销,跳表随机读取过程 给你一个单向链表,给这个链表做K反转,例如 k=3 1 -> 2 -> 3 -> 4 -> 5 -> 6 反转后为:3 -> 2 -> 1 -> 6 -> 5 -> 4 链表长度保证为K的
领取专属 10元无门槛券
手把手带您无忧上云