[LeetCode周赛复盘] 第 348场周赛20230604

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

一、本周周赛总结

  • 这场可惜了。
  • T1 模拟。
  • T2 模拟。
  • T3 倒序计算。
  • T4 同时限制上下界的数位DP。
    [LeetCode周赛复盘] 第 348场周赛20230604

6462. 最小化字符串长度

6462. 最小化字符串长度

1. 题目描述

[LeetCode周赛复盘] 第 348场周赛20230604

2. 思路分析

题意仔细想一下就会发现,其实会将每个字符仅留1个。

3. 代码实现

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        return  len(set(s))

6424. 半有序排列

6424. 半有序排列

1. 题目描述

[LeetCode周赛复盘] 第 348场周赛20230604

2. 思路分析

  • 由于只能相邻交换来移动,因此每次只能移动1步。
  • 那么分别找到1和n的位置,计算他们移动距离。
    • 额外的,若1在n的右边,移动路径交叉,那么可以1向左时,n会免费向右一下,因此答案-1。

3. 代码实现

class Solution:
    def semiOrderedPermutation(self, a: List[int]) -> int:
        n = len(a)
        x,y = a.index(1),a.index(n)
        return x + n-y-1-(x>y)
     

6472. 查询后矩阵的和

6472. 查询后矩阵的和

1. 题目描述

[LeetCode周赛复盘] 第 348场周赛20230604

2. 思路分析

你就记住,最小化最大值=二分、覆盖求整体=逆序
  • 逆序处理后,每次格子的贡献是确定的,只需要记录每次操作有多少个格子被修改即可。
  • 那么用哈希表储存已被修改的行/列,若这行/列已被改过,那这次操作可以跳过。
    • 否则记录操作这行时,有多少个空位。即 n - len(ys)。

3. 代码实现

class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        ans = 0
        xs = set()
        ys = set()
        for t,i,val in queries[::-1]:          
            if t == 0:
                if i not in xs:
                    ans += val * (n-len(ys))
                    xs.add(i)                 
            else:
                if i not in ys:
                    ans += val *(n-len(xs))
                    ys.add(i)
        return ans

6396. 统计整数数目

6396. 统计整数数目

1. 题目描述

[LeetCode周赛复盘] 第 348场周赛20230604文章来源地址https://www.toymoban.com/news/detail-475012.html

2. 思路分析

  • 套数位DP板子即可,这题同时限制了上下界,那么不用考虑前边填没填数的事(省去is_num参数)。
  • 除了上下界限制,同时传一个s作为数字求和进去。当i遍历到n时,判断方案是否合法,返回1/0。
  • 另外中途s已经超过上限的话可以提前退出。

  • 参见[python刷题模板] 数位DP
  • 加餐,同时限制上下界的数位dp1742. 盒子中小球的最大数量

3. 代码实现

MOD = 10**9 + 7
class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        m,n = len(num1),len(num2)
        num1 = '0'*(n-m) + num1
        @cache
        def f(i,s,up_limit,down_limit):
            if i == n:
                if   min_sum<=s<=max_sum:
                    return 1
                else:
                    return 0
            if s > max_sum:
                return 0
            up = int(num2[i]) if up_limit else 9 
            down = int(num1[i]) if down_limit else 0 
            ans = 0
            
            for j in range(down,up+1):
                ans += f(i+1,s+j,up_limit and j==up,down_limit and j == down)
                ans %= MOD 
            return ans 
        return f(0,0,True,True)                       

参考链接

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

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

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

相关文章

  • 【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 周赛 348(2023/06/05)数位 DP 模板学会了吗

    本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 加入知识星球提问! 往期回顾:LeetCode 单周赛第 347 场 · 二维空间上的 LIS 最长递增子序列问题 T1. 最小化字符串长度(Medium) 标签:散列表、计数 T2. 半有序排列(Easy) 标签:散列表 T3. 查询后矩阵的和(

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

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

    2024年02月11日
    浏览(37)
  • 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)
  • LeetCode第354场周赛

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

    2024年02月16日
    浏览(63)
  • leetcode第 357/358 场周赛

    可能别人有更好的解法,我这写法是不断往线段树中插入数值,每次先插入nums[i-x],然后搜索(1到i)中的最大值和(i到max)中的最小值去更新ans。 看了看别人题解,直接用set写是真的牛。自己还是见识短浅了。 暴力乱搞,考虑两种极端情况,一种无脑选profit大的,一种优先选

    2024年02月12日
    浏览(40)
  • Leetcode 第 365 场周赛题解

    思路 暴力。 代码 复杂度分析 时间复杂度:O(n 3 ),其中 n 是数组 nums 的长度。 空间复杂度:O(1)。 思路 枚举 k,我们需要知道 k 左边 nums[i]−nums[j] 的最大值。 使用 pre_max 维护 k 之前的 nums[i] 的最大值,使用 max_diff 维护 nums[i]−nums[j] 的最大值。 每次遍历一个 nums[i],都更新

    2024年02月07日
    浏览(34)
  • leetcode第354场周赛补题

    6889. 特殊元素平方和 - 力扣(LeetCode) 思路:模拟 6929. 数组的最大美丽值 - 力扣(LeetCode) 思路:排序+双指针 6927. 合法分割的最小下标 - 力扣(LeetCode) 思路:哈希+枚举 6924. 最长合法子字符串的长度 - 力扣(LeetCode) 思路:哈希+双指针

    2024年02月16日
    浏览(38)
  • LeetCode 第385场周赛个人题解

    目录 100212. 统计前后缀下标对 I 原题链接 题目描述 接口描述 思路分析 代码详解 100229. 最长公共前缀的长度 原题链接 题目描述 接口描述 思路分析 代码详解 100217. 出现频率最高的素数 原题链接 题目描述 接口描述 思路分析 代码详解 100212. 统计前后缀下标对 II 原题链接 题目

    2024年02月19日
    浏览(76)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包