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

LeetCode:2848. 与车的相交点 一次遍历,时间复杂度O(n)

2848. 与车的相交点

today 2848. 与车的相交点

题目描述

给你一个下标从 0开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 inums[i] = [starti, endi] ,其中 s t a r t i start_i starti 是第 i 辆车的起点, e n d i end_i endi 是第 i 辆车的终点。

返回数轴上被车任意部分覆盖的整数点的数目。

示例 1:

输入:nums = [[3,6],[1,5],[4,7]]
输出:7
解释:从 1 到 7 的所有点都至少与一辆车相交,因此答案为 7 。
示例 2:

示例2:

输入:nums = [[1,3],[5,8]]
输出:7
解释:1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交,因此答案为 7 。

提示:

  • 1 <= nums.length <= 100
  • nums[i].length == 2
  • 1 <= starti <= endi <= 100

题目解析

题目要求找出任意部分覆盖的整数点的数目。那么我们可以维护一个数组arr,表示所有整数点,由于1 <= starti <= endi <= 100,我们数组的长度为101,其中arr[i]表示整数点i是否被车覆盖。

遍历nums,对于每辆车,我们将 s t a r t i start_i starti e n d i end_i endi 之间的整数点都标记为true,即arr[starti] = truearr[endi+1] = true

最后遍历arr,统计true的个数即可。

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)

代码实现

C++版本:

class Solution {
public:int numberOfPoints(vector<vector<int>>& nums) {int n=nums.size();int ans=0;vector<bool> arr(101,0);for(int i=0;i<n;i++){for(int j=nums[i][0];j<=nums[i][1];j++){if(!arr[j]){ans++;arr[j]=true;}}}return ans;}
};

Go版本:

func numberOfPoints(nums [][]int) int { arr:=make([]bool,101)ans:=0for i:=range(nums){for j:=nums[i][0];j<=nums[i][1];j++{if(!arr[j]){ans++arr[j]=true}}}return ans
}

Python版本:

class Solution(object):def numberOfPoints(self, nums):n=[False]*101l=len(nums)ans=0for i in range(0,l):for j in range(nums[i][0],nums[i][1]+1):if not n[j]  :ans+=1n[j]=Truereturn ans

相关文章:

LeetCode:2848. 与车的相交点 一次遍历,时间复杂度O(n)

2848. 与车的相交点 today 2848. 与车的相交点 题目描述 给你一个下标从 0开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i &#xff0c;nums[i] [starti, endi] &#xff0c;其中 s t a r t i start_i starti​ 是第 i 辆车的起点&#xff0c; e n …...

Xcode 16 RC (16A242) 发布下载,正式版下周公布

Xcode 16 RC (16A242) - Apple 平台 IDE IDE for iOS/iPadOS/macOS/watchOS/tvOS/visonOS 请访问原文链接&#xff1a;https://sysin.org/blog/apple-xcode-16/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.org Xcode 16 的新功…...

git 更换远程地址的方法

需要将正在开发的代码远程地址改成新的地址&#xff0c;通过查询发现有三个方法可以实现&#xff0c;特此记录。具体方法如下&#xff1a; &#xff08;1&#xff09;通过命令直接修改远程仓库地址 git remote 查看所有远程仓库git remote xxx 查看指定远程仓库地址git remote…...

9. 什么是 Beam Search?深入理解模型生成策略

是不是总感觉很熟悉&#xff1f; 在之前第5&#xff0c;7&#xff0c;8篇文章中&#xff0c;我们都曾经用到过与它相关的参数&#xff0c;而对于早就有着实操经验的同学们&#xff0c;想必见到的更多。这篇文章将从示例到数学原理和代码带你进行理解。 Beam Search 对应的中文翻…...

Spring自定义注解

目录 一、interface 关键字 二、元注解 三、简单实现 四、使用切面执行自定义注解逻辑 1) 首先将刚才的注解修改成放在方法上的&#xff1a; 2) 定义一个切面类&#xff1a; 3&#xff09;将注解放入到接口方法中测试&#xff1a; 五、切点表达式 一、interface 关键字 …...

微信小程序:wx.login或调用uni.login时报错the code is a mock one

微信小程序&#xff0c;调用wx.login或调用uni.login方法&#xff0c;返回the code is a mock one 原因与解决 原因:没有关联真实的 appid&#xff0c;解决办法&#xff1a;绑定真实的微信小程序的appid...

URL的执行流程

基本概念&#xff1a; URL&#xff08;统一资源定位符&#xff0c;Uniform Resource Locator&#xff09;的执行流程是指当你在浏览器中输入一个URL并按下回车键时&#xff0c;从输入URL到最终在浏览器中显示网页的完整过程。 1.解析协议 URL 以协议开头&#xff0c;如 http…...

双指针算法专题(2)

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; 优选算法专题 想要了解双指针算法的介绍&#xff0c;可以去看下面的博客&#xff1a;双指针算法的介绍 目录 611.有效三角形的个数 LCR 1…...

加密与安全_优雅存储用户密码的最佳实践

文章目录 Pre概述最佳实践避免使用MD5、SHA1等快速哈希算法加盐哈希 &#xff08;不推荐&#xff09;使用BCrypt、Argon2等慢哈希算法 (推荐)BCrypt Code1. 自动生成和嵌入盐2. 哈希结果的格式3. 代价因子 BCrypt特点 防止暴力破解1. 登录失败锁定2. 双因素认证&#xff08;2FA…...

【多线程】深入剖析线程池的应用

&#x1f490;个人主页&#xff1a;初晴~ &#x1f4da;相关专栏&#xff1a;多线程 / javaEE初阶 还记得我们一开始引入线程的概念&#xff0c;就是因为进程太“重”了&#xff0c;频繁创建销毁进程的开销是非常大的。而随着计算机的发展&#xff0c;业务上对性能的要求越来越…...

『功能项目』切换职业面板【48】

我们打开上一篇47技能冷却蒙版的项目&#xff0c; 本章要做的事情是切换职业UI面板的功能 首先双击打开Canvas预制体在左上主角面板信息中新建一个button按钮 重命名&#xff08;父物体是按钮Button&#xff0c;子物体Image即可&#xff09; 创建一个Image 设计一下布局 复制三…...

【EasyExcel】@ColumnWidth(value = 20) EasyExcel设置列宽不生效

经过测试发现&#xff0c;只有XLS&#xff0c;ColumnWidth注解才会生效&#xff0c;选择CSV和XLSX都不会生效 //对应的导出实体类 EasyExcel.write(outputStream, Result.class)//excel文件类型&#xff0c;包括CSV、XLS、XLSX.excelType(ExcelTypeEnum.XLS)...

CPU 和 GPU:为什么GPU更适合深度学习?

目录 什么是 CPU &#xff1f; 什么是 GPU &#xff1f; GPU vs CPU 差异性对比分析 GPU 是如何工作的 &#xff1f; GPU 与 CPU 是如何协同工作的 &#xff1f; GPU vs CPU 类型解析 GPU 应用于深度学习 什么是 CPU &#xff1f; CPU&#xff08;中央处理器&#xff09;…...

【机器学习】:解锁数据背后的智慧宝藏——深度探索与未来展望

欢迎来到 破晓的历程的 博客 ⛺️不负时光&#xff0c;不负己✈️ 文章目录 引言一、深入机器学习的内在机制二、最新进展与趋势三、对未来社会的深远影响结语 引言 在上一篇博客中&#xff0c;我们初步探讨了机器学习如何成为解锁数据背后智慧的关键工具。现在&#xff0c;让…...

【Kubernetes】常见面试题汇总(十八)

目录 55.简述 Kubernetes 共享存储的作用&#xff1f; 56.简述 Kubernetes 数据持久化的方式有哪些&#xff1f; 57.简述 Kubernetes PV 和 PVC &#xff1f; 58.简述 Kubernetes PV 生命周期内的阶段&#xff1f; 55.简述 Kubernetes 共享存储的作用&#xff1f; Kubernet…...

无限边界:现代整合安全如何保护云

尽管云计算和远程工作得到广泛采用&#xff0c;零信任网络也稳步推广&#xff0c;但边界远未消失。相反&#xff0c;它已被重新定义。就像数学分形的边界一样&#xff0c;现代网络边界现在无限延伸到任何地方。 不幸的是&#xff0c;传统工具在现代无限边界中效果不佳。现代边…...

HTML贪吃蛇游戏

文章目录 贪吃蛇游戏 运行效果代码 贪吃蛇游戏 贪吃蛇是一款经典的休闲益智游戏。本文将通过HTML5和JavaScript详细解析如何实现一个简易版的贪吃蛇游戏。游戏的主要逻辑包括蛇的移动、碰撞检测、食物生成等功能。以下是游戏的完整代码及注释解析。&#xff08;纯属好玩&#…...

HTML 揭秘:HTML 编码快速入门

HTML 揭秘&#xff1a;HTML 编码快速入门 一 . 前端知识介绍二 . HTML 介绍三 . HTML 快速入门四 . HTML 编辑器 - VSCode4.1 插件安装4.2 修改主题配色4.3 修改快捷键4.4 设置自动保存4.5 创建 HTML 文件4.5 书写 HTML 代码4.6 常见快捷键 五 . 基础标签5.1 字体标签5.1.1 col…...

Ubuntu22.04系统安装opencv步骤简述及问题解决方法

前言 opencv是一个功能强大、开源且跨平台的计算机视觉库&#xff0c;适用于多种编程语言和操作系统&#xff0c;能够帮助开发者构建各种视觉项目。其模块众多&#xff0c;提供了诸多功能&#xff0c;能够进行图像处理、视频处理等等。比如&#xff1a;Highgui模块提供图像用户…...

移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——13.mapset

1. 关联式容器 在初阶阶段&#xff0c;我们已经接触过STL中的部分容器&#xff0c;比如&#xff1a;vector、list、deque、 forward_list(C11)等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面 存储的是元素本身。那什么是关…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

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

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

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...