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

LeetCode --- 410周赛

题目列表

3248. 矩阵中的蛇

3249. 统计好节点的数目

3250. 单调数组对的数目 I

3251. 单调数组对的数目 II

一、矩阵中的蛇

只要按照题目要求模拟即可,代码如下

class Solution {
public:int finalPositionOfSnake(int n, vector<string>& commands) {int i = 0, j = 0;for(auto s:commands){switch(s[0]){case 'U': i--; break; // switch 语法:记得加break,不然后面的case语句也会被执行case 'D': i++; break;case 'R': j++; break;case 'L': j--; break;}}return i * n + j;}
};

 二、统计好结点的数目

这题考多叉树的遍历,主要看对递归的理解。计算树中满足其子树结点个数相同的结点个数,本质还是求结点个数,只不过多了一些限制条件,只要在求结点个数的dfs代码中进行修改即可,代码如下

class Solution {
public:int countGoodNodes(vector<vector<int>>& edges) {int n = edges.size() + 1;// 建树vector<vector<int>> g(n);for(auto e:edges){g[e[0]].push_back(e[1]);g[e[1]].push_back(e[0]);}int ans = 0;// 下面的 dfs函数 抛开 flag 相关的语句,就是一个求树的结点个数的代码function<int(int,int)>dfs = [&](int x,int fa)->int{bool flag = true;int pre = -1;int res = 1;for(int y:g[x]){if(y != fa){int sz = dfs(y, x);res += sz;if(pre == -1) pre = sz;else if(flag) flag &= (pre == sz);}}ans += flag;return res;};dfs(0, -1);return ans;}
};

三、单调数组对的数目 I & II

这种算合法方案数的题目,一般都是用动态规划解题 ( 最重要的一点是去尝试定义状态,当然做多了题目会有感觉,具体如何定义状态还要结合题目具体问题具体分析 ) 这题的状态定义如下:

  • 状态定义:f[i][j] 表示 第 i 个数为 j 时,有多少个合法的方案数(单调数组对)
  • 状态转移方程:f[i][j] = sum(f[i-1][k]),其中 k <= min(j, nums[i-1]) && nums[i] - j <= nums[i-1] - k ,等价于 k <= min(j, nums[i-1], j + nums[i-1] - nums[i])
    表示第 i 个数填 j 时的合法方案由第 i - 1 个数填 k 时的合法方案数之和,其中 k 需要满足题目的要求
  • 状态初始化:当 i = 0 时,可以填任何数,都算作一种合法的方案,即 f[0][j] = 1

代码如下

class Solution {const int MOD = 1e9 + 7;
public:int countOfPairs(vector<int>& nums) {int n = nums.size(), m = ranges::max(nums);vector<vector<int>> f(n, vector<int>(m + 1, 1));// f[i][j] 表示 第 i 个数填 j 时,所有可能的方案数// f[0][j] 第 0 个数 可以任意取,都算作一个合法方案,初始化为 1// f[i][j] = sum(f[i-1][k]) // 满足 k <= min(j, nums[i-1]) && nums[i] - j <= nums[i-1] - k// 等价于 k <= min(j, nums[i-1], j + nums[i-1] - nums[i])for(int i = 1; i < n; i++){for(int j = 0; j <= nums[i]; j++){int res = 0;for(int k = 0; k <= min({j, nums[i-1],j + nums[i-1] - nums[i]}); k++){res = (res + f[i-1][k])%MOD;}f[i][j] = res;}}int ans = 0;for(int i = 0; i <= nums.back(); i++)ans = (ans + f[n-1][i])%MOD;return ans;}
};

如何优化?

这里其实显而易见,我们在计算 f[i][j] 时,最内层对 k 的循环遍历,本质就是在求前缀和,我们可以提前预处理得到,这样就能在O(1) 的时间内计算出 f[i][j],代码如下

class Solution {const int MOD = 1e9 + 7;
public:int countOfPairs(vector<int>& nums) {int n = nums.size(), m = ranges::max(nums);vector<vector<int>> f(n, vector<int>(m + 1, 1));// f[i][j] 表示 第 i 个数为 j 时,所有可能的方案数// f[0][j] 第 0 个数 可以任意取,都算作一个合法方案,初始化为 1// f[i][j] = sum(f[i-1][k]) // 满足 k <= min(j, nums[i-1]) & nums[i] - j <= nums[i-1] - k// 等价于 k <= min(j, nums[i-1], j + nums[i-1] - nums[i])for(int i = 1; i < n; i++){// 预处理前缀和int pre[nums[i-1]+1]; pre[0] = f[i-1][0];for(int j = 1; j <= nums[i-1]; j++){pre[j] = (pre[j-1] + f[i-1][j])%MOD;}for(int j = 0; j <= nums[i]; j++){// int res = 0;// for(int k = 0; k <= min({j, nums[i-1],j + nums[i-1] - nums[i]}); k++){//     res = (res + f[i-1][k])%MOD;// }// f[i][j] = res;int x = min({j, nums[i-1],j + nums[i-1] - nums[i]});if(x < 0) f[i][j] = 0;else f[i][j] = pre[x];}}int ans = 0;for(int i = 0; i <= nums.back(); i++)ans = (ans + f[n-1][i])%MOD;return ans;}
};

相关文章:

LeetCode --- 410周赛

题目列表 3248. 矩阵中的蛇 3249. 统计好节点的数目 3250. 单调数组对的数目 I 3251. 单调数组对的数目 II 一、矩阵中的蛇 只要按照题目要求模拟即可&#xff0c;代码如下 class Solution { public:int finalPositionOfSnake(int n, vector<string>& commands…...

最佳的iPhone解锁软件和应用程序

在探讨最佳的iPhone解锁软件和应用程序时&#xff0c;我们需要考虑多个方面&#xff0c;包括软件的解锁能力、易用性、安全性、兼容性以及用户评价等。以下是对当前市场上几款优秀iPhone解锁软件和应用程序的详细分析&#xff0c;旨在为用户提供全面而深入的指导。 一、奇客iO…...

初等函数和它的表达式

常量函数&#xff0c;幂函数&#xff0c;指数函数&#xff0c;对数函数&#xff0c;三角函数和反三角函数成为基本初等函数。基本初等函数经过有限四则运算和符合运算得到的函数称为初等函数。 1. 常量函数 表达式&#xff1a; &#xff08;其中 c 是常数&#xff09;参数的意…...

Android 12系统源码_多屏幕(二)模拟辅助设备功能开关实现原理

前言 上一篇我们通过为Android系统开启模拟辅助设备功能开关&#xff0c;最终实现了将一个Activity显示到多个屏幕的效果。 本篇文章我们具体来分析一下当我们开启模拟辅助设备功能开关的时候&#xff0c;Android系统做了什么哪些操作。 一、模拟辅助设备功能开关应用位置 …...

【Go语言初探】(二)、项目文件结构和GOPATH设置

一、go语言项目文件结构 由go/bin、go/src和go/pkg三个子文件夹组成&#xff0c;见下图&#xff1a; 实际项目&#xff1a; 二、gopath路径变量设置 在项目中创建main.go文件后&#xff0c;IDE会提示设置GOPATH路径&#xff1a; 点击“configure GOPATH”&#xff0c;设置GOP…...

三种简单排序:插入排序、冒泡排序与选择排序 【算法 05】

三种简单排序&#xff1a;插入排序、冒泡排序与选择排序 在编程中&#xff0c;排序算法是基础且重要的知识点。虽然在实际开发中&#xff0c;我们可能会直接使用标准库中的排序函数&#xff08;如C的std::sort&#xff09;&#xff0c;但了解并实现这些基础排序算法对于理解算法…...

Python -- GUI图形界面编程—GUI编程实例 博主也在持续学习中[ 持续更新中!!! 欢迎白嫖 也求粉啊啊啊~ ]

本文介绍了GUI的图形界面编程&#xff08;相关视频是哔站上的应该搜这个题目就能找到&#xff09;&#xff0c;文章还是很基础的&#xff0c;反正我是小白从0开始&#xff0c;主要的结构tinkter库、重要组件简介&#xff08;这个不用死记硬背 用的时候再说&#xff09;、Label&…...

Vue2和Vue3中的diff算法

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、diff算法是什么&#xff1f;二、vue2中的diff算法三、vue3中的diff算法总结 前言 一、diff算法是什么&#xff1f; diff算法很早就存在了&#xff0c;一开…...

springboot使用aop或Jackson进行数据脱敏

1.aop 启动类加EnableAspectJAutoProxy 自定义注解&#xff0c;在实体类中使用表示被脱敏字段 建立aop切面类 可能这里gpt会建议你用Pointcut("execution(public * com.xx.aop..*.get*(..))")这种方式拦截&#xff0c;这种我试了&#xff0c;拦截不住。猜测在mvc返…...

【Solidity】基础介绍

数据类型 值类型 值类型的变量在赋值或作为函数参数传递时会被复制。 布尔类型&#xff1a;bool整数类型&#xff1a; 无符号&#xff1a;uint8、uint16、…、uint256 (uint256 可简写为 uint)有符号&#xff1a;int8、int16、…、int256 (int256可简写为 int) 地址类型&…...

【SpringBoot3】双向实时通讯 websocket

文章目录 一、Websocket使用步骤二、示例1&#xff1a;继承抽象类 AbstractWebSocketHandler后端代码前端代码 三、示例2&#xff1a;使用注解ServerEndpoint后端代码前端代码 四、前端代码封装 一、Websocket使用步骤 在Spring Boot中使用WebSocket是一个常见的需求&#xff…...

搭建内网开发环境(一)|基于docker快速部署开发环境

引言 最近因需要搭建一套简易版的纯内网的开发环境&#xff0c;服务器采用 centos8.0&#xff0c;容器化技术采用 docker 使用 docker-compose 进行容器编排。 该系列教程分为两大类&#xff1a; 软件安装和使用&#xff0c;这类是开发环境常用的软件部署和使用&#xff0c;涉…...

MATLAB R2023b配置Fortran编译器

MATLAB R2023b配置Fortran编译器 引言1. 安装Visual Studio 20192. 安装Intel API20243. 配置xml文件文件4. 设置环境变量5. MATLAB编译Fortran 引言 当我们需要用到MATLAB编译Fortran代码后进行调用计算时&#xff0c;整个配置流程较繁琐。下面以MATLAB R2023b为例&#xff0…...

2024新型数字政府综合解决方案(七)

新型数字政府综合解决方案通过集成人工智能、大数据、区块链和云计算技术&#xff0c;创建了一个高度智能化和互联互通的政府服务平台&#xff0c;旨在全面提升行政效率、服务质量和透明度。该平台实现了跨部门的数据整合与实时共享&#xff0c;利用人工智能进行智能决策支持和…...

搭建高可用k8s集群

高可用 Kubernetes V1.28.10 安装 文章目录 1. 环境介绍2. 准备工作2.1 修改主机名称2.2 修改hosts文件2.3 关闭防火墙和SLinux2.4 配置SSH免密访问2.4.1 主机名称: k8s-master-01 操作 2.5 配置yum源2.6 禁用Swarp分区2.7 同步时间2.8 配置内核转发及网桥过滤2.9 安装 IPVS 3…...

完美解决html2canvas + jsPDF导出pdf分页内容截断问题

代码地址&#xff1a;https://github.com/HFQ12333/export-pdf.git html2canvas jspdf方案是前端实现页面打印的一种常用方案&#xff0c;但是在实践过程中&#xff0c;遇到的最大问题就是分页截断的问题&#xff1a;当页面元素超过一页A4纸的时候&#xff0c;连续的页面就会…...

14 地址映射

14 地址映射 1、地址划分2、相关函数2.1 ioremap/iounmap2.2 mmap地址映射 3、总结 1、地址划分 明确&#xff1a;在linux系统中,不管是应用程序还是驱动程序&#xff0c;都不允许直接访问外设的物理地址,要想访问必须将物理地址映射到用户虚拟地址或者内核虚拟地址&#xff0…...

Java Resilience4j-RateLimiter学习

一. 介绍 Resilience4j-RateLimiter 是 Resilience4j 中的一个限流模块&#xff0c;我们对 Resilience4j 的 CircuitBreaker、Retry 已经有了一定的了解&#xff0c;现在来学习 RateLimiter 限流器&#xff1b; 引入依赖&#xff1b; <dependency><groupId>io.g…...

Nginx--地址重写Rewrite

一、什么是Rewrite Rewrite对称URL Rewrite&#xff0c;即URL重写&#xff0c;就是把传入Web的请求重定向到其他URL的过程 URL Rewrite最常见的应用是URL伪静态化&#xff0c;是将动态页面显示为静态页面方式的一种技术。比如http://www.123.com/news/index.php?id123 使用U…...

webflux源码解析(1)-主流程

目录 1.关键实例的创建1.1 实例创建1.2 初始化 2.处理请求的关键流程2.1 从ReactorHttpHandlerAdapter开始2.1 DispatcherHandler的初始化2.2查找mapping handler2.3 处理请求(执行handler)2.4 返回结果处理 3.webflux的配置装配参考&#xff1a; WebFlux是Spring 5.0框架推出的…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...