长春火车站进站需要核酸检测吗,做去态网站要学什么语言,好网站具备条件,网站制作和app制作LeetCode笔记#xff1a;Weekly Contest 360 0. 吐槽1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接#xff1a;https://leetcode.com/contest/weekly-contest-360/
0.…LeetCode笔记Weekly Contest 360 0. 吐槽1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接https://leetcode.com/contest/weekly-contest-360/
0. 吐槽
这次的题目真的是一言难尽难倒是不难就是各种特殊情况边界条件得想的很清楚然后代码写起来就很丑完全就是一坨一坨的思路上感觉没啥难度实现上各种复杂……
然后一看出题的公司呵果然又是国内公司真的是感觉每次出现这种思路不复杂但是各种边界条件坑的一逼的题目大都是国内公司出的做完感觉除了浪费时间之外完全学不到东西鸡肋的一逼……
国内公司这个出题的风格真的是完全不明白他们出题的目的是什么……
1. 题目一
给出题目一的试题链接如下
2833. Furthest Point From Origin
1. 解题思路
这一题没啥难度左右符号的数目相减取绝对值然后加上下划线符号的数目即可得到可行走的最远距离。
2. 代码实现
给出python代码实现如下
class Solution:def furthestDistanceFromOrigin(self, moves: str) - int:cnt Counter(moves)return abs(cnt[L] - cnt[R]) cnt[_]提交代码评测得到耗时31ms占用内存16.1MB。
2. 题目二
给出题目二的试题链接如下
2834. Find the Minimum Possible Sum of a Beautiful Array
1. 解题思路
这一题其实和上周的题目2829差不多LeetCode笔记Weekly Contest 359也都是从小的数开始取然后block与其pair的数剩下不足的从target开始依次补足即可。
然后知道取法之后我们就可以优化一下直接用求和公式给出结果了。
2. 代码实现
给出python代码实现如下
class Solution:def minimumPossibleSum(self, n: int, target: int) - int:if n target // 2:return n * (n1) // 2else:m target // 2return m * (m1) // 2 (n-m) * (targettargetn-m-1) // 2提交代码评测得到耗时38ms占用内存16.4MB。
3. 题目三
给出题目三的试题链接如下
2835. Minimum Operations to Form Subsequence With Target Sum
1. 解题思路
这一题就是一个贪婪算法的思路我们首先可以对给出的nums进行统计获得所有 2 n 2^n 2n的个数。
然后我们将target数用 2 n 2^n 2n的求和表示出来即将其用二进制表示出来然后依次看各个位上的数字能否在nums里面找到即可。
而这里说的贪婪算法的思路其实就是我们从小到大依次看target的各个二进制组成
如果这个值直接在nums中存在那么直接取用如果这个值可以用一系列比它的二进制数拼出来那么就用这些更小的数来拼成这个值如果上述两者都不存在那么就找到当前nums中比这个值大的最小的数然后将其拆分到这个值的程度并更新nums如果nums不存在比这个值大的数那么返回-1即可。
2. 代码实现
给出python代码实现如下
class Solution:def minOperations(self, nums: List[int], target: int) - int:cnt [0 for _ in range(32)]for num in nums:idx 0while num ! 1:num num // 2idx 1cnt[idx] 1def is_possible(idx):need 1for i in range(idx, -1, -1):if cnt[i] need:return Trueneed - cnt[i]need * 2return Falseres 0idx 0while target ! 0:if target % 2 ! 0:if is_possible(idx):need 1for i in range(idx, -1, -1):if cnt[i] need:cnt[i] - needbreakneed - cnt[i]cnt[i] 0need * 2else:if all(cnt[i] 0 for i in range(idx1, 32)):return -1i idx 1while cnt[i] 0:i 1cnt[i] - 1for j in range(idx, i):cnt[j] 1res 1delta (target % 2) * pow(2, idx)target target // 2 idx 1return res提交代码评测得到耗时69ms占用内存16.5MB。
4. 题目四
给出题目四的试题链接如下
2836. Maximize Value of Function in a Ball Passing Game
1. 解题思路
这一题其实也不复杂就是实现上麻烦一点。
本质上来说这道题就是找到所有完整路径然后统计一下其中长度为 k k k的所有子路径当中的最大值。
因此事实上问题就拆分成了两步
找到所有的路径在每一条路径当中计算所有走过 k k k步的遍历长度亦即所有长度为 k 1 k1 k1的所有子路径。
关于第一个问题事实上就是一个拓扑序列的问题显然这里所有的路径最后都会进入到一个环当中这里就有两种情况
起点不在环当中也就是先走过一段直线然后进入到一个环当中起点就在环当中也就是整条路径就是一个无限循环的圈
而要找全这两种路径其实也简单首先对于第一种情况显然起点不会出现在receiver当中因此我们对所有receiver当中没出现过的值作为起点分别考察一下即可。
然后对于第二种情况我们只要在处理完了第一种情况之后的剩余点当中逐一考察每一个点作为起点的情况遍历其路径即可。
而每一种遍历方法都一样就是不断地走直到下次出现的点在已走过的路径当中已经出现过即可。
然后我们考察对于一条给定的路径如何求所有长度为 k 1 k1 k1的所有子路径。
这个同样不复杂就是考察以路径上每一个点作为起点时后续连续长度为 k 1 k1 k1的子串但是这里同样有些特殊情况因为最后可能会进入到子环当中因此后面的路径可能就会有循环因此不够的部分我们需要用环来补充然后这部分的操作事实上我们可以用环的长度进行求余来快速处理即我们计算出环需要循环的次数和剩下需要多走的步数然后直接计算即可。
2. 代码实现
给出python代码实现如下
class Solution:def getMaxFunctionValue(self, receiver: List[int], k: int) - int:n len(receiver)status [0 for _ in range(n)]def get_max_value(visited, idx):n len(visited)m n-idxaccums [0] list(accumulate(visited))d k1def get_value(i):if i d n:return accums[id] - accums[i]r id - na, b r // m, r % mreturn accums[-1] - accums[i] a * (accums[-1]-accums[idx]) accums[idxb] - accums[idx]res max(get_value(i) for i in range(n))return resres 0nxt set(receiver)inits [i for i in range(n) if i not in nxt]for i in inits:idx iseen set()visited []while idx not in seen:status[idx] 1seen.add(idx)visited.append(idx)idx receiver[idx]res max(res, get_max_value(visited, visited.index(idx)))for i in range(n):if status[i] 1:continueidx iseen set()visited []while idx not in seen:status[idx] 1seen.add(idx)visited.append(idx)idx receiver[idx]res max(res, get_max_value(visited, visited.index(idx)))return res 提交代码评测得到耗时581ms占用内存38.4MB。
