当前位置: 首页 > news >正文

[LeetCode周赛复盘] 第 99 场双周赛20230304

[LeetCode周赛复盘] 第 99 场双周赛20230304

    • 一、本周周赛总结
    • 二、 [Easy] 2578. 最小和分割
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 三、[Medium] 2579. 统计染色格子数
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 四、[Medium] 2580. 统计将重叠区间合并成组的方案数
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 五、[Hard] 2581. 统计可能的树根数目
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 六、参考链接

一、本周周赛总结

  • T1 贪心。
  • T2 数学/dp。
  • T3 线段合并/快速幂取模。
  • T4 换根DP。

二、 [Easy] 2578. 最小和分割

链接: 2578. 最小和分割

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 这题如果不写暴力枚举的话,是个贪心,想了好一会。
  • 排序后奇偶交错分配即可。
  • 枚举的话,状压枚举可能写的更快一些。

3. 代码实现

class Solution:def splitNum(self, num: int) -> int:              s = []for c in str(num):if c != '0':s.append(c)s = sorted(s)n = len(s)h = n // 2a = []b = []for i,c in enumerate(s):if i & 1:b.append(c)else:a.append(c)x = int('0'+''.join(a))y = int('0'+''.join(b))return x + y 

三、[Medium] 2579. 统计染色格子数

链接: 2579. 统计染色格子数

1. 题目描述

在这里插入图片描述

2. 思路分析

数学能力已经退化,比赛时肯定不优先推公式。

  • 找规律dp。
  • 发现每次增加i*4个。

3. 代码实现

f = [1]*(10**5+1)
x = [1]*(10**5+1)
for i in range(2,10**5+1):x[i] = (i-1)*4f[i] = f[i-1] + x[i]
class Solution:def coloredCells(self, n: int) -> int:return f[n]        

四、[Medium] 2580. 统计将重叠区间合并成组的方案数

链接: 2580. 统计将重叠区间合并成组的方案数

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 分析题意发现,有交集的区间一定在一起,那么划分完会变成x个集合,这x个集合分别可以在左边或右边就互不影响了。
  • 因此答案就是2**x。

3. 代码实现

MOD = 10 ** 9 + 7
class Solution:def countWays(self, ranges: List[List[int]]) -> int:cnt = 1ranges.sort()print(ranges)p = ranges[0][1]for x,y in ranges:if x <= p:p = max(p,y)else:cnt += 1p = yreturn pow(2,cnt,MOD)

五、[Hard] 2581. 统计可能的树根数目

链接: 2581. 统计可能的树根数目

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 知道是换根DP,之前学了max版的换根dp,这次遇到加法的就不会了。
  • 学了一下。
  • 当然用模板也能做。

3. 代码实现

class Solution:def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:n = len(edges)+ 1g = [[] for _ in range(n)]for u,v in edges:g[u].append(v)g[v].append(u)s = set(tuple(x) for x in guesses)f = [0]*ndef dfs(u,fa):for v in g[u]:if v != fa:if (u,v) in s:f[0] += 1dfs(v,u)def reroot(u,fa):for v in g[u]:if v != fa:f[v] = f[u] + int((v,u) in s) - int((u,v) in s)reroot(v,u)dfs(0,-1)reroot(0,-1)return sum(x >= k for x in f)      

六、参考链接

相关文章:

[LeetCode周赛复盘] 第 99 场双周赛20230304

[LeetCode周赛复盘] 第 99 场双周赛20230304 一、本周周赛总结二、 [Easy] 2578. 最小和分割1. 题目描述2. 思路分析3. 代码实现三、[Medium] 2579. 统计染色格子数1. 题目描述2. 思路分析3. 代码实现四、[Medium] 2580. 统计将重叠区间合并成组的方案数1. 题目描述2. 思路分析…...

Parcel Bundle漏洞学习

Bundle的序列化细节看上去还是有些复杂的&#xff0c;在之前已经讨论过&#xff0c;一般我们使用Parcel的时候&#xff0c;都是严格的write和read相对应。一些疏漏&#xff0c;不对应&#xff0c;竟然就可以成为漏洞&#xff0c;https://xz.aliyun.com/t/2364 里介绍了Bundle漏…...

RTP载荷H264(实战细节)

RTP包由两部分组成&#xff0c;RTP头和RTP载荷&#xff1a; RTP头 RTP头的 结构如下&#xff1a; 代码结构&#xff1a; typedef struct RtpHdr {uint8_t cc : 4, // CSRC countx : 1, // header extendp : 1, // padding flagversion : 2; // versionuint8_t …...

软考高级信息系统项目管理师系列之四十三:信息系统安全管理

软考高级信息系统项目管理师系列之四十三:信息系统安全管理 一、信息系统安全管理内容二、信息安全策略1.信息系统安全策略的概念与内容2.信息系统安全等级保护的概念三、信息安全系统1.信息安全系统三维空间2.信息安全系统三种架构体系四、PKI公开密钥基础设施1.PKI总体架构2…...

并发编程之AtomicUnsafe

目录 原子操作 定义 术语 处理器如何实现原子操作 处理器自动保证基本内存操作的原子性 使用总线锁保证原子性 使用缓存锁保证原子性 Java当中如何实现原子操作 Atomic 定义 原子更新基本类型类 原子更新数组类 原子更新引用类型 原子更新字段类 Unsafe应用解析…...

GDB调试快速入门

什么是GDB&#xff1a; GDB - - - (GNU symbolic debugger)是Linux平台下最常用的一款程序调试器。 自己的Linux是否安装GDB? 一般来说&#xff0c;使用Ubuntu的话&#xff0c;系统就会自带的有GDB调试器的 命令窗口输入如下命令可以查看是否安装了gdb&#xff1a; gdb -v …...

Vim一次复制,多次粘贴

我们平常在使用Vim时候&#xff0c;通过viwy或者yy等复制操作之后&#xff0c;p操作粘贴的时候&#xff0c;只能粘贴一次&#xff0c;想要粘贴多次怎么办&#xff1f; 解决方案&#xff1a;在使用p的是时候使用"0p&#xff0c;这样就能无限制的一直粘贴了。 可是&#xff…...

如何修改Win11上的默认程序?

在Win10之前&#xff0c;更改特定文件格式的默认程序很简单&#xff0c;但在Win11发布之后&#xff0c;很多用户都不清楚关于Win11的修改默认程序的操作步骤&#xff0c;接下来我们就一起来看看吧&#xff0c;希望可以帮助到大家。 步骤如下&#xff1a; 一、如何更改Windows 1…...

安装Linux虚拟机和Hadoop平台教程汇总及踩坑总结

&#x1f4cd;主要内容介绍安装Linux虚拟机、ubuntu系统、安装hadoop三个环节的教程链接介绍及本机与虚拟机的FTP传输教程总结&#xff08;直接找hadoop安装环节的5.filezilla传输文件&#xff09;新鲜出炉的踩坑总结和填坑指南安装Linux虚拟机和ubuntu系统一、材料和工具1、下…...

Shell脚本的使用和介绍

为了方便以后工作使用和复习,吐血整理记录一下学习shell脚本的笔记,看这篇文章需要对linux系统熟悉,希望对大家有所帮助! 文章目录 目录 文章目录 一、什么是shell? 为什么要学习和使用shell? 二、shell的分类...

机械学习 - 基础概念 - scikit-learn - 数据预处理 - 1

目录安装 scikit-learn术语理解1. 特征&#xff08;feature &#xff09;和样本&#xff08; sample / demo&#xff09;的区别&#xff1f;2. 关于模型的概念一、机械学习概念1. 监督学习总结&#xff1a;2. 非监督学习总结&#xff1a;3. 强化学习总结&#xff1a;三种学习的…...

OLCNE cluster 配置 NFS Storage(英文)

OLCNE cluster 配置 NFS Storage&#xff08;英文&#xff09;Create an OLCNE cluster.Create an NFS server.a. Install the NFS utility package on the server and client instances.b. Create a directory for your shared files. Make sure that the server does not hav…...

RabbitMQ高级特性

RabbitMQ高级特性 消息可靠性投递 Consumer ACK 消费端限流 TTL 死信队列 延迟队列 日志与监控 消息可靠性分析与追踪 管理 消息可靠性投递 在使用 RabbitMQ 的时候&#xff0c;作为消息发送方希望杜绝任何消息丢失或者投递失败场景。RabbitMQ 为我们提供了两种方式用来控制…...

利用Dockerfile开发定制镜像实战.

Dockerfile的原理 dockerfile是一种文本格式的文件&#xff0c;用于描述如何构建Docker镜像。在Dockerfile中&#xff0c;我们可以定义基础镜像、安装依赖、添加文件等操作&#xff0c;最终生成一个可以直接运行的容器镜像。 Dockerfile的原理可以分为以下几个步骤&#xff1a…...

PyInstaller 将DLL文件打包进exe

PyInstaller 将DLL文件打包进exe方法1&#xff1a;通过--add-data命令方法2&#xff1a;通过修改 .spec扩展&#xff1a;博主热门文章推荐&#xff1a;方法1&#xff1a;通过–add-data命令 注意&#xff1a;这里 dll末尾添加的.为当前目录&#xff0c;则该dll要放到main.py同一…...

【JVM篇2】垃圾回收机制

目录 一、GC的作用 申请变量的时机&销毁变量的时机 内存泄漏 内存溢出(oom) 垃圾回收的劣势 二、GC的工作过程 回收垃圾的过程 第一阶段&#xff1a;找垃圾/判定垃圾 方案1&#xff1a;基于引用计数(非Java语言) 引用计数方式的缺陷 方案2&#xff1a;可达性分析…...

LeetCode598. 范围求和 II(python)

题目 给你一个 m x n 的矩阵 M &#xff0c;初始化时所有的 0 和一个操作数组 op &#xff0c;其中 ops[i] [ai, bi] 意味着当所有的 0 < x < ai 和 0 < y < bi 时&#xff0c; M[x][y] 应该加 1。 提示: 1 < m, n < 4 * 104 0 < ops.length < 104 o…...

观察者模式与发布订阅模式

前言 我的任督二脉终于被打通了&#xff0c;现在该你了 区别 观察者模式 就2个角色&#xff1a;观察者和被观察者&#xff08;重要&#xff09;明确知道状态源&#xff0c;明确知道对方是谁一对多关系 发布订阅模式 有3个角色&#xff1a;发布者&#xff0c;订阅者和发布订阅…...

磨金石教育摄影技能干货分享|烟花三月下扬州,是时候安排了!

人间三月最柔情&#xff0c;杨柳依依水波横。三月的风将要吹来&#xff0c;春天的门正式打开。对中国人来说&#xff0c;古往今来&#xff0c;赏春最好的地方是江南。人人都说江南好&#xff0c;可是江南哪里好呢&#xff1f;古人在这方面早就给出了答案&#xff1a;故人西辞黄…...

Kafka 消费组位移

Kafka 消费组位移消费者 API命令行Kafka : 基于日志结构&#xff08;log-based&#xff09;的消息引擎 消费消息时&#xff0c;只是从磁盘文件上读取数据&#xff0c;不会删除消息数据位移数据能由消费者控制&#xff0c;能很容易修改位移的值&#xff0c;实现重复消费历史数据…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...