【LeetCode】3356、零数组变换 II
【LeetCode】3356、零数组变换 II
文章目录
- 一、数据结构-差分-一维差分、二分
- 1.1 数据结构-差分-一维差分、二分
- 1.1.1 题意复述
- 1.1.2 思路
- 1.1.3 手写二分
- 1.1.4 sort.Search() 二分
- 1.1.5 sort.Find() 二分
- 二、多语言解法
一、数据结构-差分-一维差分、二分
1.1 数据结构-差分-一维差分、二分
1.1.1 题意复述
题意复述: 有 nums[] 数组(如 [2, 0, 2]), 有 queries[] 数组(如 [[0,2,1], [0,2,1], [1,1,3]])
遍历 queries, 对每个 queries[i] 为 [li, ri, vali]
可以把 介于 nums[li…ri] 的元素的子集, 减去 [0…vali] 的数
问最终需操作几个 queries[], 可使 nums[] 全部变为 0. 记答案为 k(即操作的是 queries[0…k])
1.1.2 思路
因为操作的是 nums[li…ri] 的【子集】, 且减小的数 【最多】为 vali, 所以 k【越多越好】.
即 k 越多, 越满足答案. 【具备单调性】, 所以可用 【二分法】.
二分法: 是指, 从 queries[] 数组的长度的二分, 即 queries[0…len(queries)] 中 k 从 i = 0, j = len(queries) 的 二分.
二分的 check() 函数, 即为 【LeetCode 3355】 的过程.
最终返回二分的 k 即可.
二分法的注意: 用 开区间 确实更容易写边界条件
- 没有 +1 或 -1 的判断
- 最后返回的值 肯定是 l 或 r, 只需根据 二分的分支 确定 l 的含义, r 的含义, 即可
1.1.3 手写二分
// go
func minZeroArray(nums []int, queries [][]int) int {n := len(nums)check := func(k int) bool {d := make([]int, n+1) // 差分数组for _, q := range queries[:k] { // k锁定了queries[]的前k项start, end, val := q[0], q[1], q[2]d[start]+=vald[end+1]-=val}now := 0for i := range n {now += d[i]if now < nums[i] {return false}}return true}q := len(queries)l, r := -1, q+1 // 左开右开区间for l + 1 < r {m := l + (r-l)>>1if check(m) {r = m // m 已经符合, 但为了找更小的, 再向左找} else {l = m // 不符合, 则需找更大的(向右找), 因为k越大越符合题意}}if r <= q {return r // 因为二分中 check(m) 符合时, r 为 m. 所以最终返回的 r 就是符合题意的}return -1 // r == q+1
}
1.1.4 sort.Search() 二分
func minZeroArray(nums []int, queries [][]int) int {n := len(nums)check := func(k int) bool {d := make([]int, n+1) // 差分数组for _, q := range queries[:k] { // k锁定了queries[]的前k项start, end, val := q[0], q[1], q[2]d[start]+=vald[end+1]-=val}now := 0for i := range n {now += d[i]if now < nums[i] {return false}}return true}q := len(queries)ans := sort.Search(q+1, func(k int) bool { // sort.Search() 是找第一个 true 的下标return check(k)})if ans <= q {return ans}return -1 // r == q+1
}
1.1.5 sort.Find() 二分
func minZeroArray(nums []int, queries [][]int) int {n := len(nums)check := func(k int) bool {d := make([]int, n+1) // 差分数组for _, q := range queries[:k] { // k锁定了queries[]的前k项start, end, val := q[0], q[1], q[2]d[start]+=vald[end+1]-=val}now := 0for i := range n {now += d[i]if now < nums[i] {return false}}return true}q := len(queries)// 因为 sort.Search() 是找第一个 f() == true 的下标, 而 sort.Find() 是找第一个 f() <= 0 的下标, 所以此处定义 sort.Find() 的 f 为 if check(k) {return 0}ans, found := sort.Find(q+1, func(k int) int { // sort.Find() 是找第一个 f() <= 0 的下标if check(k) {return 0 // <= 0}return 1})if found {return ans}return -1 // r == q+1
}
二、多语言解法
C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts Cpp/Go/Python/Rust/Js/Ts
// cpp
// go 同上
# python
// rust
// js
// ts
相关文章:
【LeetCode】3356、零数组变换 II
【LeetCode】3356、零数组变换 II 文章目录 一、数据结构-差分-一维差分、二分1.1 数据结构-差分-一维差分、二分1.1.1 题意复述1.1.2 思路1.1.3 手写二分1.1.4 sort.Search() 二分1.1.5 sort.Find() 二分 二、多语言解法 一、数据结构-差分-一维差分、二分 1.1 数据结构-差分…...
Vue 子组件修改父组件传过来的值的三种方式
方式1:子组件发送emit,触发父组件修改 父组件 <template><div><son :count"count" updateCount"updateCount" /></div> </template><script> import son from "./son"; export def…...
4.Python 数字类型
Python 数字类型总结 文章目录 Python 数字类型总结1. 数字类型概述特点 2. 数字类型的创建与赋值3. 数字类型转换4. 数学运算与函数math 模块cmath 模块 5. 随机数生成6. 三角函数7. 数学常量 总结 Python 提供了多种数字类型来存储和操作数值数据。这些类型包括整数、浮点数、…...
MacOs 日常故障排除troubleshooting
1. 关闭开机自启动 app X macOs 15.1 System settings -> General -> Login Items & Extensions->Open at Login -> Select app X and click -...
(补)算法刷题Day19:BM55 没有重复项数字的全排列
题目链接 给出一组数字,返回该组数字的所有排列 例如: [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. (以数字在数组中的位置靠前为优先级,按字典序排列输出。) 思路: 使用回…...
golang中的值传递与引用传递,如何理解结构体的方法?
先从一个例子说起 type Counter struct {count int }func (c Counter) Inc() {c.count }func test1() {c : Counter{}do : func() {for i : 0; i < 10; i {c.count}fmt.Println("done")}go do()go do()time.Sleep(3 * time.Second)fmt.Println(c.count) }func te…...
linux部署ansible自动化运维
ansible自动化运维 1,编写ansible的仓库(比赛已经安装,无需关注) 1、虚拟机右击---设置---添加---CD/DVD驱动器---完成---确定 2、将ansible.iso的光盘连接上(右下角呈绿色状态) 3、查看光盘挂载信息 df -h…...
docker—私有仓库搭建
docker—私有仓库搭建 HTTP 部署 docker run -d \-p 5000:5000 \--restartalways \--name registry \-v /opt/data/registry:/var/lib/registry \registry:2使用官方的 registry 镜像来启动私有仓库。默认情况下,仓库会被创建在容器的 /var/lib/registry 目录…...
【SpringAOP】深入浅出SpringAOP从原理到源码
AOP对象是如何创建的 对于熟悉Spring IOC流程源码的同学来说,一定了解bean的整个生命周期,也就是从实例化、属性填充、初始化三个过程。那么对于Bean 工厂来说,是如何保证需要创建代理的对象创建代理的呢。 从图中可以看到,本质…...
Java 从查询超时到性能提升 (实战讲解)
目录 1. 问题所示2. 原理分析3. 解决方法3.1 代码优化3.2 索引优化3.3 删数据 1. 问题所示 查询返回速度慢,导致前端页面无数据显示 前端和后端均未报错,但后端未能在合理时间内返回结果到前端 后端没有报错日志 2. 原理分析 单独分析代码中的对算法…...
《C 语言携手 PaddlePaddle C++ API:开启深度学习开发新征程》
在深度学习领域,PaddlePaddle 作为一款强大的深度学习框架,为开发者提供了丰富的功能和高效的计算能力。而 C 语言,凭借其高效性和广泛的应用场景,与 PaddlePaddle 的 C API 相结合,能够为深度学习开发带来独特的优势。…...
Mysql之存储过程
MySQL 存储过程(Stored Procedure) 1. 概念 存储过程是一组预编译的 SQL 语句集合,可以通过调用名称来执行。存储过程可以接收参数,并支持复杂的业务逻辑(如条件语句、循环、异常处理等)。它们可以提高代…...
XV6 开发环境搭建
Step 1 搭建ubuntu 20.04 虚拟机 注意:一定要使用ubuntu 20.04,该版本可以直接通过deb安装gnu编译工具链。 安装完虚拟机后,换apt源。 ubuntu20.04镜像下载链接 设置root账户密码: sudo passwd root Step 2 下载解压qemu 5.1.0 wget ht…...
Windows 系统下 Python 环境安装
一、引言 Python 作为一种广泛应用的编程语言,在数据分析、人工智能等领域发挥着重要作用。本文将详细介绍在 Windows 系统上安装 Python 环境的步骤。 二、安装前准备 系统要求 Windows 7 及以上版本一般都能支持 Python。硬件方面,通常 2GB 内存、几…...
VMware Workstation的有线连接消失了
进入/var/lib目录下 cd /var/lib 查看是否存在NetworkManager 文件 ls 将其删除,然后虚拟机reboot一下。 sudo rm -r NetworkManager reboot 解决了,可以联网...
73页车企大数据平台规划与数据价值挖掘应用咨询项目方案解读
该项目旨在帮助乘用车公司规划大数据平台并提高数据挖掘应用水平,以满足业务部门对数据的需求,同时保证数据完整性和真实性。数据应用体系现状存在数据孤岛和数据关注维度不统一的问题,导致业务部门无法便捷使用数据并无法进行业务预测。大数…...
MIF格式详解,javascript加载导出 MIF文件示例
MIF 格式详解 MIF(MapInfo Interchange Format)是由Pitney Bowes Software开发的一种文本格式,用于存储地理空间数据。它通常与地图可视化和地理信息系统(GIS)相关联。MIF文件通常成对出现,一个.mif文件用…...
若依实现图片上传时自动添加水印
文章目录 总体思路1. 修改通用上传方法2. 去除文件路径前两级目录3. 添加水印方法运行效果总结 为了解决图盗用,并有效保护图片版权,若依项目需要实现一个功能:上传图片时,自动在图片上添加水印。这不仅可以有效防止盗用ÿ…...
用于日语词汇学习的微信小程序+ssm
日语词汇学习小程序是高校人才培养计划的重要组成部分,是实现人才培养目标、培养学生科研能力与创新思维、检验学生综合素质与实践能力的重要手段与综合性实践教学环节。本学生所在学院多采用半手工管理日语词汇学习小程序的方式,所以有必要开发日语词汇…...
【信息系统项目管理师】高分论文:论信息系统项目的范围管理(融媒体发布系统)
更多内容请见: 备考信息系统项目管理师-专栏介绍和目录 文章目录 正文1、规划范围管理2、收集需求3、定义范围4、创建WBS5、确认范围6、控制范围正文 我市xx社区作为智慧社区建设的试点社区,将通过各种创新技术手段,促进小区公共服务智能管理应用,实现社区中的基础设施、环…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...
【深度学习新浪潮】什么是credit assignment problem?
Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...
网页端 js 读取发票里的二维码信息(图片和PDF格式)
起因 为了实现在报销流程中,发票不能重用的限制,发票上传后,希望能读出发票号,并记录发票号已用,下次不再可用于报销。 基于上面的需求,研究了OCR 的方式和读PDF的方式,实际是可行的ÿ…...
