算法——滑动窗口(day6)
1004.最大连续1的个数 |||
1004. 最大连续1的个数 III - 力扣(LeetCode)
题目解析:
这道题如果能转化为滑动窗口的话就会很简单,因为我们如果尝试去把0翻转为1再计数的话等到第2轮又得重新翻转回来,费时费力~
那么我们不妨默认就把0当作1,选中一段区间只要里面0的个数不超过k那就可以了。这样就把问题转化为求0的个数不超过k的最长子数组,妥妥用滑动窗口。
老规矩,我们先来用暴力找找灵感:
需要列举的有点多,不过也有很多可优化的空间~
算法解析:
其实当我们转换为滑动窗口后相信看过我前边博客的友友们肯定都知道了,所以我们废话不多说。
在right不断遍历的过程中遇到0就记录其个数,等到不满足条件(sum>k)时说明在它之前已经找到最长子数组了。开始新一轮的寻找,这时候我们的right不用再回来遍历,因为之前都已经遍历并记录在sum中了,所以留在原位移动left即可。
滑动窗口流程:
滑动窗口的两个指针移动规律也很简单:
- right 遇1——> right++
- right 遇0——> sum++,right++
- left 遇1——> left++
- left 遇0——> sum--,left++
代码:
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int sum = 0;int ret = INT_MIN;for (int left = 0, right = 0; right < n; right++){//扩充窗口if (nums[right] == 0){sum++;}//判断,若sum<=k,到下一循环继续扩充//若sum>k,缩小窗口while (sum > k){if (nums[left] == 0){sum--;}left++;}//更新长度ret = max(ret, right - left + 1);}return ret;}
};
1658.将x减到0的最小操作数
1658. 将 x 减到 0 的最小操作数 - 力扣(LeetCode)
题目解析:
这道题从正面来做会很难,因为你要不断考虑是从左边选数还是从右边选数。那么我们不如从另外一个角度来思考这个问题~
首先我们要把通过移除左右两边数使得x==0转换为挑选出左右两区间使得里面的数之和为x.
但两段区间也还是麻烦,我们不妨去挑出处于两区间中间的连续区间。
我们只需要让这个连续区间里面的和为sum-x就可以了,再求出连续区间的长度len,最后n-len反推出真正的最小操作数。
算法解析:
问题转换:求出总数之和为sum-x的最长连续子数组
只要t<a,我们就让right继续往后遍历直到出现t>=a的情况。
而在第二轮开始遍历的时候right其实不用去复位,因为在t>=a的那个节点前面的总和本来就是t<a,left前进一位只会让t更小。所以right是没必要复位的,留在原地就好了。
滑动窗口流程:
最后有一点小细节:
如果题目给的x比我们所有数组之和还大,得特殊处理~
代码:
class Solution {
public:int minOperations(vector<int>& nums, int x) {int len = -1;int n = nums.size();int sum = 0;for (int i : nums){sum += i;}//遍历连续数组之和int target = 0;//连续段的期望数值int a = sum - x;//细节处理if (a < 0) return -1;for (int left = 0, right = 0; right < n; right++){//扩充窗口target += nums[right];//判断,只要target>a就缩小窗口,反之就进行下一轮的扩充while (target > a){//缩小窗口target -= nums[left++];}//只有达到期望数值才可以记录长度if (target == a){len = max(len, right - left + 1);}}//没有达到期望数值,说明找不到if (len == -1){return -1;}else{return n - len;}}
};
相关文章:

算法——滑动窗口(day6)
1004.最大连续1的个数 ||| 1004. 最大连续1的个数 III - 力扣(LeetCode) 题目解析: 这道题如果能转化为滑动窗口的话就会很简单,因为我们如果尝试去把0翻转为1再计数的话等到第2轮又得重新翻转回来,费时费力~ 那么我…...

推荐一款基于Spring Boot 框架开发的分布式文件管理系统,功能齐全,非常便捷(带私活源码)
前言 在数字化时代,文件管理是企业和个人用户的基本需求。然而,现有的文件管理系统往往存在一些痛点,如存储空间有限、文件共享困难、缺乏在线编辑功能、移动端适配性差等。这些问题限制了用户在不同设备和场景下的文件处理能力。 为了解决…...

Mysql-查询
1.基本查询 //查询所有内容 select * from 表名;//查询指定字段 select 字段1,字段2,字段3.....from 表名;//查询时给字段起别名 select 字段1 as 别名1 , 字段2 as 别名2 ... from 表名;//去重查询 select distinct 字段列表 from 表名; …...

广东科学技术职业学院计算机学院领导一行莅临泰迪智能科技参观交流
7月17日,广东科学技术职业学院计算机学院副院长张军、计算机学院副书记吴国庆、计算机学院大数据教学部部长谢文达、科技与校企合作部副部长黄相杰、科技与校企合作部副部长吴胜兵莅临广东泰迪智能科技股份有限公司产教融合实训基地参观交流,泰迪智能科技…...

exo 大模型算力共享;Llama3-70B是什么
目录 exo 大模型算力共享 exo框架的特点 如何使用exo框架 注意事项 结论 Llama3-70B是什么 一、基本信息 二、技术特点 三、性能与应用 四、未来发展 exo 大模型算力共享 exo框架的特点 异构支持:支持多种不同类型的设备,包括智能手机、平板电脑、笔记本电脑以及高…...

测试——Junit
内容大纲: 常用的五个注解 测试用例顺序指定 参数化 测试套件 断言 1. 常用的五个注解 1.1 Test 通常情况下,我们输入要写在main方法下,此时我想直接输出: Test void Test01(){System.out.println("第一个测试用例"); } 1.2 BeforeAll AfterAll BeforeALL在Tes…...
BUG ImportError: cannot import name ‘QAction‘ from ‘PySide6.QtWidgets‘
BUG ImportError: cannot import name ‘QAction’ from ‘PySide6.QtWidgets’ 环境 PySide6 6.7.2详情 在参考 PyQt5 的代码写 Pyside6 的右键菜单时遇到的错误。 错误代码 from PySide6.QtWidgets import QAction错误原因: 在PySdie6中…...

对某次应急响应中webshell的分析
文章前言 在之前处理一起应急事件时发现攻击者在WEB应用目录下上传了webshell,但是webshell似乎使用了某种加密混淆手法,无法直观的看到其中的木马连接密码,而客户非要让我们连接webshell来证实此文件为后门文件且可执行和利用(也是很恼火&a…...

Vue3新特性
Vue3新特性 1、Composition API1.1 什么是 Composition API1.2 常用 Composition API1.2.1 setup1.2.2 ref1.2.3 reactive1.2.4 computed1.2.5 watchEffect、watchPostEffect、watchSyncEffect1.2.6 watch 2、生命周期2.1 Vue3生命周期钩子2.2 vue2 和 vue3 关于生命周期的对比…...

一套功能齐全、二开友好的即时通讯IM工具,提供能力库和UI库,支持单聊、频道和机器人(附源码)
前言 在当今数字化时代,即时通讯(IM)和实时音视频(RTC)功能已成为众多应用的标配。然而,现有的解-决方案往往存在一些痛点,如架构落后、成本高昂、数据安全性和隐私保护不足,以及二次开发和部署的复杂性。 为了解决这些问题&…...

MySQL:JOIN 多表查询
多表查询 在关系型数据库中,表与表之间是有联系的,它们通过 外键 联系在一起,所以在实际应用中,经常使用多表查询。多表查询就是同时查询两个或两个以上的表。 MySQL多表查询是数据库操作中非常重要的一部分,它允许你…...

【机器学习】必会算法模型之:一文掌握 密度聚类,建议收藏。
密度聚类 1、引言2、密度聚类2.1 定义2.2 核心原理2.3 实现步骤2.4 算法公式2.5 代码示例 3、总结 1、引言 在机器学习的无监督学习领域,聚类是一项基础而重要的任务。 聚类算法通过将数据点分组,使同一组内的数据点具有更大的相似性,而组间…...

代码:前端与数据库交互的登陆界面
<!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>登录</title> </head> <body>…...

发电机基础知识:负载组
什么是发电机负载组? 简单地说,负载组是一种可以产生人工电力负载的设备,用于测试发电机并验证发电机组的性能,包括相关组件,以确保通过使发电机发动机达到适当的工作温度和压力来满足适当的负载。 它是如何工作的&a…...

内网安全:各类密码的抓取
Mimikatz在线读取SAM文件 离线读取SAM文件 在线读取lsass进程 离线读取lsass进程 BrowserGhost浏览器密码抓取 Sharp-HackBrowserData浏览器密码抓取 SharpDecryptPwd数据库密码抓取 LaZagne各类密码的抓取 Windows其他类型抓NTLM Hash工具 sam文件和lsass进程就是Wind…...
前端面试题汇总2
1. CSS 中两个 .class1 .class2 从哪个开始解析 在 CSS 中,选择器 .class1 .class2 表示所有 class 为 class1 的元素中的 class 为 class2 的子元素。浏览器解析这个选择器时,从右向左解析。也就是说,浏览器首先找到所有 class 为 class2 的…...

分布式服务框架zookeeper+消息队列kafka
一、zookeeper概述 zookeeper是一个分布式服务框架,它主要是用来解决分布式应用中经常遇到的一些数据管理问题,如:命名服务,状态同步,配置中心,集群管理等。 在分布式环境下,经常需要对应用/服…...

服务攻防-应用协议cve
Cve-2015-3306 背景: ProFTPD 1.3.5中的mod_copy模块允许远程攻击者通过站点cpfr和site cpto命令读取和写入任意文件。 任何未经身份验证的客户端都可以利用这些命令将文件从文件系统的任何部分复制到选定的目标。 复制命令使用ProFTPD服务的权限执行,…...

Springcloud之gateway的使用详解
官网地址:https://docs.spring.io/spring-cloud-gateway/docs/4.0.4/reference/html/ 1.网关入门 helloword 网关不依赖start-web 导入的pom: <!--gateway--> <dependency><groupIdorg.springframework.cloud</groupId><arti…...

中望CAD 建筑 v2024 解锁版下载、安装教程 (超强的CAD三维制图)
前言 中望CAD建筑版是一款国产CAD制图软件,专注于建筑设计领域。中望CAD建筑版拥有丰富多样的建筑图块和图案,完美兼容各类建筑图纸。同时,它提供了绘图标准规范,使绘图更加规范和专业。更值得一提的是,该软件还具备智…...

MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...