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

【leetcode图文详解】特殊数组II : 空间换时间的“记忆化”,越多越好吗?

题目详解

需求:判断给定区间内的元素是否满足“特殊数组”要求

尝试: 暴力求解?

如果试着直接对每个queries中的区间进行检测而不做其他处理,那么最后不出意外地超时了。。

细想优化策略,不难察觉到其中可能存在大量的重复运算

那还等什么(doge)?记忆化!

记忆化

设置rem数组,rem[ i ] = k 意味着nums从 i 到 k 的元素均满足“特殊数组”要求

int *rem = (int *)calloc(sizeof(int), sz+1);
//更新rem示例:
for(int m=st; m<=ed; m++) rem[m] = ed;
一个错误想法:

不妨思考,下面利用 rem 的记录判断符合“特殊数组”的考虑,完善吗?

int st = queries[i][0];//起始位置
int ed = queries[i][1];//终止位置
if(rem[st] != 0 && rem[ed] != 0) return true;

答案是否定的,比如下面这种情况,就会漏掉中间绿色部分的检验。

那怎么办嘞?

其实不难,只要再加上rem值相等的条件就好啦~

if(rem[st] != 0 && rem[ed] != 0 && rem[st] == rem[ed]) return true;

记忆化,越多越好吗?

        按理说,后面的思路应该就很清楚了,只要根据 rem[st] 和 rem[ed] 取值的不同情况,分别检验 & 记忆化处理即可。

        但写完提交,虽然AC了,但是,本以为记忆化能大大提升时间效率的我,却碰上远低于平均值的结果。

 其实,边写的时候,笔者也隐约感觉有些重复,毕竟更新rem的过程本身就是耗费时力的

        于是,笔者试着注释掉一些记忆化操作,保留了两处较为主要的部分,果然,去掉了部分记忆化,反倒轻松多了~

  // 虽然跟大佬们比起来还是差很多(小声),后面笔者会去学习一下优秀代码,再写篇解读文章~

AC代码见下

// 由于分类讨论较多,显得有点冗长(小声)

class Solution {
public:vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {int sz = nums.size();int *rem = (int *)calloc(sizeof(int), sz+1);vector<bool>ret;//返回数组//遍历 queriesfor(int i=0; i<queries.size(); i++){int st = queries[i][0];int ed = queries[i][1];if(rem[st] != 0 && rem[ed] != 0 && rem[st] == rem[ed]) ret.push_back(true);else if(rem[st] != 0){st = rem[st];int j=st+1;for(; j<=ed; j++){if(nums[j]%2 == nums[j-1]%2) {ret.push_back(false);break;}}if(j > ed)	ret.push_back(true);}else if(rem[ed] != 0){for(int k=st+1; k<=ed; k++){if(nums[k]%2 == nums[k-1]%2) {ret.push_back(false); break;}if(rem[k] == rem[ed]){ret.push_back(true);//记忆化for(int m=st; m<=k; m++)rem[m] = rem[ed];break;}}}else{int k=st+1;for(; k<=ed; k++){if(nums[k]%2 == nums[k-1]%2){ret.push_back(false); break;}if(rem[k] != 0) k = rem[k];}if(k > ed){ret.push_back(true);	//记忆化for(int m=st; m<=ed; m++)rem[m] = ed;}}}return ret;}
};
~希望对你有启发~

相关文章:

【leetcode图文详解】特殊数组II : 空间换时间的“记忆化”,越多越好吗?

题目详解 需求&#xff1a;判断给定区间内的元素是否满足“特殊数组”要求 尝试: 暴力求解? 如果试着直接对每个queries中的区间进行检测而不做其他处理&#xff0c;那么最后不出意外地超时了。。 细想优化策略&#xff0c;不难察觉到其中可能存在大量的重复运算 那还等什…...

离线安装prometheus与Grafana实现可视化监控

简介 prometheus 是一个专为云环境设计的开源系统监控和警报工具&#xff0c;它收集并存储多维度的时间序列数据&#xff0c;通过PromQL查询语言提供强大的数据检索能力&#xff0c;并支持可视化及警报功能。而 Grafana 则是一个开源的数据可视化平台&#xff0c;能够与包括Pr…...

【Python学习-UI界面】PyQt5 小部件7-QSpinBox 计数器

样式如下: 一个 QSpinBox 对象向用户呈现一个文本框&#xff0c;右侧有一个上下按钮&#xff0c;显示一个整数。如果按下上下按钮&#xff0c;文本框中的值将增加/减少。 默认情况下&#xff0c;框中的整数从0开始&#xff0c;最高到99&#xff0c;并以步长1变化。对于浮点数…...

[二次元]个人主页搭建

文章目录 域名买一个免费的 框架HexoHexo-Theme-ParticleX Halo 参考 域名 买一个 有钱人玩这个 免费的 github.io 教程在github官方文档有&#xff1b; 框架 Hexo 静态的 Hexo-Theme-ParticleX Argvchsの小窝 Halo 动态的 halo 参考 基于Hexo框架的GitHub个人主页…...

Spring Data JPA 自动创建时间的相关注解和用法

以Springboot项目为例 在实体类上加上注解 EntityListeners(AuditingEntityListener.class)在相应的字段上添加对应的时间注解 LastModifiedDate 和 CreatedDateApplication启动类中添加注解 EnableJpaAuditing...

Java基础之隐式类型转换

类型转换 基本数据类型表示范围大小排序&#xff1a; 在变量赋值及算术运算的过程中&#xff0c;经常会用到数据类型转换&#xff0c;其分为两类&#xff1a; 隐式类型转换 显式类型转换 1 隐式类型转换 情形1&#xff1a;赋值过程中&#xff0c;小数据类型值或变量可以直…...

【数据结构与算法 | 图篇】Dijkstra算法(单源最短路径算法)

1. 前言 由图&#xff1a; 如果我们想要求得节点1到节点5&#xff08;也可以是其他节点&#xff09;的最短路径&#xff0c;我们可以使用Dijkstra算法。 2. 步骤与思路 1. 将所有顶点标记为未访问(顶点类的visited属性设置为false)。创建一个未访问顶点的集合。 2. 为每个顶…...

windows c转linux c要做的事情。

写在开头&#xff1a; 最近的copy项目要转到windows版本了&#xff0c;一直在跟进做这个事情。 直入主题说下移植过程中可能涉及以下几个方面的调整&#xff1a;‌ 编译器和工具链的更改&#xff1a;‌Windows和Linux使用不同的编译器和工具链&#xff0c;‌因此需要在Windo…...

【高等代数笔记】002.高等代数研究对象(二)

1. 高等代数的研究对象 1.4 一元高次方程的求根 a n x n a n − 1 x n − 1 . . . a 1 x a 0 0 a_{n}x^{n}a_{n-1}x^{n-1}...a_{1}xa_{0}0 an​xnan−1​xn−1...a1​xa0​0 等式左边是一元多项式。 所有一元多项式组成的集合称为一元多项式环。...

ubuntu服务器部署的mysql本地连不上的问题

试过了网上的所有方法,都连不上,可以执行: SELECT user, host, plugin FROM mysql.user WHERE user root; 查一下:plungin这个连接插件是不是auth_socket, auth_socket是只能本地连接的插件,需要修改: ALTER USER root% IDENTIFIED WITH mysql_native_password BY your_pass…...

python redis安装

python redis安装 #方法1、 sudo apt-get install redis-server python 支持包&#xff1a; (其实就一个文件&#xff0c;搞过来就能用) sudo apt-get install python-redis #方法2、 sudo pip install redis...

YJ0043定制版抖音电商卷抢购系统带回收商城抖音电商优惠卷投资理财系统

系统是基于逍遥商城二开的系统&#xff0c;pc手机端都新增了邀请码验证 手机端重新定制的UI&#xff0c;前端产品不至于抖音卷也可以自行更改其他产品 用户前端下单&#xff0c;后台订单可以直接回收&#xff0c;后台支持设置默认邀请码和抢卷时间限制...

如何选择图片和视频

文章目录 1. 概念介绍2. 方法与细节2.1 实现方法2.2 具体细节 3. 示例代码4. 内容总结 我们在上一章回中介绍了"如何选择视频文件"相关的内容&#xff0c;本章回中将介绍如何混合选择图片和视频文件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我…...

html+css网页制作 电商华为商城首页 ui还原度100%

htmlcss网页制作 电商华为商城首页 ui还原度100% 网页作品代码简单&#xff0c;可使用任意HTML编辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作&#xff09;。 获取源码…...

EDAS(企业级应用服务)

1 :介绍 1&#xff1a;edas 提供了应用&#xff0c;开发&#xff0c;部署&#xff0c;监控&#xff0c;运维。同时支持 spring cloud, dubbo ,HSF 2:Ali-Tomcat 基于tomcat改造的Servlet容器。支持原有功能&#xff0c;它在启动时会自动加载Pandora&#xff08;潘多拉&#x…...

简单工厂,工厂方法 和 抽象工厂

这三种模式&#xff0c; 都是创建类型的模式&#xff0c; 将对象的创建流程封装起来供客户调用 简单工厂模式 简介: 和策略模式一样&#xff0c;就是针对不通的参数&#xff0c; 返回不通的实例而已 问题: 没有遵循开闭原则&#xff0c; 如果我们想增加一种类&#xff0c; 那…...

python 压力测试脚本

需求&#xff1a; 生成一个12位不重复的随机数将随机数赋值给Json 串中的 orderCode字段将Json用ECB 指定 key为bJXQezYtR4ZSNK4p进行加密并作为值传给{ “data”: “” }设置每秒30个并发持续1分钟调用接口接口输出测试测试报告 代码示例 import json import random import…...

【Linux】多线程7——线程池

1.线程池的概念 1.1.池化技术 池化技术指的是提前准备一些资源&#xff0c;在需要时可以重复使用这些预先准备的资源。 在系统开发过程中&#xff0c;我们经常会用到池化技术。通俗的讲&#xff0c;池化技术就是&#xff1a;把一些资源预先分配好&#xff0c;组织到对象池中…...

Linux Shell实例

1.查空行 答案&#xff1a; awk /^$/{print NR} file1.txt#awk:一个强大的文本分析工具&#xff0c;把文件逐行的读入&#xff0c;以空格为默认分隔符将每行切片&#xff0c;切开的部分再进行分析#处理。 #1&#xff09;基本语法 #awk [选项参数]/pattern1/{action1} /pattern…...

Linux~MySQL数据库具体操作

一、数据库的字符集编码设置 &#xff08;一&#xff09;查看数据库默认的字符集 MariaDB [(none)]> show variables like %character%; ------------------------------------------------------ | Variable_name | Value | ------------…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...