【算法挨揍日记】day06——1004. 最大连续1的个数 III、1658. 将 x 减到 0 的最小操作数

 

 1004. 最大连续1的个数 III

1004. 最大连续1的个数 III

题目描述: 

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。

 解题思路:

首先题目要我们求出的最多翻转k个0后(可以翻转【0,k】个0,不一定要全翻转)的连续1最多的子数组的长度

我们可以用left,right滑动窗口的思想,定一个zero来记录0的个数,right不断向右走,当遇到nums【right】等于0时,zero++,当zero的个数大于k的时候,left先右走,当遇到nums【left】等于0时,zero--直到zero<=k,然后更新length的大小

解题代码:

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int length=0;int n=nums.size();int zero=0;int left=0,right=0;while(right<n){if(nums[right]==0)zero++;while(zero>k){if(nums[left++]==0)zero--;}length=max(length,right-left+1);right++;}return length;}
};

 1658. 将 x 减到 0 的最小操作数

1658. 将 x 减到 0 的最小操作数

题目描述: 

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1 。

解题思路:

本题是要不断从左右两边减一个数,使x减为0,我们可以发现左右两边减的数组是两个连续区间,也就是说整个大数组被分成了三个小数组,我们可以转换一下思想:变为求中间数组之和等于target(大数组之和-x)的最长长度,也就是变成了子数组问题

值得注意的是length应该初始化为-1,而不是0,因为当length=0有两种情况

  • 当数组为【5,6,7,8,9】,而x=4,中间数组每个数都大于x
  • 刚好length=0,每个元素都要出的情况

解题代码:

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(int i=0;i<nums.size();i++)sum+=nums[i];int target=sum-x;if(target<0)  return -1;int n=nums.size();int length=-1;for(int left=0,right=0,num=0;right<n;right++){num+=nums[right];while(num>target)num-=nums[left++];if(num==target)length=max(length,right-left+1);}if(length==-1)return length;else return n-length;}
}; 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/140032.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2023华为杯数模C题——大规模创新类竞赛评审方案研究

B题——大规模创新类竞赛评审方案研究 思路&#xff1a;采用数据分析等手段改进评分算法性能 完成情况(1-2问已经完成) 代码下载 问题一 在每个评审阶段&#xff0c;作品通常都是随机分发的&#xff0c;每份作品需要多位评委独立评审。为了增加不同评审专家所给成绩之间的可比…

Android ANR日志分析

会造成ANR的场景&#xff1a; Service Timeout&#xff1a;前台服务在20s内未执行完成&#xff0c;后台为200s&#xff1b; BroadcastQueue Timeout&#xff1a;前台广播在10s内未执行完成&#xff0c;后台为60s&#xff1b; ContentProvider Timeout&#xff1a;内容提供者在…

SAP Oracle表空间扩展技术手册

1、DBACOCKPIT下查看表空间 当表空间不足(达到99%)时,需要按以下步骤扩充表空间(每次扩充20000M,20G): (也可以通过DB13,DB02查看表空间) 新浪博客 Tablespace PSAPSR3 is 100% used | SAP Community Oracle是通过增加数据文件的方式来为表空间扩容。为指定表空间增…

BST搜索二叉树

目录 二叉搜索树概念 ​编辑 1 二叉搜索树的构建 2. 二叉搜索树的删除 3二叉搜索树中放入元素 4. 二叉搜索树中元素的删除 5. 二叉搜索树中元素的遍历 6 二叉搜索树中元素的查找 7二叉搜索树的拷贝构造 二叉搜索树概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一…

WeCanStudio工具套件介绍

直接上视频,在超燃的《天马座幻想》的背景音乐下&#xff0c;再次了解一下该工具套件吧。 WeCanStudio开发套件介绍

LeetCode(力扣)96. 不同的二叉搜索树Python

LeetCode96. 不同的二叉搜索树 题目链接代码 题目链接 https://leetcode.cn/problems/unique-binary-search-trees/description/ 代码 class Solution:def numTrees(self, n: int) -> int:dp [0] * (n 1)dp[0] 1for i in range(1, n 1):for j in range(1, i 1):dp[…

基于华为云云耀云服务器L实例开展性能评测|MySQL性能测评

基于华为云云耀云服务器L实例开展性能评测&#xff5c;MySQL性能测评 1. 测试环境介绍2. 测试环境搭建3. 测试工具3.1. mysqlslap3.2. sysbench 1. 测试环境介绍 随着云计算时代的进一步深入&#xff0c;越来越多的中小企业企业与开发者需要一款简单易用、高能高效的云计算基础…

C++核心编程——P45-52继承

继承 继承是面向对象三大特性之一 有些类与类之间存在特殊的关系&#xff0c;例如下图中: 我们发现&#xff0c;定义这些类的时候&#xff0c;下级别的成员除了拥有上一级的共性&#xff0c;还有自己的特性。 这时候我们就可以考虑利用继承的技术&#xff0c;减少重复代码量…

【一、虚拟机vmware安装】

安装虚拟机 下载 官方下载地址&#xff1a;https://www.vmware.com/cn.html 大概流程就是&#xff0c;最重要的事最后一步

【WSN】基于蚁群算法的WSN路由协议(最短路径)消耗节点能量研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

【初阶数据结构】二叉树全面知识总结

二叉树详解 树的概念及其结构树的概念树的相关概念树的表示方法孩纸兄弟表示法双亲表示法&#xff08;并查集&#xff09; 树的实际应用 二叉树二叉树的概念二叉树的种类二叉树的性质二叉树的存储结构 二叉树顺序结构的实现堆的概念及结构堆向上、向下调整法堆的插入堆的删除堆…

YOLOv5如何训练自己的数据集

文章目录 前言1、数据标注说明2、定义自己模型文件3、训练模型4、参考文献 前言 本文主要介绍如何利用YOLOv5训练自己的数据集 1、数据标注说明 以生活垃圾数据集为例子 生活垃圾数据集&#xff08;YOLO版&#xff09;点击这里直接下载本文生活垃圾数据集 生活垃圾数据集组成&…

[Linux入门]---初识冯诺依曼体系

文章目录 1.背景知识2.冯诺依曼体系结构 1.背景知识 冯诺依曼&#xff08;John von Neumann&#xff09;&#xff0c;被称为“计算机之父”&#xff0c;确定了计算机的体系结构——即“冯诺依曼结构”&#xff1b;我们常见的计算机&#xff0c;如笔记本。我们不常见的计算机&am…

蓝桥杯每日一题2023.9.23

4961. 整数删除 - AcWing题库 题目描述 分析 注&#xff1a;如果要进行大量的删除操作可以使用链表 动态求最小值使用堆&#xff0c;每次从堆中取出最小值的下标然后在链表中删除 注意long long 代码解释&#xff1a; while(k --){auto t q.top();q.pop();res t.first;i…

经典题记录 字符串相加/相乘

1. LeetCode 415 字符串相加 代码一&#xff1a;代码简短&#xff0c;但需要借助额外的一个string来保存结果&#xff0c;更占用内存。 class Solution { public:string addStrings(string num1, string num2) {string ans"";int size1num1.size();int size2num2.si…

qt 6知识集

1.Use multi-arg instead [clazy-qstring-arg] 存在过个arg&#xff0c;连写形式如下&#xff1a; QString("%1 %2").arg(a).arg(b);QString("%1 %2").arg(a, b); // one less temporary heap allocation详见参考文献[1]。 2.widget运行后正常打开却看不…

基于Java的酒店管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…

Three.js后期处理简明教程

后期处理&#xff08;Post Processing&#xff09;通常是指对 2D 图像应用某种效果或滤镜。 在 THREE.js 中我们有一个包含一堆网格物体的场景。 我们将该场景渲染为 2D 图像。 通常&#xff0c;该图像会直接渲染到画布中并显示在浏览器中&#xff0c;但我们可以将其渲染到渲染…

双向链表的实现(增删查改)——最好理解的链表

双向链表的实现 一&#xff0c;双向链表的特点二&#xff0c;双向链表的结构三&#xff0c;双向链表的内容实现3.1创建node节点3.2初始化3.3打印3.4插入3.4.1尾插3.4.2头插3.4.3在pos位置上插入 3.5删除3.5.1尾删3.5.2头删3.5.3删除pos位置上的数据 四&#xff0c;调试技巧&…

html页面仿word文档样式(vue页面也适用)

目录 文章title&#xff1a; 标题&#xff1a; 正文&#xff1a; 完整代码&#xff1a; 页面效果&#xff1a; 文章title&#xff1a; <div><h3 style"display: flex;justify-content: center; align-items: center; color: #000;">实验室招新报名公…