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 一、矩阵中的蛇 只要按照题目要求模拟即可,代码如下 class Solution { public:int finalPositionOfSnake(int n, vector<string>& commands…...
最佳的iPhone解锁软件和应用程序
在探讨最佳的iPhone解锁软件和应用程序时,我们需要考虑多个方面,包括软件的解锁能力、易用性、安全性、兼容性以及用户评价等。以下是对当前市场上几款优秀iPhone解锁软件和应用程序的详细分析,旨在为用户提供全面而深入的指导。 一、奇客iO…...
初等函数和它的表达式
常量函数,幂函数,指数函数,对数函数,三角函数和反三角函数成为基本初等函数。基本初等函数经过有限四则运算和符合运算得到的函数称为初等函数。 1. 常量函数 表达式: (其中 c 是常数)参数的意…...
Android 12系统源码_多屏幕(二)模拟辅助设备功能开关实现原理
前言 上一篇我们通过为Android系统开启模拟辅助设备功能开关,最终实现了将一个Activity显示到多个屏幕的效果。 本篇文章我们具体来分析一下当我们开启模拟辅助设备功能开关的时候,Android系统做了什么哪些操作。 一、模拟辅助设备功能开关应用位置 …...
【Go语言初探】(二)、项目文件结构和GOPATH设置
一、go语言项目文件结构 由go/bin、go/src和go/pkg三个子文件夹组成,见下图: 实际项目: 二、gopath路径变量设置 在项目中创建main.go文件后,IDE会提示设置GOPATH路径: 点击“configure GOPATH”,设置GOP…...
三种简单排序:插入排序、冒泡排序与选择排序 【算法 05】
三种简单排序:插入排序、冒泡排序与选择排序 在编程中,排序算法是基础且重要的知识点。虽然在实际开发中,我们可能会直接使用标准库中的排序函数(如C的std::sort),但了解并实现这些基础排序算法对于理解算法…...
Python -- GUI图形界面编程—GUI编程实例 博主也在持续学习中[ 持续更新中!!! 欢迎白嫖 也求粉啊啊啊~ ]
本文介绍了GUI的图形界面编程(相关视频是哔站上的应该搜这个题目就能找到),文章还是很基础的,反正我是小白从0开始,主要的结构tinkter库、重要组件简介(这个不用死记硬背 用的时候再说)、Label&…...
Vue2和Vue3中的diff算法
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、diff算法是什么?二、vue2中的diff算法三、vue3中的diff算法总结 前言 一、diff算法是什么? diff算法很早就存在了,一开…...
springboot使用aop或Jackson进行数据脱敏
1.aop 启动类加EnableAspectJAutoProxy 自定义注解,在实体类中使用表示被脱敏字段 建立aop切面类 可能这里gpt会建议你用Pointcut("execution(public * com.xx.aop..*.get*(..))")这种方式拦截,这种我试了,拦截不住。猜测在mvc返…...
【Solidity】基础介绍
数据类型 值类型 值类型的变量在赋值或作为函数参数传递时会被复制。 布尔类型:bool整数类型: 无符号:uint8、uint16、…、uint256 (uint256 可简写为 uint)有符号:int8、int16、…、int256 (int256可简写为 int) 地址类型&…...
【SpringBoot3】双向实时通讯 websocket
文章目录 一、Websocket使用步骤二、示例1:继承抽象类 AbstractWebSocketHandler后端代码前端代码 三、示例2:使用注解ServerEndpoint后端代码前端代码 四、前端代码封装 一、Websocket使用步骤 在Spring Boot中使用WebSocket是一个常见的需求ÿ…...
搭建内网开发环境(一)|基于docker快速部署开发环境
引言 最近因需要搭建一套简易版的纯内网的开发环境,服务器采用 centos8.0,容器化技术采用 docker 使用 docker-compose 进行容器编排。 该系列教程分为两大类: 软件安装和使用,这类是开发环境常用的软件部署和使用,涉…...
MATLAB R2023b配置Fortran编译器
MATLAB R2023b配置Fortran编译器 引言1. 安装Visual Studio 20192. 安装Intel API20243. 配置xml文件文件4. 设置环境变量5. MATLAB编译Fortran 引言 当我们需要用到MATLAB编译Fortran代码后进行调用计算时,整个配置流程较繁琐。下面以MATLAB R2023b为例࿰…...
2024新型数字政府综合解决方案(七)
新型数字政府综合解决方案通过集成人工智能、大数据、区块链和云计算技术,创建了一个高度智能化和互联互通的政府服务平台,旨在全面提升行政效率、服务质量和透明度。该平台实现了跨部门的数据整合与实时共享,利用人工智能进行智能决策支持和…...
搭建高可用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分页内容截断问题
代码地址:https://github.com/HFQ12333/export-pdf.git html2canvas jspdf方案是前端实现页面打印的一种常用方案,但是在实践过程中,遇到的最大问题就是分页截断的问题:当页面元素超过一页A4纸的时候,连续的页面就会…...
14 地址映射
14 地址映射 1、地址划分2、相关函数2.1 ioremap/iounmap2.2 mmap地址映射 3、总结 1、地址划分 明确:在linux系统中,不管是应用程序还是驱动程序,都不允许直接访问外设的物理地址,要想访问必须将物理地址映射到用户虚拟地址或者内核虚拟地址࿰…...
Java Resilience4j-RateLimiter学习
一. 介绍 Resilience4j-RateLimiter 是 Resilience4j 中的一个限流模块,我们对 Resilience4j 的 CircuitBreaker、Retry 已经有了一定的了解,现在来学习 RateLimiter 限流器; 引入依赖; <dependency><groupId>io.g…...
Nginx--地址重写Rewrite
一、什么是Rewrite Rewrite对称URL Rewrite,即URL重写,就是把传入Web的请求重定向到其他URL的过程 URL Rewrite最常见的应用是URL伪静态化,是将动态页面显示为静态页面方式的一种技术。比如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的配置装配参考: WebFlux是Spring 5.0框架推出的…...
ipad作为扩展屏的最简单方式
将iPad用作扩展屏幕有几种简单而有效的方法。以下是几种常见的方式: 1. Sidecar(苹果官方功能) 适用设备:iPad和Mac(macOS Catalina及以上版本)。功能:Sidecar 是苹果官方的功能,可…...
【卡码网Python基础课 17.判断集合成员】
目录 题目描述与分析一、集合二、集合的常用方法三、代码编写 题目描述与分析 题目描述: 请你编写一个程序,判断给定的整数 n 是否存在于给定的集合中。 输入描述: 有多组测试数据,第一行有一个整数 k,代表有 k 组测…...
生物研究新范式!AI语言模型在生物研究中的应用
–https://doi.org/10.1038/s41592-024-02354-y 留意更多内容,欢迎关注微信公众号:组学之心 Language models for biological research: a primer 研究团队及研究单位 James Zou–Department of Biomedical Data Science, Stanford University, Stan…...
python语言day08 属性装饰器和property函数 异常关键字 约束
属性装饰器: 三个装饰器实现对私有化属性_creat_time的get,set,del方法; 三个装饰器下的方法名都一样,通过message.creat_time的不同操作实现调用get,set,del方法。 __inti__: 创建并…...
day01JS-数据类型-01
1. 浏览器内核 通常所谓的浏览器内核也就是浏览器所采用的渲染引擎,渲染引擎决定了浏览器如何显示网页的内容以及页面的格式信息。不同的浏览器内核对网页编写语法的解释也有不同,因此同一网页在不同的内核的浏览器里的渲染(显示)…...
MATLAB 手动实现一种高度覆盖值提取建筑物点云的方法(74)
专栏往期文章,包含本章 MATLAB 手动实现一种高度覆盖值提取建筑物点云的方法(74) 一、算法介绍二、算法实现1.代码2.效果总结一、算法介绍 手动实现一种基于高度覆盖值的建筑物点云提取方法,适用于高大的城市建筑物,比只利用高度提取建筑物的方法更加稳定和具有价值,主要…...
git的下载与安装(Windows)
Git是一个开源的分布式版本控制系统(Distributed Version Control System,简称DVCS),它以其高效、灵活和强大的功能,在现代软件开发中扮演着至关重要的角色。 git官网:Git (git-scm.com) 1.进入git官网 2…...
腾讯云AI代码助手 —— 编程新体验,智能编码新纪元
阅读导航 引言一、开发环境介绍1. 支持的编程语言2. 支持的集成开发环境(IDE) 二、腾讯云AI代码助手使用实例1. 开发环境配置2. 代码补全功能使用💻自动生成单句代码💻自动生成整个代码块 3. 技术对话3. 规范/修复错误代码4. 智能…...
使用 ESP32 和 TFT 屏幕显示实时天气信息 —— 基于 OpenWeatherMap API
实时监测环境数据是一个非常常见的应用场景,例如气象站、智能家居等。这篇博客将带你使用 ESP32 微控制器和一个 TFT 屏幕,实时显示当前城市的天气信息。通过 OpenWeatherMap API,我们能够获取诸如温度、天气情况以及经纬度等详细的天气数据&…...
高阶数据结构——B树
1. 常见的搜索结构 以上结构适合用于数据量相对不是很大,能够一次性存放在内存中,进行数据查找的场景。如果数据量很大,比如有100G数据,无法一次放进内存中,那就只能放在磁盘上了,如果放在磁盘上࿰…...
Vue2中watch与Vue3中watch对比和踩坑
上一节说到了 computed计算属性对比 ,虽然计算属性在大多数情况下更合适,但有时也需要一个自定义的侦听器。这就是为什么 Vue 通过 watch 选项提供了一个更通用的方法,来响应数据的变化。当需要在数据变化时执行异步或开销较大的操作时&#…...
在Java程序中执行Linux命令
在Java中执行Linux命令通常涉及到使用Java的运行时类 (java.lang.Runtime) 或者 ProcessBuilder 类来启动一个外部进程 1. 使用 Runtime.exec() Runtime.exec() 方法可以用来执行一个外部程序。它返回一个 Process 对象,可以通过这个对象与外部程序交互࿰…...
微信小程序在不同移动设备上的差异导致原因
在写小程序的时候用了rpx自适应单位,但是还是出现了在不同机型上布局不统一的问题,在此记录一下在首页做一个输入框,在测试的时候,这个输入框在不同的机型上到处跑,后来排查了很久都不知道为什么会这样 解决办法是后 …...
快速体验fastllm安装部署并支持AMD ROCm推理加速
序言 fastllm是纯c实现,无第三方依赖的高性能大模型推理库。 本文以国产海光DCU为例,在AMD ROCm平台下编译部署fastllm以实现LLMs模型推理加速。 测试平台:曙光超算互联网平台SCNet GPU/DCU:异构加速卡AI 显存64GB PCIE&#…...
报错:java: javacTask: 源发行版 8 需要目标发行版 1.8
程序报错: Executing pre-compile tasks... Loading Ant configuration... Running Ant tasks... Running before tasks Checking sources Copying resources... [gulimail-coupon] Copying resources... [gulimail-common] Parsing java… [gulimail-common] java…...
【数据结构篇】~单链表(附源码)
【数据结构篇】~链表 链表前言链表的实现1.头文件2.源文件 链表前言 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 1、链式机构在逻辑上是连续的,在物理结构上不一定连续 2、结点一般是从…...
旋转图像(LeetCode)
题目 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 解题 def rotate(matrix):n len(matrix)# 矩阵转置for i in range(n):for…...
入门 - vue中v-model的实现原理和完整用法详解
v-model介绍 v-model是vue的双向绑定的指令,能将页面上控件输入的值同步更新到相关绑定的data属性,也会在更新data绑定属性时候,更新页面上输入控件的值。在view层,model层相互需要数据交互,即可使用v-model。 双向绑…...
【区块链+金融服务】港融区域股权服务平台 | FISCO BCOS应用案例
中国证监会在 2020 年启动了区块链建设试点工作,提出建设基于区块链的场外市场登记系统和交易报告库,利 用区块链去中心化、不易篡改、安全稳定等技术特点,构建区域性股权市场数字化信任机制,为区域性股权市场 提供基础支撑设施。…...
Nginx反向代理和前后端分离项目打包部署
Nginx反向代理 Nginx的定位:主要用于做反向代理,一般都是用它来做前端页面的服务器,动态资源代理到后端服务器。这样做的好处是可以避免跨域请求带来的不便。 使用Nginx主要是对Nginx中的nginx.conf文件进行配置: 虚拟主机配置…...
Spring 中ApplicationContext
ApplicationContext 是 Spring 框架中最重要的接口之一,用于提供 Spring IoC 容器的功能。它是一个比 BeanFactory 更高级的容器,负责管理 Spring bean 的生命周期,同时提供对各种企业服务的集成,例如事件传播、国际化、弱引用等。…...
python之时间 datetime、date、time、timedelta、dateutil
在 Python 中,处理日期和时间的常用库是 datetime。此外,还有一些第三方库如 pytz 和 dateutil 可以帮助处理时区和日期解析。 1. 使用 datetime 模块 导入模块 from datetime import datetime, date, time, timedelta获取当前日期和时间 now datet…...
【机器学习第11章——特征选择与稀疏学习】
机器学习第11章——特征选择与稀疏学习 11.特征选择与稀疏学习11.1子集搜索与评价子集搜索子集评价 11.2 过滤式选择11.3 包裹式选择11.4 嵌入式选择11.5 稀疏表示与字典学习稀疏表示字典学习 11.6 压缩感知 11.特征选择与稀疏学习 11.1子集搜索与评价 特征:描述物…...
LeetCode-day43-3137. K 周期字符串需要的最少操作次数
LeetCode-day43-3137. K 周期字符串需要的最少操作次数 题目描述示例示例1:示例2: 思路代码 题目描述 给你一个长度为 n 的字符串 word 和一个整数 k ,其中 k 是 n 的因数。 在一次操作中,你可以选择任意两个下标 i 和 j&#x…...
基于springboot的智能家居系统
TOC springboot198基于springboot的智能家居系统 研究背景与现状 时代的进步使人们的生活实现了部分自动化,由最初的全手动办公已转向手动自动相结合的方式。比如各种办公系统、智能电子电器的出现,都为人们生活的享受提供帮助。采用新型的自动化方式…...
【从问题中去学习k8s】k8s中的常见面试题(夯实理论基础)(七)
本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》:python零基础入门学习 《python运维脚本》: python运维脚本实践 《shell》:shell学习 《terraform》持续更新中:terraform_Aws学习零基础入门到最佳实战 《k8…...
C:每日一练:单身狗(2.0版本)
前言: 今天在刷题的时候突然看到一道题,疑似一位故题。仔细一看,欸!这不是就是单身狗的升级版吗?我想那必须再安排一篇,不过由于本篇文章与上一篇单身狗文章所涉及的知识点基本相同,所以还请大…...
打破接口壁垒:适配器模式让系统无缝对接
适配器模式(Adapter Pattern)是一种结构型设计模式,它允许不兼容的接口之间协同工作。主要用途是将一个类的接口转换成客户期望的另一个接口,使得原本接口不兼容的对象可以一起工作。 一、适配器模式的组成 目标接口(…...
U-Boot 命令使用
U-Boot 是一种常用的引导加载程序,用于引导嵌入式系统。它提供了一系列命令以进行系统配置、引导操作和调试。 以下是一些常见的 U-Boot 命令及其用法: bootm:从指定的内存地址启动操作系统映像。 用法:bootm [addr] bootz&…...
谷歌的高级指令有哪些
今天会分享一些组合用法,这样就能节省许多时间可以放在跟进客户上面(本文只介绍谷歌的搜索指令,并无推广) part one 谷歌常用的搜索引擎指令: 1、Inurl,在网址中 2、Intext,在网页内容中 3、…...