题目:
思想:
动态规划,找到最小子问题
最小子问题:第i天的最大利润 = max(第i-1天的最大利润, 第i天的价格 - 前i-1天的最小价格)
代码:
1 | class Solution: |
动态规划,找到最小子问题
最小子问题:第i天的最大利润 = max(第i-1天的最大利润, 第i天的价格 - 前i-1天的最小价格)
1 | class Solution: |
看的题解,想法太复杂了。学了一个新的库,bisect,二分查找,可以用来查找插入位置。
bisect_right(a, x)
: 在有序列表a中查找x,返回x应该被插入的位置,这个位置位于a中所有相同元素的右侧。
bisect_left(a, x)
: 在有序列表a中查找x,返回x应该被插入的位置,这个位置位于a中所有相同元素的左侧。
我们可以使用bisect_right来找到所有在该人出现之前开花的花的数量,使用bisect_left来找到所有在该人出现之前凋零的花的数量。
1 | class Solution: |
这是一开始的pop思想,但是时间复杂度太高,400ms,后面改成了列表推导式。
想起了学长说过,pop()的运行时间还行,但是里面一旦加了索引,就会特别慢。
sorted 与 lambda 的用法:
lambda是Python中的匿名函数。在这里,lambda x: (x[1], x[0])定义了一个接受一个元素x(在这种情况下,x是restaurants列表中的一个子列表)并返回一个元组(x[1], x[0])的函数。
这意味着,排序首先基于每个子列表的第二个元素x[1],然后在这个基础上基于第一个元素x[0]。换句话说,它首先按照x[1]进行排序,如果x[1]相同,则按照x[0]进行排序。
1 | while ind < len(restaurants): |
1 | class Solution: |
第一次遇见:’2023/3/14-15:21’
简单的模拟,用字典就做出来了,好像完全没用到双向链表和LRU的思想。。。我有罪,依稀能记得半年前吹着空调做的。
题解就看代码的注释应该就能看懂,不懂的留言我会回复。
1 | class LRUCache: |
1 | class Node: |
第一次遇见:’2023/3/19-16:51’
6323. 将钱分给最多的儿童.md
“————–”
这道题是上半年3月份的时候的周赛题目,题目链接:6323
“————–”
一开始就发现了这个是数学题,奈何写了半天不知道怎么处理最后剩下的钱。
于是写了一个列表,一个孩子一个孩子地给钱。
数学:
如果剩余 0 人,且 money>0,那么必须分给一个已经分到 8 美元的人,
ans 减一。
如果剩余 1 人,且 money=3,为避免分配 4 美元,
那么必须分给一个已经分到 8 美元的人,ans 减一。
其它情况全部给一个人,如果这个人分配到 4 美元,
他再给另一个人 1 美元,这样 ans 不变。
以下为ylb大佬的解释:(2023-9-22更新)
如果 money<children,那么一定存在儿童没有分到钱,返回 −1。
如果 money>8×children,那么有 children−1 个儿童获得了 8 美元,剩下的一个儿童获得了 money−8×(children−1) 美元,返回 children−1。
如果 money=8×children−4,那么有 children−2 个儿童获得了 8 美元,剩下的两个儿童分摊剩下的 12 美元(只要不是 4, 8 美元就行),返回 children−2。
如果,我们假设有 x 个儿童获得了 8 美元,那么剩下的钱为 money−8×x,只要保证大于等于剩下的儿童数 children−x,就可以满足题意。因此,我们只需要求出 x 的最大值,即为答案。
1 | class Solution: |
1 | class Solution: |
1 | class Solution: |
参考了 ylb 大佬的题解,
这道题和打家劫舍1和2的区别在于,这道题是一棵二叉树,而且不能打劫相邻的节点。
所以他的最小子问题是:打劫了当前节点,就不能打劫自己的左右孩子。
如果偷取 root 节点,那么不能偷取其左右子节点,结果为 root.val+lb +rb
;
如果不偷取 root 节点,那么可以偷取其左右子节点,结果为 max(la, lb)+max(ra ,rb)
。
1 | class Solution: |
这一次终于懂一点动态规划了,首先是最小子问题,我一开始认为是考虑从哪里开始,是从第一个还是第二个开始(这刚好是和打家劫舍1的区别)。
但实际上最小子问题还是和打家劫舍1一样:是否打劫当前房子。
首先我们设置一个dp
数组,dp[i]
表示打劫到第i
个房子时的最大收益。
那么我们打劫当前房子后 dp[i] = dp[i-2] + nums[i]
,(因为打劫了当前房子就不能打劫之前的房子),不打劫当前房子 dp[i] = dp[i-1]
。
所以我们可以得到状态转移方程:dp[i] = max(dp[i-2] + nums[i], dp[i-1])
。
最后分类讨论打劫第一个还是第二个开始就行。
1 | class Solution: |