[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日
    浏览(48)
  • LeetCode 周赛 348(2023/06/05)数位 DP 模板学会了吗

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

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

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

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

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

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

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

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

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

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

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

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

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

    2024年02月16日
    浏览(36)
  • 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日
    浏览(32)
  • LeetCode 第 388 场周赛个人题解

    目录 100233. 重新分装苹果 原题链接 思路分析 AC代码 100247. 幸福值最大化的选择方案 原题链接 思路分析 AC代码 100251. 数组中的最短非公共子字符串 原题链接 思路分析 AC代码 100216. K 个不相交子数组的最大能量值 原题链接 思路分析 AC代码 100233. 重新分装苹果 直接模拟 降序排

    2024年03月15日
    浏览(60)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包