oa网站开发模板,用什么做网站后台,网站开发干嘛,关于家乡的网页制作教程如题#xff1a;
https://leetcode.cn/problems/longest-increasing-subsequence/description/ 其实常规动态规划的解法就没什么好说的了#xff0c;有意思的是官方放出了一个二分查找的动态规化解法#xff0c;时间复杂度能降到O(nlog(n))#xff0c;但是为什么这样能解
https://leetcode.cn/problems/longest-increasing-subsequence/description/ 其实常规动态规划的解法就没什么好说的了有意思的是官方放出了一个二分查找的动态规化解法时间复杂度能降到O(nlog(n))但是为什么这样能解似乎讲的不是那么清楚。
另外即使是从操作步骤及状态转移函数上来说可能俄罗斯套娃的第二个解里面还说的更清楚一点~~。具体可以去看题解
. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/russian-doll-envelopes/solutions/633231/e-luo-si-tao-wa-xin-feng-wen-ti-by-leetc-wj68/注因为俄罗斯套娃信封问题最终转换成了最长递增子序列问题所以在求最长递增子序列的时候的解法是一模一样的下面的截图就是354.俄罗斯套娃信封问题的官方解二。 这里面最关键的就是“f[j]表示h的前i个元素可以组成的长度为j的最长严格递增子序列的末尾元素的最小值”这一点只要f[j]满足这一条件状态转移的公式也完全是按照这个概念来的并且把所有有定义的f[j]都计算完那么最大的j就是最长严格递增子序列的长度j从0开始则长度就是最大的j加1啦。
一。初步实操
不过这个概念似乎本身就有点绕啊结合一下实际操作更容易理解并且操作过程我稍微加点东西参考的是laboladong的算法笔记里面的patience game纸牌游戏不过他也没有说这么解为什么一定行
数组就用题目里的即nums[0,3,1,6,2,2,7]f函数也可以当成一个列表长度会一点点增长元素值也可能会更新一开始f是空的。
第1步直接把nums第0个元素加到f中即f[0]0 此时的f[0]的含义就是当前长度为1的严格递增子序列的末尾元素的最小值就是0
第2步取nums第1个元素值为3它明显比f[0]0大所以把它放到f[1] 此时的f[1]的含义就是当前长度为2的严格递增子序列的末尾元素的最小值就是3
其实f[j]的含义永远不会变啦只是值可能会变后不缀述。
第3步取nums[2]1它比f[0]0大比f[1]3小所以更新f[1]的值为1。 我为什么把1写在3的下面没有把3擦掉后面自有妙用并且这就是patience game纸牌游戏的玩法。
注意我们更新的位置就是大于等于1的最小值。即f[0, 3]找1的位置自然就是3了。
此处直接多列举些情况
a)f[0, 3, 4]找1找到的位置索引为1从0开始即f[1]3
b)f[0, 3, 4]找4找到的位置索引为2即f[2]4
c)f[0, 3, 4, 4]找4找到的位置索引为2即f[2]4最左边的4哦但是但是注意了f其实不可能出现这种情况正因为我们会在f[0, 3, 4]找4的时候返回位置2所以我们不会再新增一个4只会用4更新4你也可以认为啥也没变所以更新完了仍然是f[0, 3, 4]。我只是在此阐述一下严格的查找逻辑。
d)官方题解里面说先找到小于它的最大值f[j0]然后去更新f[j01]其实是一样的正如c)中所说f中不会有重复值。
第4步: 第5步 第6步 第7步 好结束了f最终为[0, 1, 2, 7]所以最长严格递增子序列的长度就是4。我说“所以”只是按照题解的说明说的并不是在敷衍啊。。。我的解释还在后面
另外你确实也找不到更长的严格递增子序列啦比如0 3 6 70 1 2 7都是4。
你可能会问f最终为[0, 1, 2, 7]是不是代表[0, 1, 2, 7]就是最长严格递增子序列那还真不一定
我立马就给你举个反例比如nums[0,3,1,6,7,2,2]最终画出来还是一样的图 得到的自然是一样的f[0, 1, 2, 7]但是明显[0, 1, 2, 7]不是最长严格递增子序列当然喽此时最长严格递增子序列长度仍然是4只是这次的答案只有[0, 3, 6, 7]
你可能会问那是不是上图的第一行就一定是最长严格递增子序列那仍然还真不一定
我再给你举一个反例比如nums[6,0,3,1,2,2,7]第1行的6 3 2 7明显不是不过提前透露一下判断它是不是的办法十分简单那就是如果它不是它就不是【狗头】。 别急我说“如果它不是”的意思就是直接判断它是不是一个严格递增序列只要它是那它就是最长严格递增子序列。那如果它真不是那我仍然想知道谁是咋办呢办法也很简单就是从右往左从上往下挨个找找到的第一个比右侧小的值就在严格递增序列之中 最后一列那选7肯定没错第3列2也OK第1列3不行往下找1行不是1 hang 是1 xing哦就它了第0列6不行0行就它了所以0 1 2 7必然是最长严格递增子序列并且最终你会发现这么找的算法复杂度还很低它就是O(n)原因很简单上图中的所有元素就是原nums中的元素一共就n个顶多把每个遍历一遍。至于为什么这样找就能找出来下面再详述。
二。进一步分析
先言归正传为什么最长严格递增子序列的长度就是f的最终长度呢
继续研究一下刚才的实操过程再贴一下nums[0,3,1,6,2,2,7]
比如第4步 此时我们已经处理完的元素为0 3 1 6这里面的最长严格递增子序列只有0 1 6或者0 3 6注意上图6放的位置6一定在第2列从第0列开始算3一定在第1列0一定在第0列其实还有一个1它也一定在第1列。虽然这里只有nums的前4个元素但只要把局部想明白了后面所有的元素都是按照这个规则来堆的。
之前说到怎样才能从上图的这堆数字中找出最长严格递增子序列而不是只知道其长度呢
为什么不能简单地根据从左往右的顺序来取原因很简单比如上图的1他虽然处于第1列6处于第2列但这并不代表在nums中它一定在6的左边我立马给你找个反例
nums[0, 3, 6, 1]堆出来的f图跟上图一模一样可是在nums中1明显在6的右边。所以问题就是f图中不能直接看出所有数字在nums中的先后顺序。
如果你能知道摆放这些数字的先后顺序那你就确切地找出所有可能的最长严格递增子序列。
即比如我记住了先放0其次放3再次放1最后放6那自然0 3 6 0 1 6都是ok的当然实际上代码中不会记住这件事。但是有一件事我们是能确定的那就是在放6之前第0列第1列都有人了否则6也跑不到第2列来其实串起来说就是第1列中有一个元素x它一定在6之前就放进来了并且它比6小第0列中有一个元素y它一定在x之前就放进来了并且它比x小。
你可能有几点疑惑
a)为啥一定会有yx6
正如上面所说虽然我记不住f图的堆放顺序但是它一定有这么个过程啊所以y和x是客观存在的只是你不能一眼看出它们是谁。
你要是没明白我再废话几句回忆一下摆放过程6为什么放在第2列因为它比第1列的某个元素x大同时如果6这一列在6之上还有元素z的话那6自然还满足它小于等于z这里的x就是1虽然3也比6小但实际6是跟1比较的1为什么在第1列因为它比第0列的某个元素y大这里的y就是0。
b)你为啥说有一个元素y有一个元素x跟6在同一行的0和3不就是的吗
正如你所问第0行的元素摆放顺序必然是0在3之前3在6之前。但是第0行的元素它未必是一个递增序列比如[6, 0, 1, 3]其f图如下很明显6 1 3它不行0 1 3它才行 等等我问的是同一行你说第0行em....这个坑请见文章第四大点
c)你为啥要强调有这么一个顺序并且yx6
因为y,x,6它就是当前的最长的严格递增子序列啊
别跟上图搞混啊我把对应图再放一下 d)嗯我能明白y x 6一定是一个严格递增子序列了但我想不明白它为什么一定是最长的
如果不能证明这一点那我这帖子仍然是在敷衍。所以到了最关键的步骤了。
另外我们再确认一下你怀疑最长严格递增子序列长度3起码3的下限我们是确定了
现在让我们抛开杂念【狗头】不要管yx具体是什么但是6它是具体的因为它就是我们当前正在摆放的元素如下图现在的实际情况就是我们按照摆放规则6就是摆在了第2列从0列开始但是你怀疑存在某个以当前这个6结尾的严格递增子序列它的长度大于3也就是说存在一个z它能插到6的前面。我们逐个分析有没有这种可能性。 (1)这个序列是y x z 6
z明显在x之后再往图上摆放如果当时x这一列下面没东西末端就是x那么会因为z大于x所以z放到第2列末端。如果x这一列下面还有东西末端是xmin那还是一样啊z更是大于xmin了。
那问题是如果z放到了第2列那再轮到放6的时候它怎么可能仍然放在第2列它只可能放到3列了
(2)同样的道理y z x 6z y x 6都是不行的与上图矛盾。
(3)这个序列是y x 6 z
开玩笑我们现在处理的当前元素是6后面的还没处理到一个个来。我们现在要确定的是因为当前元素摆在第2列从0列开始所以以当前元素结尾的最长严格递增子序列的长度就是3。
所以说其实我们每往图上摆一个元素它摆在哪一列就说明了以这个元素结尾的最长严格递增子序列的长度就是对应的列数从0列开始算的话自然要加1啦
等我们把所有元素都摆完了那么最大的列数自然就是真正的最长严格递增子序列的长度了。
(4)这个序列是y x z1 z2它是4比y x 6长呢并且z1z2在nums中排在6之前
完全有可能比如nums[0,3,1,7,8,6]f图如下6仍然在第3列但是在摆放6的时候当前最长严格递增子序列的长度就已经是4了而不是3. 但是注意我们并没有说错正如第3点中所说是以6结尾的最长严格递增子序列长度为3.
我为什么之前说的时候没有加上“以6结尾”这个前缀我先把之前的图放一下 因为当时的这个图一共就3列并且当时还没有到强调这个前缀的时候。所以重点就是第3点中的那段红字可以再回顾一下它就是证明的关键了
三。上代码
注由于原题只需要计算长度不需要找出序列所以代码中其实跟题解的逻辑是一样的即只更新f值而不是把所有数字摆成牌堆。上述的牌堆只是为了理解原理。
from typing import Listimport bisectclass Solution:def lengthOfLIS(self, nums: List[int]) - int:piles [nums[0]]for i in range(1, len(nums)):if piles[-1] nums[i]:piles.append(nums[i])find_index Solution.bisect_left(piles, nums[i])# find_index bisect.bisect_left(piles, nums[i])piles[find_index] nums[i]return len(piles)staticmethoddef bisect_left(a, x, l0, h-1):if h -1:h len(a)while l h:mid (l h) // 2if x a[mid]:l mid 1else: # elif x a[mid]# 这里为什么不是h mid - 1因为如果找不到x则找大于x的最小值即右边界我们可能是需要的# 为什么把x a[mid]的分支也合到这里面其实只是想跟bisect.bisect_left逻辑保持一致而已即如果存在重复的x则返回最左边的x# 实际上本题不可能有重复的x完全可以在找到x后立马返回能稍微快那么一点点h midreturn lif __name__ __main__:nums [0, 3, 1, 6, 2, 2, 7]print(Solution().lengthOfLIS(nums))
四。那序列到底怎么找出来
前面提过找的方法再总结一下 从右往左找第3列从0列开始就选第0行的7
第2列第0行2小于7OK就它了
第1列第0行3大于2不行第1行1小于2OK就它了
第0列第0行6大于1不行第1行0小于1OK就它了对你可能发现了虽然第1列取的1已经是第1行了但是第0列仍然从第0行开始找
为什么这么找一定行呢
我们换个例子nums[3,8,7,4,5,1] 很明显3 4 5就是最长严格递增子序列这是我们直接看nums得出的。但是在f图上怎么才能确定4是在5之前的呢正如我们之前所说你既然想从f图中获取信息那就请想象5之前一定有一个x比5小这是第一个已知条件。条件二是8绝对在5之前这是无疑的因为它们在第0行。
可惜现在8比5大假设紧接着8下面的那个元素z比5小请问z是不是一定在5之前答案是一定 有图好分析现在把z标出来假设z比5小但是z在nums中就是排在5之后有没有可能没可能假设z真的排在5之后那z下面的4也肯定排在5之后那问题来了5到底是因为谁而来到了第2列从0列开始兄弟你排错队了啊所以如果z比5小它绝对排在5之前。 当然喽我们看z的时候发现它其实是7它虽然排在5之前但它不顶用啊同理的逻辑继续往下找找到的第1个小于5的元素绝对排在5之前。
问题1
你刚才说如果z比5小则它一定在5之前。但你好像没说如果z大于等于5的话它也一定在5之前啊
它当然还是在5之前啦因为它下面绝对有一个比5小的new_z就是那个4啦4在5之前那z还不在5之前
问题2
现在发现4在第2行了从第0行开始那处理第0列的时候还是从第0行开始吗
自然得从第0行开始其实我刚留了一个坑没说明白我说8一定在5之前是因为它们都在第0行注意不是因为它们是同一行而是第0行。0乃创世之初从左到右遵循先创与后创其它行则不然。所以我们只有确定第0行不行的时候才能往下找。
具体到第0列就是我们只有发现3大于等于4的时候才能去找1。当然喽3实际小于4所以我们没证据表明1是行的。我们只有证据表明3是行的。
