[LeetCode周赛复盘] 第 353 场周赛20230709

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

一、本周周赛总结

  • 感觉有奖品大家都来了。
  • T1 数学。
  • T2 dp。
  • T3 dp。
  • T4 差分/BIT RUPQ。
    [LeetCode周赛复盘] 第 353 场周赛20230709,力扣周赛复盘,leetcode,算法,职场和发展

6451. 找出最大的可达成数字

6451. 找出最大的可达成数字

1. 题目描述

[LeetCode周赛复盘] 第 353 场周赛20230709,力扣周赛复盘,leetcode,算法,职场和发展

2. 思路分析

  • 为了使x num在t步内相同,需要相向而行,每步最大缩短距离是2,那么t步距离是2t。

3. 代码实现

class Solution:
    def theMaximumAchievableX(self, num: int, t: int) -> int:
        return num+2*t

6899. 达到末尾下标所需的最大跳跃次数

6899. 达到末尾下标所需的最大跳跃次数

1. 题目描述

[LeetCode周赛复盘] 第 353 场周赛20230709,力扣周赛复盘,leetcode,算法,职场和发展

2. 思路分析

  • 每个位置都尝试向后跳即可。
  • 思考,如果n<=1e5咋做?
    • 改成填表法,然后用离散化线段树维护前边的max。
    • 要离散的数据是nums里所有v v-t v+t。
    • 这题由于n小,所以用BIT甚至更快。

3. 代码实现

class Solution:
    def maximumJumps(self, nums: List[int], t: int) -> int:
        n = len(nums)
        f = [-inf]*n 
        f[0] = 0 
        for i in range(n-1):
            for j in range(i+1,n):
                if abs(nums[j]-nums[i]) <= t:
                    f[j] = max(f[j],f[i]+1)
           
        return f[-1] if f[-1] > -inf else -1

nlgn线段树做法


class ZKW:
    # n = 1
    # size = 1
    # log = 2
    # d = [0]
    # op = None
    # e = 10 ** 15
    """自低向上非递归写法线段树,0_indexed
    tmx = ZKW(pre, max, -2 ** 61)
    """
    __slots__ = ('n', 'op', 'e', 'log', 'size', 'd')

    def __init__(self, V, OP, E):
        """
        V: 原数组
        OP: 操作:max,min,sum
        E: 每个元素默认值
        """
        self.n = len(V)
        self.op = OP
        self.e = E
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        # assert 0 <= p and p < self.n
        update = self.update
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            update(p >> i)

    def get(self, p):
        # assert 0 <= p and p < self.n
        return self.d[p + self.size]

    def query(self, l, r):  # [l,r)左闭右开
        # assert 0 <= l and l <= r and r <= self.n
        sml, smr, op, d = self.e, self.e, self.op, self.d

        l += self.size
        r += self.size

        while l < r:
            if l & 1:
                sml = op(sml, d[l])
                l += 1
            if r & 1:
                smr = op(d[r - 1], smr)
                r -= 1
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_query(self):
        return self.d[1]

    def max_right(self, l, f):
        """返回l右侧第一个不满足f的位置"""
        # assert 0 <= l and l <= self.n
        # assert f(self.e)
        if l == self.n:
            return self.n
        l += self.size

        sm, op, d, size = self.e, self.op, self.d, self.size
        while True:
            while l % 2 == 0:
                l >>= 1
            if not (f(op(sm, d[l]))):
                while l < size:
                    l = 2 * l
                    if f(op(sm, d[l])):
                        sm = op(sm, d[l])
                        l += 1
                return l - size
            sm = op(sm, d[l])
            l += 1
            if (l & -l) == l:
                break
        return self.n

    def min_left(self, r, f):
        """返回r左侧连续满足f的最远位置的位置"""
        # assert 0 <= r and r < self.n
        # assert f(self.e)
        if r == 0:
            return 0
        r += self.size
        sm, op, d, size = self.e, self.op, self.d, self.size

        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not (f(op(d[r], sm))):
                while r < size:
                    r = (2 * r + 1)
                    if f(op(d[r], sm)):
                        sm = op(d[r], sm)
                        r -= 1
                return r + 1 - size
            sm = op(d[r], sm)
            if (r & -r) == r:
                break
        return 0

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def __str__(self):
        return str([self.get(i) for i in range(self.n)])



class Solution:
    def maximumJumps(self, nums: List[int], t: int) -> int:
        n = len(nums)
        h = set(nums)
        for v in nums:
            h.add(v-t)
            h.add(v+t)
        h = sorted(h)
        size = len(h)
        f = ZKW([-inf]*size,max,-inf)
        f.set(bisect_left(h,nums[0]),0)
        for i in range(1,n):            
            l,r = bisect_left(h,nums[i]-t),bisect_right(h,nums[i]+t)
            i = bisect_left(h,nums[i])           
            ans = max(f.get(i), f.query(l,r)+1)
            f.set(i,ans)
            
           
        return [-1,ans][ans>-inf]

6912. 构造最长非递减子数组

6912. 构造最长非递减子数组

1. 题目描述

[LeetCode周赛复盘] 第 353 场周赛20230709,力扣周赛复盘,leetcode,算法,职场和发展

2. 思路分析

  • dp。
  • 定义f[i][0/1]为以i为右端点时,分别使用num1 num2中数字时的最长长度。
  • 那么转移分别讨论前一个数大小即可。
  • 实现时可以省去第一维度。

3. 代码实现

class Solution:
    def maxNonDecreasingLength(self, nums1, nums2):
        n = len(nums1)        
        
        x = y = 1
        ans = 1 
        for i in range(1,n):
            a=b=1
            if nums1[i] >= nums1[i-1]:
                a = x+1
            if nums1[i] >= nums2[i-1]:
                a = max(a,y+1)
            
            if nums2[i] >= nums1[i-1]:
                b = x+1
            if nums2[i] >= nums2[i-1]:
                b = max(b,y+1)
            ans = max(ans,a,b)
            x,y = a,b 
        
        return ans

6919. 使数组中的所有元素都等于零

6919. 使数组中的所有元素都等于零

1. 题目描述

[LeetCode周赛复盘] 第 353 场周赛20230709,力扣周赛复盘,leetcode,算法,职场和发展

2. 思路分析

  • 一眼RUPQ,且是顺序的,所以强行写差分wa半天。
  • 早知道直接BIT了。

3. 代码实现

差分

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        d = [0]*(n+1)
        d[0] = nums[0]
        for i in range(1,n):
            d[i] = nums[i] - nums[i-1]
       
        for i in range(n-k+1):
            # print(i)
            if d[i]<0:
                # print(i,d[i])
                return False
            
            d[i+k] += d[i]
            d[i]-=d[i]
        # print(d)
        if all(v==0 for v in d[:-1])  :
            return True 
        return False            

BIT文章来源地址https://www.toymoban.com/news/detail-551667.html

class BinIndexTreeRUPQ:
    """树状数组的RUPQ模型,结合差分理解"""
    def __init__(self, size_or_nums):  # 树状数组,下标需要从1开始
        # 如果size 是数字,那就设置size和空数据;如果size是数组,那就是a
        if isinstance(size_or_nums, int):
            self.size = size_or_nums
            self.c = [0 for _ in range(self.size + 5)]
        else:
            self.size = len(size_or_nums)
            self.c = [0 for _ in range(self.size + 5)]
            for i, v in enumerate(size_or_nums):
                self.add_interval(i + 1, i + 1, v)

    def add_point(self, i, v):  # 单点增加,下标从1开始;不支持直接调用,这里增加的是差分数组的单点
        while i <= self.size:
            self.c[i] += v
            i += i&-i

    def sum_prefix(self, i):  # 前缀求和,下标从1开始;不支持直接调用,这里求和的是差分数组的前缀和
        s = 0
        while i >= 1:
            s += self.c[i]
            i &= i-1
        return s

    def add_interval(self, l, r, v):  # 区间加,下标从1开始,把[l,r]闭区间都加v
        self.add_point(l, v)
        self.add_point(r + 1, -v)

    def query_point(self, i):  # 单点询问值,下标从1开始,返回i位置的值
        return self.sum_prefix(i)

    def lowbit(self, x):
        return x & -x
class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        bit = BinIndexTreeRUPQ(nums)
        for i in range(n-k+1):
            p = bit.query_point(i+1)
            if p < 0:
                return False 
            bit.add_interval(i+1,i+k,-p)
        if all(bit.query_point(i)==0 for i in range(1,n+1))  :
            return True 
        return False                  

参考链接

到了这里,关于[LeetCode周赛复盘] 第 353 场周赛20230709的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【力扣周赛】第357场周赛

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

    2024年02月13日
    浏览(33)
  • 【力扣周赛】第 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)
  • [LeetCode108双周赛&LeetCode353周赛] 学习用记忆化搜索解决 DP 问题

    参考灵神直播和代码 @cache 装饰器的作用:将传入不同参数得到的函数值存储到缓存,避免下次传递相同参数重复计算结果,可用于解决递归函数重复计算问题,比如递归求斐波那契问题。 https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/ 记忆化搜索 dfs(i) 表示以

    2024年02月13日
    浏览(37)
  • 【LeetCode周赛】LeetCode第358场周赛

    给你一个下标从0开始的整数数组nums。请你从nums中找出和最大的一对数,且这两个数数位上最大的数字相等。 返回最大和,如果不存在满足题意的数字对,返回 -1 。 示例 1: 输入:nums = [51,71,17,24,42] 输出:88 解释: i = 1 和 j = 2 ,nums[i] 和 nums[j] 数位上最大的数字相等,且这

    2024年02月12日
    浏览(44)
  • 【LeetCode周赛】LeetCode第359场周赛

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

    2024年02月10日
    浏览(42)
  • 【LeetCode周赛】LeetCode第370场周赛

    一场比赛中共有 n 支队伍,按从 0 到 n - 1 编号。 给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 = i, j = n - 1 且 i != j 的所有 i, j :如果 grid[i][j] == 1,那么 i 队比 j 队 强 ;否则,j 队比 i 队 强 。 在这场比赛中,如果不存在某支强于 a 队的队伍,则认为

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

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

    2024年02月11日
    浏览(37)
  • LeetCode第354场周赛

    给你一个下标从 1 开始、长度为 n 的整数数组 nums 。 对 nums 中的元素 nums[i] 而言,如果 n 能够被 i 整除,即 n % i == 0 ,则认为 num[i] 是一个 特殊元素 。 返回 nums 中所有 特殊元素 的 平方和 。 直接模拟就好了 给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。 在一

    2024年02月16日
    浏览(62)
  • LeetCode第343场周赛

    2023.4.30LeetCode第343场周赛 根据题意模拟 使用哈希表记录每个数出现的位置,再用m+n个集合记录每一行和每一列被涂满的格子数,若某行或某列全部被涂满则返回答案 BFS 首先将距离大于两点的曼哈顿距离的特殊路径去掉 每个点考虑经过每个特殊路径到达,分成两段,一段是当

    2024年02月02日
    浏览(41)
  • LeetCode第347场周赛

    2023.5.28LeetCode第347场周赛 从最后一位开始遍历,为0则跳过 暴力模拟 对于每个 s[i] != s[i - 1] ,要使其相等 有两种选择,翻转前 i 个,或者翻转后 n - i 个,选择代价最小的方案 动态规划 从小到大枚举所有值,每个值一定是从更小的数转移而来 定义动态规划数组f, f[i][j] 表示

    2024年02月06日
    浏览(75)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包