LeetCode笔记:Weekly Contest 359

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

  • LeetCode笔记:Weekly Contest 359
    • 1. 题目一
      • 1. 解题思路
      • 2. 代码实现
    • 2. 题目二
      • 1. 解题思路
      • 2. 代码实现
    • 3. 题目三
      • 1. 解题思路
      • 2. 代码实现
    • 4. 题目四
      • 1. 解题思路
      • 2. 代码实现
  • 比赛链接:https://leetcode.com/contest/weekly-contest-359

1. 题目一

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

  • 2828. Check if a String Is an Acronym of Words

1. 解题思路

这一题倒是没啥好多说的,把题意翻译成代码语言即可。

2. 代码实现

给出python代码实现如下:

class Solution:
    def isAcronym(self, words: List[str], s: str) -> bool:
        if len(words) != len(s):
            return False
        return all(word[0] == ch for word, ch in zip(words, s))

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

2. 题目二

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

  • 2829. Determine the Minimum Sum of a k-avoiding Array

1. 解题思路

这一题我的做法多少也有点暴力,就是从1开始枚举,每增加一个元素的同时block掉它的成对元素,然后直到取满n个元素即可。

2. 代码实现

给出python代码实现如下:

class Solution:
    def minimumSum(self, n: int, k: int) -> int:
        block = set()
        i, cnt = 1, 0
        res = 0
        while cnt < n:
            if i not in block:
                res += i
                block.add(k-i)
                cnt += 1
            i += 1
        return res

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

3. 题目三

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

  • 2830. Maximize the Profit as the Salesman

1. 解题思路

这一题说来惭愧,没有一下子搞出来,一开始的思路跑偏了,想了分段树和greedy的方式,但是怎么也想不到可行的解法,然后看了一下其他大佬们的思路,发现就是一个简单的动态规划的算法,没能自力做出来真的是委实有些丢脸……

2. 代码实现

给出python代码实现如下:

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        locs = defaultdict(list)
        for st, ed, gold in offers:
            locs[st].append([ed, gold])
            
        @lru_cache(None)
        def dp(idx):
            if idx >= n:
                return 0
            res = dp(idx+1)
            for ed, gold in locs[idx]:
                res = max(res, gold + dp(ed+1))
            return res
        
        return dp(0)

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

4. 题目四

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

  • 2831. Find the Longest Equal Subarray

1. 解题思路

这一题我的思路上就是首先记录下每一个元素出现的位置,然后考察以每一个元素作为Equal Subarray的核心元素的话,在至多删除k个字符的情况下可以组成的最大长度并记录下来,最后,我们返回这些最大长度的最大值即可。

而考察对于任意给定的字符在至多删除k个字符的情况下可以组成的最大长度的过程,我们用一个滑动窗口即可进行实现。

2. 代码实现

给出python代码实现如下:

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        locs = defaultdict(list)
        for i, x in enumerate(nums):
            locs[x].append(i)

        cnt = {}
        for vals in locs.values():
            i, j, n = 0, 0, len(vals)
            while j < n:
                while vals[j]-vals[i] - (j-i) > k:
                    i += 1
                s, d = j-i+1, vals[j]-vals[i] - (j-i)
                cnt[s] = min(cnt[s], vals[j]-vals[i] - (j-i)) if s in cnt else vals[j]-vals[i] - (j-i)
                j += 1

        return max(cnt.keys())

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

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

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

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

相关文章

  • 【LeetCode周赛】LeetCode第359场周赛

    给你一个字符串数组 words 和一个字符串 s ,请你判断 s 是不是 words 的 首字母缩略词 。 如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ,则认为 s 是 words 的首字母缩略词。例如,“ab” 可以由 [“apple”, “banana”] 形成,但是无法从 [“bear”, “aardvark”

    2024年02月10日
    浏览(42)
  • leetcode359周赛

    滑动窗口 总长度 - 众数 k 就需要收缩窗口了。 所以需要一个数据结构统计众数: multiset 维护每一个数字的个数。 这里有一个坑 ms.erase(x) :会把所有的等于x的数字都删除。所以需要使用 auto it = ms.find(x); ms.erase(it) 来进行单个删除。 排序 + 二分 + dp 类似于学最多的课程,按照

    2024年02月12日
    浏览(38)
  • [LeetCode周赛复盘] 第 359 场周赛20230820

    T1 模拟。 T2 数学贪心。 T3 dp。 T4 分组+滑窗。 2828. 判别首字母缩略词 1. 题目描述 2. 思路分析 按题意模拟即可。 3. 代码实现 2829. k-avoiding 数组的最小总和 1. 题目描述 2. 思路分析 贪心 1~k-1中,选了1就不能选k-1;选了2就不能选k-2… 因此可以选1~k//2 剩余的从k开始向上选。 可以

    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日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包