Posts

题目分析 本题需要首先在数组$nums$中选择一个子数组，并对其中所有元素都乘以或除以$k$，之后在整个数组中选出一个最大的子数组总和。 基本思路 贪心(无法通过) 如果要完全按照题目的顺序进行模拟计算，太过复杂，并且选择所有可能的子数组分别计算的时间复杂度太高，因此正难则反，既然要操作以后求最大的子数组总和，那为什么不能先求出原先$nums$中的最大子数组总和，然后再通过乘除$k$得到最后的答案呢？ 理论上这是可以的，如果已知原先$nums$中的最大子数组总和为$maxSum$，那么答案就有两种情况： 当$maxSum>0$时，为了让最终的答案尽可能的大，就需要将其乘以$k$，即答案为$maxSum\times k$； 当$maxSum<0$时，为了让答案尽可能大，则需要将其除以$k$，即答案为$\lceil \frac{maxSum}{k} \rceil$； 因此根据上面的分析可以简单写出以下贪心代码： class Solution: def maxSubarraySum(self, nums: List[int], k: int) -> int: sum_num = nums[0] max_sum_num = nums[0] for i in nums[1:]: if sum_num < 0: sum_num = 0 sum_num += i max_sum_num = max(sum_num,max_sum_num) if max_sum_num > 0: max_sum_num *= k else: max_sum_num = -(abs(max_sum_num)//k) return max_sum_num 可惜的是，在提交之后，上面代码并不能通过全部测试用例，而是卡在了$717/718$的位置上，一直到竞赛结束后才发现那个测试用例长这样： $$ \begin{align} &nums = \underbrace{[-8,5,-8,10,-8,5,-8,10,\dots,-8,5,-8,10]}_{总共100个-8,5,-8,10循环}\\ &k = 5 \end{align} $$按照上面的贪心算法，首先在$nums$中求出最大子数组和，可以得到$maxSum=10$，之后根据判断条件，即可得到最终的答案是$maxSum\times k=50$，但这并不是正确答案，原因在于如果在原数组中先找最大子数组和，寻找过程中会发现单独一个循环节的和是： $$ -8+5-8+10=-1 $$ 但如果将所有数字都按照题目要求的方式整除$k=5$后，上面的四个数字就会变成： $$ \begin{align} -8&\rightarrow -1\\ 5&\rightarrow 1\\ 10&\rightarrow 2\\ \end{align} $$ 于是四个数字相加就变成了： ...

题目分析 本题实际上要求的是满足以下条件的数组数量： 长度为给定值$n$； 每一个值都在限定范围$[l,r]$内； 相邻两个位置的关系从左到右依次增减交替变化。 基本思路 动态规划思路 由于本题要保证的只是数字的大小关系，并没有强制要求按照区间$[l,r]$进行计算，因此为了简便计算，可以将$l$和$r$都减少$l$，使区间变为$[0,r-l]$，这和原有情况是等价的。 本题要求最终的数组长度为$n$，如果此时确定第$n$个数字是$x$，并且确定最后两个数字呈上升趋势，那么就可以确定第$n-1$个数字的取值范围，这样，问题其实变成了一个相似但规模更小的问题。因此可以使用动态规划来解决该问题。仿照上面的分析，可以定义两个动态规划数组如下： $dp0[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈上升趋势的情况下，数组的总数量； $dp1[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈下降趋势的情况下，数组的总数量。 这样，答案就应该是$sum(dp0[n])+sum(dp1[n])$。 那么对于$dp0[i][j]$，由于最后两个数字呈上升趋势，因此可以确定第$i-1$个数字的取值范围为$[l,j-1]$，并且第$i-2$和第$i-1$个数字必须呈下降趋势，故可得递推公式如下： $$ dp0[i][j] = \sum_{k=l}^{j-1}dp1[i-1][k] $$类似的，对于$dp1[i][j]$，也可以得到递推公式如下： $$ dp1[i][j] = \sum_{k=j+1}^{r}dp0[i-1][k] $$根据上面两个公式，即可写出动态规划代码。观察到在递推关系式中用到了区间求和，因此可以用前缀和来优化，当加上前缀和优化时，本题目的第$I$题即可通过了。 矩阵乘法和快速幂优化 观察上面两个递推式子，不难发现，如果将$dp0[i]$和$dp1[i]$合并成一个长度为$2 \times (r-l+1)$的数组$dp[i]$，那么每一个$dp[i]$实际上都可以用同样一个公式从$dp[i-1]$中计算得来，而如果将$dp[i]$看作一个维度是$2 \times (r-l+1)$的空间中的一个坐标，那么上面说的这个递推公式其实可以看作一个坐标变换矩阵，每次只需用同样的矩阵乘以原来的坐标，即可得到新的坐标。 （注意，两个数组经过上述合并后，$dp0$中原有的索引不变，但$dp1$中原有的索引会增加$r-l+1$。为叙述方便，定义$k = r-l+1$） 举个例子，如果$k=2$，也就意味着数组中的每个位置上都只有两个数字可以选，那么根据之前的递推公式可以得到： $dp0[i][0] = 0$; $dp0[i][1]=dp1[i-1][0]$; $dp1[i][0]=dp0[i-1][1]$; $dp1[i][1] = 0$. 而如果将$dp0[i][x]$换成$dp[i][x]$，并将$dp1[i][x]$换成$dp[i][x+k]$，即可得到以下递推式： $dp[i][0] = 0$; $dp[i][1] = dp[i-1][2]$; $dp[i][2] = dp[i-1][1]$; $dp[i][3] = 0$; 因此可以整理出从$dp[i-1]$转成$dp[i]$所需要进行的坐标变换矩阵如下： $$ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $$总结规律，可以发现，对于任意一个$k$值，对应的坐标变换矩阵都可以按照下面方式列写： ...

题目分析 本题要求的是至多选$m$次元素时能够得到的最大总价值，且对于第$i$个元素，每选择它一次，它的价值就会减少$decay[i]$，即从$value[i]$变成$value[i]-decay[i]$。 基本思路 大顶堆模拟 最直接的思路就是模拟选取元素，如果对于每一个位置都将其对应的二元组$(value[i], decay[i])$存入一个大顶堆中，那么在一次选取元素的过程中，直接取出堆顶元素即可最大化当前选取的价值。假设当前弹出的堆顶元素是$(v_i, d_i)$，那么根据题目要求，「选择元素$i$后其价值会减少$decay[i]$」，则需要将更新价值后的该元素,即二元组$(v_i-d_i, d_i)$再次压入堆中。 虽然这是一个暴力模拟方法，但依然可以加入一点优化，即在模拟$m$次选取的$while$循环中，如果某次选择元素时，整个堆中的最大值都小于0了，即可直接退出循环，因为这时再加下去也没有意义了，只会让总和变得更小。 根据上述思路，即可简单写出暴力模拟的代码如下： class Solution: def maxTotalValue(self, value: list[int], decay: list[int], m: int) -> int: n = len(value) hp = [] for i in range(n): heappush(hp, (-value[i], decay[i])) res = 0 modNum = 1_000_000_007 while m: m -= 1 cur, d = heappop(hp) cur = -cur if cur < 0: break res = (res+cur)%modNum heappush(hp, (-(cur-d), d)) return res 确实很简单，但实测只能通过221 / 561个测试用例，因此需要整个优化。 二分查找优化 如果说在整个数组中选至多$m$个元素比较困难，那么可以倒过来想，由于每一个值在选择的过程中它会变得越来越小，因此如果确定了一个最小值的界限，实际上就可以确定一个元素能够被选择的次数。具体操作是这样的： 已知要选的所有值都要大于阈值$X$，且对于元素$i$，它初始值是$v_i$，每选择它一次值就会减少$d_i$； 那么能够减少$d_i$的次数就是：$cnt=\lfloor \frac{v_i-X-1}{d_i} \rfloor$；（其中-1是为了保证减少后其值大于$X$） 因此该元素能够被选择的次数就是：$cnt+1$. 综上所述，如果$X$增大，那么总共选择的数量就一定非增(不变或减小)，否则总共选择的数量就一定非减(不变或增大)，即总共选择的数量随$X$的增大呈有序分布状态，因此可以考虑用二分查找的方式寻找一个能够满足总共选择数量小于等于$m$的最小阈值$X$。 ...

题目 在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。 这座城市对这些新建筑有一些规定： 每栋建筑的高度必须是一个非负整数。 第一栋建筑的高度 必须 是 0 。 任意两栋相邻建筑的高度差 不能超过 1 。 除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出，其中 restrictions[i] = [idi, maxHeighti] ，表示建筑 idi 的高度 不能超过 maxHeighti 。 题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在 restrictions 中。 请你返回 最高 建筑能达到的 最高高度 。 思路 每一个限制都有可能影响到所有建筑物的最高高度，因此可以这样考虑： 先向右遍历一遍所有的限制，根据左侧一个限制位置的最高高度即可计算出当前限制位置的最高高度。即，如果位置i左侧最近一个限制的位置是j，且已知j的最高高度为h，那么位置i的最高高度就应该是$h+(i-j)$； 再向左遍历一遍所有的限制，按照同样的方法处理一遍所有的限制位置对应的最高高度，即可得到在所有限制下，每个位置可以达到的最高高度。 得到了每个限制位置可以达到的最高高度后，就需要计算答案了，需要注意的是，答案不仅仅是每个限制位置上的最高高度的最大值，而是每一个位置上可能的最高高度的最大值，因此需在两个已知最大高度的相邻限制位置之间求一个可能的最大高度。 如果两个相邻限制位置i和j对应的最大高度分别为$h_i$和$h_j$，那么假设在它中间的位置上有一个最大的高度best，由于题目限制了任意两栋相邻的建筑高度差最大为1，因此best必须满足以下式子： $$ (best-h_i)+(best-h_j) = j-i $$即可求出best最大为: $$ \frac{j-i+h_i+h_j}{2} $$之后，对于每两个相邻的限制位置都求一个中间的最高高度best的最大值，即可得到答案。 代码 class Solution: def maxBuilding(self, n: int, R: List[List[int]]) -> int: R.sort() R.insert(0, [1,0]) # 为了求所有的最高高度，需要在左右都加上哨兵 if R[-1][0] != n: R.append([n, n-1]) m = len(R) for i in range(1, m): R[i][1] = min(R[i][1], R[i-1][1]+(R[i][0]-R[i-1][0])) for i in range(m-2, 0, -1): R[i][1] = min(R[i][1], R[i+1][1]+(R[i+1][0]-R[i][0])) res = 0 for i in range(m-1): best = (R[i+1][0]-R[i][0]+R[i][1]+R[i+1][1])//2 res = max(res, best) return res

题目分析 如果称一个长度$length$「满足条件」，即表示在$nums$中所有长度为$length$的子数组中存在一个唯一的子数组，那么本题要求的，就是最小的满足条件的长度$length$。 基本思路 分析题目可以发现以下两条性质： 如果一个给定的长度$length$无法满足条件，即该长度对应的所有子数组中没有单独出现的，那么所有小于等于它的长度都一定不满足条件，说明要找的最小长度一定是大于$length$的； 相反，如果一个长度$length$可以满足条件，即存在一个单独出现的长度为$length$的子数组，那么在该长度之下可能还有能够满足条件的长度，结合本题要求最小长度，因此要找的长度一定是小于等于$length$的。 可以发现，只要确定一个长度是否满足条件，即可确定需要的答案究竟大于还是小于这个长度，因此可以想到采用二分查找的方式寻找答案。 思路1：列表模拟计算 根据上述分析可以发现，二分查找的判断函数应判断给出的中间值$mid$是否是一个满足条件的长度，因此最暴力的方式就是：直接用列表模拟找所有长度为$mid$的子数组，并逐个转为tuple类型用哈希表计数（转为tuple是因为list类型无法直接在哈希表里当作键来计数），其中列表维护长度为$mid$的子数组，即可采用滑动窗口的方式维护。代码很简单直观，如下： def check(mid): cur = [] tot = defaultdict(int) for i in range(n): cur.append(nums[i]) if i < mid-1: continue tp = tuple(cur) tot[tp] += 1 cur.pop(0) return 1 in tot.values() 不过上面代码中，list转tuple以及pop操作的空间复杂度都很高，最坏情况下单单$tot$中存储值的数量都会逼近$O(n^2)$，因此最终上述代码超内存。 思路2：列表哈希化处理 既然用列表计数会超内存，那么就需要想将列表压缩的方法。可以发现，如果将列表压缩成一个数字，那么空间复杂度将大大降低，因此这里可以借鉴哈希化的方法。 什么叫哈希化？如果要将一个列表哈希化，即意味着用一个特定数字表示该列表。如果要用一个数字$w$代替一个长度为$length$的列表$lst$，则可以使用一个质数$base$，令： $$w = lst[0]\times base^{length-1}+lst[1]\times base^{length-2}+...+lst[length-1]\times base^0$$ 即可使用数字$w$表示列表$lst$。 因此可以定义$w$，表示当前长度为$length$的子数组对应的数字，如果依旧用上述滑动窗口的方式对其增减元素，假设当前要增加的元素是$nums[i]$，那么要删除的元素就是$nums[i-length]$，即可知道$w$的变化如下： $w \rightarrow w\times base$（将每一个元素中$base$的指数都增加1，为新元素腾出位置） $w \rightarrow w-nums[i-length]\times b^{length}$（删除$nums[i-length]$，这里由于上一步将$base$的指数加了1，此处对应的指数就变成了$length$而非原先的$length-1$） $w \rightarrow w+nums[i]$（加上$nums[i]$，此处省略$base^0$） 因此根据上述步骤即可实现元素的增减，从而将所有子数组压缩成一个单独的数字。 实现细节 需要注意的是，如果按照上述的计算方式，当$nums$中的值很大并且$length$很大时，$w$的值就会很大，因此可以使用另一个大质数$mod$来对$w$的值不断取模，从而保证不会超出整数范围，同时减少大数相乘的计算量，减少时间。 同时，按照思路2进行计算时，可以先计算出第一个窗口对应的值，这样，在后面进行增减运算的循环中不会在同一个循环中实现太多功能，增强可读性。 在本题中，如果只用一组$base, mod$数对将每一个子数组进行压缩，不会出现哈希值的冲突，但当数据量增大时，为了防止哈希值的冲突，可以再增加一组$base2,mod2$的值对每一个子数组计算出另一个压缩后的数字，两者同时对应一个子数组，即可降低哈希值冲突的可能性。 （在下面的代码中，我给出了用两组值分别压缩子数组的方式，如果追求运行速度，可以将有关$b2,m2,pow2,w2$的计算全部删除，可以降低运行时间） 复杂度 时间复杂度：$O(n\cdot logn)$ 空间复杂度：$O(n)$ 代码 class Solution: def smallestUniqueSubarray(self, nums: List[int]) -> int: n = len(nums) b1, m1 = 1_000_07, 1_000_000_007 # 第一组数据 b2, m2 = 1_000_09, 1_000_000_009 # 第二组数据 def check(mid): pow1 = pow(b1, mid, m1) pow2 = pow(b2, mid, m2) w1, w2 = 0, 0 for i in range(mid): w1 = (w1*b1+nums[i])%m1 w2 = (w2*b2+nums[i])%m2 # 用第二组数据进行压缩 cnt = defaultdict(int) cnt[(w1, w2)] = 1 for i in range(mid, n): w1 = (w1*b1+nums[i]-nums[i-mid]*pow1)%m1 w2 = (w2*b2+nums[i]-nums[i-mid]*pow2)%m2 # 用第二组数据进行压缩 cnt[(w1, w2)] += 1 for v in cnt.values(): if v == 1: return True return False l, r = 1, n while l<=r: mid = (l+r)//2 if check(mid): r = mid-1 else: l = mid+1 return l