当前位置: 首页 > 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框架推出的…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...