算法练习:1658. 将 x 减到 0 的最小操作数

题目链接:1658. 将 x 减到 0 的最小操作数

这道题目的意思就是,给定一个整数数组,和一个x,只能从数组最左边或者最右边进行删除,使得x恰好等于0,并且要操作次数最少的情况,否则返回-1.

这道题直接进行删左右元素的话,有很多种情况,一下删左边一下删右边,同时还要保证,要最小操作次数。这样就有很多种情况,直接做非常复杂。

所以当正面做非常复杂的时候就考虑正难则反。

上图满足式子:sum = target +a+b,a+b = x。target = sum-x。

sum表示整个数组大小。target表示中间子数组大小。

既然我们要删除两边的数来保证x减去这些数为0,我们可以找中间的子数组数,使整个子数组和满足,整个数组和减去x的大小。然后再用整个数组长度减去子数组长度,就可以得到操作次数。但是要保证子数组长度最大,长度最大就可以保证操作次数最少。

这样就把找两边数转换成找中间子数组。找到中间最长子数组就相当于找到两边数。

就利用找最大字串方法,利用滑动窗口。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size(),sum = 0;
        int m = n-1;
        while(m>=0) sum += nums[m--];
        int target = sum - x;
        int sum1 = 0;
        int cut = -1;
        if(target < 0) return -1;
            for(int right = 0,left = 0;right<n;)
            {
                sum1 += nums[right];//进窗口
                while(sum1 > target && left<n)//判断出窗口
                {
                    left++;
                    sum1 -=nums[left-1];
                }
                
                if(sum1 == target)//更新
                {
                    cut = max(cut,right-left+1);
                }
                right++;
            }
        if(cut == -1) return -1;
        return n-cut;
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

职场如雷场,稍有不慎就会被炸翻?十大生存法则送给你

大多数人的一生都要经历过&#xff1a;求学&#xff0c;入职&#xff0c;退休三个阶段。其中职场生涯一般都在30至40年左右&#xff0c;占据了人生的大部分时间&#xff0c;而这段时间&#xff0c;是每个人最年富力强&#xff0c;精力充沛的时光。 那么&#xff0c;如何把这人…

这款神器,运维绝杀 !!!

项目简介 CrowdSec 是一款开源的、基于社区协作的网络安全防护工具&#xff0c;它通过分析和共享IP信誉数据来对抗恶意行为。该软件不仅支持IPv6&#xff0c;而且相较于传统的Python实现&#xff0c;其采用Go语言编写&#xff0c;运行速度提升了60倍。CrowdSec 利用Grok模式解析…

[C++] cpphttplib使用https而不是http

前言 首先我们假设是直接使用 httplib.h 的源文件。 支持 https 根据readme来看&#xff0c;需要开启一个宏&#xff0c;链接libssl和libcrypto就可以了。 下载openssl 保姆级OpenSSL下载及安装教程 选择非light的版本&#xff0c;这样才会有头文件和lib库引入文件。 编写C…

gitee 使用 webhoot 触发 Jenkins 自动构建

一、插件下载和配置 Manage Jenkins>Plugin Manager 搜索 gitee 进行安装 插件配置 1、前往Jenkins -> Manage Jenkins -> System -> Gitee Configuration -> Gitee connections 2、在 Connection name 中输入 Gitee 或者你想要的名字 3、Gitee host URL 中…

MDC(重要)

1.简介 MDC 介绍​ MDC&#xff08;Mapped Diagnostic Context&#xff0c;映射调试上下文&#xff09;是 log4j 和 logback 提供的一种方便在多线程条件下记录日志的功能。MDC 可以看成是一个与当前线程绑定的Map&#xff0c;可以往其中添加键值对。MDC 中包含的内容可以被同一…

Linux—进程学习-01

目录 Linux—进程学习—11.冯诺依曼体系结构2.操作系统2.1操作系统的概念2.2操作系统的目的2.3如何理解管理2.4计算机软硬件体系的理解2.5系统调用和库函数的概念 3.进程3.1进程是什么3.2管理进程3.2.1描述进程-PCB3.2.2组织进程3.2.3总结 3.3查看进程 4.与进程有关的系统调用 …

初始JavaEE篇——多线程(5):生产者-消费者模型、阻塞队列

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a;JavaEE 文章目录 阻塞队列生产者—消费者模型生产者—消费者模型的优势&#xff1a;生产者—消费者模型的劣势&#xff1a; Java标准库中的阻…

Redis常见面试题(二)

Redis性能优化 Redis性能测试 阿里Redis性能优化 使用批量操作减少网络传输 Redis命令执行步骤&#xff1a;1、发送命令&#xff1b;2、命令排队&#xff1b;3、命令执行&#xff1b;4、返回结果。其中 1 与 4 消耗时间 --> Round Trip Time&#xff08;RTT&#xff0c;…

Scala学习记录,List

List是一个不可变&#xff08;immutable&#xff09;的序列。特点&#xff1a;数据是有序的 前面学习的Set&#xff0c;Map数据是无序的&#xff1b;Array是有序的&#xff0c;Array数组物理空间上是连续的 List可变不可变&#xff1a; list中不可变的列表是不能修改的 list…

【从零开始的LeetCode-算法】1456. 定长子串中元音的最大数目

给你字符串 s 和整数 k 。 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为&#xff08;a, e, i, o, u&#xff09;。 示例 1&#xff1a; 输入&#xff1a;s "abciiidef", k 3 输出&#xff1a;3 解释&#xff1a…

0-基于图的组合优化算法学习(NeurIPS 2017)(未完)

文章目录 Abstract1 Introduction2 图上的贪婪算法的通用表述3 表示:图嵌入3.1 Structure2Vec3.2 参数化 Q ^ ( h ( S ) , v ; Θ ) \widehat{Q}(h(S), v; \Theta) Q ​(h(S),v;Θ)4 Training: Q-learningAbstract 为NP-hard组合优化问题设计好的启发式或近似算法通常需要大…

RK3568平台开发系列讲解(设备树篇)设备树(device Tree)的由来

🚀返回专栏总目录 文章目录 一、设备树的由来二、设备树的组成沉淀、分享、成长,让自己和他人都能有所收获!😄 一、设备树的由来 首先不得不提到Linus的一封重要的邮件:(硬件解耦)(可以复用的代码) Gaah. Guys, this whole ARM thing is a f*cking pain in the ass.…

基于C++深度优先遍历迷宫

c实现的深度优先遍历迷宫&#xff0c;迷宫大小为20*20&#xff0c;代码简练清楚&#xff0c;内涵关键注释。代码与网上都不一样。 深度优先遍历迷宫&#xff0c;核心思想是借助一个栈&#xff0c;站在一个节点上时&#xff0c;将它附近可以走的节点存在栈中&#xff0c;再按顺…

QML项目实战:自定义CheckBox

目录 一.添加模块 import QtQuick.Controls 1.2 import QtQuick.Controls.Styles 1.4 import QtGraphicalEffects 1.15 二.自定义CheckBox 1.CheckBox设置 2.勾选框设置 3.标签部分 4. 状态变化处理 5.文本设置 三.效果 1.当enabled为true 2.当enabled为true 3.当…

天命人开店日记之门店经营调研(下)

在调研前拟定了一些想要去了解的信息&#xff0c;包括&#xff1a;月销量、净利润、用户购买的主要担忧、与电商平台的竞争差异等关键内容&#xff0c;然而当自己去实地考察线下门店时&#xff0c;确发现实际情况与自己的预期相差非常大。大大出乎预料的包括三方面&#xff1a;…

【昇腾】Linux系统常见命令

文章目录 查看操作系统信息查看EulerOS内核版本 查看root下的内容查看/etc目录下的内容sh: yum: command not foundValueError: zero-size array to reduction operation minimum which has no identityAttributeError: torch_npu._C._NPUDeviceProperties object has no attri…

立体视觉的核心技术:视差计算与图像校正详解

立体视觉的核心技术&#xff1a;视差计算与图像校正详解 在立体视觉中&#xff0c;通过双目相机&#xff08;即左右两台相机&#xff09;的不同视角捕获的图像&#xff0c;结合几何关系&#xff0c;我们可以推算出场景中物体的深度。本文将深入讲解如何基于视差&#xff08;di…

11.6-11.7重大专业能力测试(换皮c++考试)全攻略(两天速通版)

relations的vector存储的就是Relation类型的数据&#xff0c;并不是指针&#xff0c;所以relations[i]访问Relation的成员就是直接用.&#xff0c; 但是joins的JoinSql里面存的是指针&#xff0c;并不是实际的数据&#xff0c;所以应当用->来访问其中的成员 结构体当中的Sq…

Go语言结构体、方法与接口

文章目录 一、结构体构造函数Go语言中的构造函数语法 二、结构体方法和接收器无参数和返回值值类型接收者指针类型接收者方法继承方法重写 三、结构体比较结构体比较要求结构体比较符号 四、接口声明接口定义接口特点接口格式标准格式接口的实现&#xff1a;空接口error接口 五…

用Puppeteer点击与数据爬取:实现动态网页交互

用Puppeteer与代理IP抓取51job招聘信息&#xff1a;动态网页交互与数据分析 引言 在数据采集领域&#xff0c;传统的静态网页爬虫方式难以应对动态加载的网页内容。动态网页通常依赖JavaScript加载数据&#xff0c;用户需要与页面交互才能触发内容显示。因此&#xff0c;我们…