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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/404057.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

9 算术、关系、逻辑、赋值、位操作、三元运算符及其优先级

目录​​​​​​​ 1 运算符基础 1.1 什么是运算符 1.2 什么是表达式 1.3 左操作数和右操作数 1.4 运算符分类 1.4.1 按照操作数个数分类 1.4.2 按照功能分类 1.5 如何掌握运算符 2 算术运算符 2.1 正号和负号 2.2 加、减、乘、除 2.3 取模&#xff08;取余&#…

Git的使用-初级

Git 主要可以使用的远程仓库有 Github &#xff0c;Gitee 如果在国内建议使用 Gitee 比较快 从远程仓库下载工程 在安装好了 Git 后&#xff0c;我们右键单击一个本地的文件夹作为下载的目的地&#xff0c;选择 Git Bash Here 便可以通过 Linux 命令行的形式操作 Git Linux…

Redis的基本概念和使用

目录 一、Redis简介 1、NOSQL 2、NOSQL和关系型数据库比较 3、主流的NOSQL产品 4、什么是Redis 5、启动Redis 二、Redis基本操作 1、大概操作 三、 Redis 数据类型&#xff08;5种常用&#xff09; 1、redis 数据存储格式 2、String 3、hash 4、list 5、Set 6、…

【Linux入门】Linux常见指令

目录 前言 一、Linux基本指令 1.ls指令 2.pwd命令 3.cd 指令 4.touch指令 5.mkdir指令 6.rmdir指令 && rm 指令 7.man指令 8.cp指令 9.mv指令 10.cat 11.date 12.top 13.shutdown-关机 14.重要的几个热键 二、Linux扩展指令 总结 前言 Linux指令是在…

自学编程从哪个语言入手比较好?

自学编程时选择哪个语言作为起点&#xff0c;仍然取决于你的个人兴趣、学习目标和职业规划。希望以下建议可以帮到你。 Python&#xff1a; 如果你对数据分析、机器学习、人工智能、Web 开发或自动化脚本编写等领域感兴趣&#xff0c;Python 是一个非常好的起点。它的语法简洁…

Charles 抓包工具的使用

Charles 是一个网络抓包工具&#xff0c;我们可以用它抓取 APP 运行过程中产生的所有请求内容和响应内容&#xff0c;这和在浏览器开发者工具的 Network 面板中看到网页产生的内容是一样的道理 Charles , Fiddler 等都是非常强大的 HTTP 抓包软件&#xff0c;功能基本类似&…

网站配置了https证书,但浏览器访问时却访问了http

是由于缺少强制将 HTTP 请求重定向到 HTTPS 的规则 # HTTP 到 HTTPS 重定向配置 server {listen 80;server_name www.xlqd.site xlqd.site;return 301 https://$host$request_uri; } # 那么你原来的server块就要删除 listen 80;

Linux系统之部署轻量级Markdown文本编辑器

Linux系统之部署轻量级Markdown文本编辑器 一、项目介绍1.1 项目简介1.2 使用方法 二、本次实践介绍2.1 本地环境规划2.2 本次实践介绍 三、检查本地环境3.1 检查系统版本3.2 检查系统内核版本3.3 检查软件源 四、安装Apache24.1 安装Apache2软件4.2 启动apache2服务4.3 查看ap…

【Nginx】Nginx 安装(平滑升级和回滚)

一、 Nginx 概述 Nginx 介绍 Nginx &#xff1a; engine X &#xff0c; 2002 年开发&#xff0c;分为社区版和商业版 (nginx plus ) 2019 年 3 月 11 日 F5 Networks 6.7 亿美元的价格收购 Nginx 是免费的、开源的、高性能的 HTTP 和反向代理服务器、邮件代理服务器、以…

【word】修改图名/表名/公式编号后快速更新交叉引用的内容;交叉引用的字体不跟随正文如何解决

本文解决两个问题&#xff0c;不是什么特别正规的方法&#xff0c;主打一个迅速且通用。 问题描述 修改图名/表名/方程编号后快速更新交叉引用的内容 假设我们现在word文档中某处用了交叉引用。显然&#xff0c;图 1两个字颜色更深&#xff0c;就是我交叉引用的地方。 由于某…

贝莱德与摩根大通的最新季度持仓分析

近期&#xff0c;华尔街的两大投资巨头贝莱德和摩根大通公布了其2024年第二季度的13F报告&#xff0c;揭示了他们在投资组合上的最新动向。通过分析这些持仓数据&#xff0c;我们可以更清楚地了解这些顶级投资机构的投资策略和市场偏好。 贝莱德的科技巨头与能源投资 根据贝莱…

SpringBoot教程(二十二) | SpringBoot实现分布式定时任务之elastic-job

SpringBoot教程&#xff08;二十二&#xff09; | SpringBoot实现分布式定时任务之elastic-job 简介前置条件&#xff1a;需要ZooKeeper配合1、引入相关依赖2、application.yml中配置注册中心和作业调度巨坑&#xff08;配置修改无效&#xff09;3、job实例4、ElasticJob-UI监控…

网络编程-网络基础

IO进程: 进程和进程之间的通信 - 信号 信号量 消息队列 有名管道 无名管道 共享内存 套接字 套接字: 不同主机 不同操作系统之间的 进程通信 干什么: 实现无线 局域网&#xff1a;同一局域网下IP网段一致 IP地址 1) IP地址 是 网络中的 主机的标识, 本质是二进制数字。 2…

37_DC-5靶机渗透测试、nmap使用、kail漏洞库使用、系统提权、反弹shell到kali、留后门、蚁剑连接webshell、文件包含漏洞利用、NC用法

环境准备 靶机下载地址&#xff1a;https://www.vulnhub.com/entry/dc-5,314/ 百度网盘&#xff1a;https://pan.baidu.com/s/1lqFMjoqQpIl4DA-Amb00pA?pwd9LJY 攻击机&#xff1a;kali&#xff08;192.168.58.130&#xff0c;IP是各自不同的&#xff09; 靶机&#xff1…

SystemUI手势操作隐藏显示导航栏

在Android 12中&#xff0c;通过SystemUI手势操作来隐藏和显示导航栏主要涉及对系统UI的定制和编程控制。以下是一些实现这一功能的方法&#xff1a; 默认是隐藏 向上滑动 第一类. 使用WindowInsetsController Android 12引入了一个新的WindowInsetsController类&#xff0c;它…

【数据分享】1999—2022年地级市地区生产总值及一二三产构成数据(Shp/Excel格式)

在之前的文章中&#xff0c;我们分享过基于2000-2023年《中国城市统计年鉴》整理的1999-2022年地级市的人口相关数据、各类用地面积数据、污染物排放和环境治理相关数据、房地产投资情况和商品房销售面积、社会消费品零售总额和年末金融机构存贷款余额、一般公共预算收支状况、…

bootchart抓Android系统启动各阶段性能数据

最近在做Android系统启动优化&#xff0c;首要任务是找到启动过程中各阶段耗时点&#xff0c;进而有针对性地进行优化。主要用bootchart抓开机数据&#xff0c;本文主要记录下工具的使用方法。 1.抓开机数据 adb root adb shell ‘touch /data/bootchart/enabled’ adb rebo…

STM32标准库学习笔记-6.定时器-输入捕获

参考教程&#xff1a;【STM32入门教程-2023版 细致讲解 中文字幕】 定时器输入捕获 IC&#xff08;Input Capture&#xff09;输入捕获输入捕获模式下&#xff0c;当通道输入引脚出现指定电平跳变时&#xff0c;当前CNT的值将被锁存到CCR中&#xff0c;可用于测量PWM波形的频率…

8.14-LVS主从+nginx的haproxy+mysql的haproxy+读写分离

一、LVS-主从数据库 # nat # 添加规则 [rootDS ~]# ipvsadm -A -t 192.168.2.130:3306 -s rr [rootDS ~]# ipvsadm -a -t 192.168.2.130:3306 -r 192.168.2.40:3306 -m [rootDS ~]# ipvsadm -a -t 192.168.2.130:3306 -r 192.168.2.42:3310 -m [rootDS ~]# ipvsadm -Ln IP Vir…

计算机毕业设计选什么题目好? springboot 大学志愿填报系统

✍✍计算机毕业编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java、…