LeetCode笔记:Weekly Contest 360

这篇具有很好参考价值的文章主要介绍了LeetCode笔记:Weekly Contest 360。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  • 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 * (n+1) // 2
        else:
            m = target // 2
            return m * (m+1) // 2 + (n-m) * (target+target+n-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的各个二进制组成:

  1. 如果这个值直接在nums中存在,那么直接取用;
  2. 如果这个值可以用一系列比它的二进制数拼出来,那么就用这些更小的数来拼成这个值;
  3. 如果上述两者都不存在,那么就找到当前nums中比这个值大的最小的数,然后将其拆分到这个值的程度,并更新nums;
  4. 如果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 = 0
            while num != 1:
                num = num // 2
                idx += 1
            cnt[idx] += 1

        def is_possible(idx):
            need = 1
            for i in range(idx, -1, -1):
                if cnt[i] >= need:
                    return True
                need -= cnt[i]
                need *= 2
            return False
        
        res = 0
        idx = 0
        while target != 0:
            if target % 2 != 0:
                if is_possible(idx):
                    need = 1
                    for i in range(idx, -1, -1):
                        if cnt[i] >= need:
                            cnt[i] -= need
                            break
                        need -= cnt[i]
                        cnt[i] = 0
                        need *= 2
                else:
                    if all(cnt[i] == 0 for i in range(idx+1, 32)):
                        return -1
                    i = idx + 1
                    while cnt[i] == 0:
                        i += 1
                    cnt[i] -= 1
                    for j in range(idx, i):
                        cnt[j] += 1
                        res += 1
            delta = (target % 2) * pow(2, idx)
            target = target // 2   
            idx += 1
        return res

提交代码评测得到:耗时69ms,占用内存16.5MB。

4. 题目四

给出题目四的试题链接如下:

  • 2836. Maximize Value of Function in a Ball Passing Game

1. 解题思路

这一题其实也不复杂,就是实现上麻烦一点。

本质上来说,这道题就是找到所有完整路径,然后统计一下其中长度为 k k k的所有子路径当中的最大值。

因此,事实上问题就拆分成了两步:

  1. 找到所有的路径;
  2. 在每一条路径当中,计算所有走过 k k k步的遍历长度,亦即所有长度为 k + 1 k+1 k+1的所有子路径。

关于第一个问题,事实上就是一个拓扑序列的问题,显然,这里所有的路径最后都会进入到一个环当中,这里就有两种情况:

  1. 起点不在环当中,也就是先走过一段直线,然后进入到一个环当中;
  2. 起点就在环当中,也就是整条路径就是一个无限循环的圈;

而要找全这两种路径其实也简单,首先对于第一种情况,显然起点不会出现在receiver当中,因此我们对所有receiver当中没出现过的值作为起点分别考察一下即可。

然后,对于第二种情况,我们只要在处理完了第一种情况之后的剩余点当中逐一考察每一个点作为起点的情况遍历其路径即可。

而每一种遍历方法都一样,就是不断地走直到下次出现的点在已走过的路径当中已经出现过即可。

然后,我们考察对于一条给定的路径,如何求所有长度为 k + 1 k+1 k+1的所有子路径。

这个同样不复杂,就是考察以路径上每一个点作为起点时后续连续长度为 k + 1 k+1 k+1的子串,但是这里同样有些特殊情况,因为最后可能会进入到子环当中,因此后面的路径可能就会有循环,因此不够的部分我们需要用环来补充,然后这部分的操作事实上我们可以用环的长度进行求余来快速处理,即我们计算出环需要循环的次数和剩下需要多走的步数,然后直接计算即可。

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-idx
            accums = [0] + list(accumulate(visited))
            d = k+1
            
            def get_value(i):
                if i + d <= n:
                    return accums[i+d] - accums[i]
                r = i+d - n
                a, b = r // m, r % m
                return accums[-1] - accums[i] + a * (accums[-1]-accums[idx]) + accums[idx+b] - accums[idx]
            
            res = max(get_value(i) for i in range(n))
            return res
        
        res = 0
    
        nxt = set(receiver)
        inits = [i for i in range(n) if i not in nxt]
        for i in inits:
            idx = i
            seen = set()
            visited = []
            while idx not in seen:
                status[idx] = 1
                seen.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:
                continue
            idx = i
            seen = set()
            visited = []
            while idx not in seen:
                status[idx] = 1
                seen.add(idx)
                visited.append(idx)
                idx = receiver[idx]
            res = max(res, get_max_value(visited, visited.index(idx)))
        return res  

提交代码评测得到:耗时581ms,占用内存38.4MB。文章来源地址https://www.toymoban.com/news/detail-677091.html

到了这里,关于LeetCode笔记:Weekly Contest 360的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode - 360周赛

     这道题的意思是,遇到 \\\"L\\\" 向左走,遇到 \\\"R\\\" 向右走,遇到 \\\"_\\\" 左右都可以走,那么要想找到距离原点最远的点,就是在找 | \\\"L\\\" + \\\"R\\\" | + \\\"_\\\"  代码如下:  这道题要我们求最小和,那么我们肯定是从1开始往后遍历,而且题目要求不存在两个不同的下标 i 和 j,使得 nums[i] + nu

    2024年02月09日
    浏览(51)
  • leetcode 第360场周赛

    好久没参加leetcode周赛了,比赛时间都从两小时变成了一个半小时。这次周赛由两道签到题和两道中等难度题组成,严格来说最后一道的难度也可以视为hard,但是只要想到正确的思路,编码还是比较容易的。 比赛链接:leetcode 第 360 场周赛 题目描述 给你一个长度为 n 的字符串

    2024年02月11日
    浏览(37)
  • 【力扣周赛】第357场周赛

    题目描述 描述:你的笔记本键盘存在故障,每当你在上面输入字符 ‘i’ 时,它会反转你所写的字符串。而输入其他字符则可以正常工作。 给你一个下标从 0 开始的字符串 s ,请你用故障键盘依次输入每个字符。 返回最终笔记本屏幕上输出的字符串。 示例 1: 示例 2: 提示

    2024年02月13日
    浏览(34)
  • 【力扣周赛】第350场周赛

    题目描述 描述:卡车有两个油箱。给你两个整数,mainTank 表示主油箱中的燃料(以升为单位),additionalTank 表示副油箱中的燃料(以升为单位)。 该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时,如果副油箱至少有 1 升燃料,则会将 1 升燃料从副油箱

    2024年02月09日
    浏览(55)
  • 【力扣周赛】第 352 场周赛

    第 352 场周赛 2760. 最长奇偶子数组 提示: 1 = nums.length = 100 1 = nums[i] = 100 1 = threshold = 100 因为数据范围特别小,所以怎么暴力都是无所谓的。 继续优化 可以发现,每个满足条件的子数组是不会重叠的, 所以在枚举 l 的时候,每次可以将下一个 l 设置成 r。 代码如下: 2761. 和

    2024年02月12日
    浏览(35)
  • 【力扣周赛】第 357 场周赛(⭐反悔贪心)

    https://leetcode.cn/contest/weekly-contest-357/ https://leetcode.cn/problems/faulty-keyboard/ 提示: 1 = s.length = 100 s 由小写英文字母组成 s[0] != \\\'i\\\' 遇到 ‘i’ 翻转已有的字符串,其它字符直接添加即可。 用一个变量维护当前翻转了几次,来决定新来的字符添加在开头还是结尾。 https://leetcode.cn

    2024年02月09日
    浏览(38)
  • 力扣周赛日记350

    早上兴高采烈起床写周赛,结果写完两题开始坐牢。菜的很。 LeetCode 第 350 场周赛 LeetCode 6901. 总行驶距离 2.1.1 题意 卡车两个油箱,耗油1L行驶10km。油箱A耗5L,油箱B给邮箱A油1L。油箱A空后停止行驶,求可行使距离。 2.1.2 分析 开始想O(1)解法,发现这题主要问题在油箱B给了油箱

    2024年02月10日
    浏览(39)
  • 【力扣周赛】第 113 场双周赛(贪心&异或性质&换根DP)

    https://leetcode.cn/contest/biweekly-contest-113/ https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/ 提示: 1 = nums.length = 100 1 = nums[i] = 100 nums 中的整数互不相同。 因为数据范围很小,所以可以从小到大枚举可能的答案。 https://leetcode.cn/problems/minimum-array-length-after-pair-removals/ 提示: 1

    2024年02月07日
    浏览(34)
  • LeetCode笔记:Biweekly Contest 108

    LeetCode笔记:Biweekly Contest 108 1. 题目一 1. 解题思路 2. 代码实现 2. 题目二 1. 解题思路 2. 代码实现 3. 题目三 1. 解题思路 2. 代码实现 4. 题目四 1. 解题思路 2. 代码实现 比赛链接:https://leetcode.com/contest/biweekly-contest-108/ 给出题目一的试题链接如下: 2765. Longest Alternating Subarray 1

    2024年02月13日
    浏览(38)
  • LeetCode笔记:Biweekly Contest 112

    LeetCode笔记:Biweekly Contest 112 0. 吐槽 1. 题目一 1. 解题思路 2. 代码实现 2. 题目二 1. 解题思路 2. 代码实现 3. 题目三 1. 解题思路 2. 代码实现 4. 题目四 1. 解题思路 2. 代码实现 比赛链接:https://leetcode.com/contest/biweekly-contest-112/ 这一次的双周赛题目委实是有点水了,难怪第一名的

    2024年02月10日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包