Leetcode 3354 Make Array Elements Equal to Zero

题意:给定一个数组arr,有个cur使得nums[curr] == 0,一开始可以选择向左向右移动, 如果nums[cur] > 0, 那就 nums[cur] -= 1,并且移动的方向变更,求多少个cur的位置以及向左向右的方式能够使nums中的所有数字变化成0(想象一个球里面撞来撞去)

https://leetcode.com/problems/make-array-elements-equal-to-zero/description/

题解:本质上是找到一个每一个nums[cur] == 0的点,这个位置的左边所有数的和以及右边所有数的和相等或者相差1,如果是相等的话答案+2,如果相差1的话答案+1
由此想到前缀和

preS[i] == preS[n] - preS[i] 答案+2
preS[i] + 1 == preS[n] - preS[i] || preS[i] == preS[n] - preS[i] + 1 答案+1

class Solution {
public:int countValidSelections(vector<int>& nums) {int n = nums.size();int res = 0;vector<int> preS(n+1, 0);for(int i = 1; i < n+1; i++) {preS[i] = preS[i-1] + nums[i-1];}for(int i = 0; i < n; i++) {if(nums[i] == 0) {if(preS[i] == preS[n] - preS[i]) {res += 2;} else if(preS[i] + 1 == preS[n] - preS[i] || preS[i] == preS[n] - preS[i] + 1) {res += 1;}}}return res;}
};

时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

利用c语言详细介绍下冒泡排序

软件开发过程中&#xff0c;排序算法是常规且使用众多的方法之一&#xff0c;而冒泡算法又是排序算法中最常规且基本的算法。今天我们利用c语言&#xff0c;图文详细介绍下冒泡算法。 一、图文介绍 我们输入一个数组&#xff0c;数组为【10&#xff0c;5&#xff0c;3&#xf…

小程序-基于java+SpringBoot+Vue的实习生管理系统设计与实现

项目运行 1.运行环境&#xff1a;最好是java jdk 1.8&#xff0c;我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境&#xff1a;IDEA&#xff0c;Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境&#xff1a;Tomcat 7.x,8.x,9.x版本均可 4.硬件环境&#xff1a…

全新升级抗性宏基因组,直击病毒和毒力因子分析!

基于宏基因组测序的抗性基因分析是目前抗性基因分析的重要手段。为了协助研究工作者对抗性基因开展更深入且全面的探研&#xff0c;凌恩生物技术团队致力于技术研发&#xff0c;推出了全新升级版的宏基因组抗性基因分析流程。此流程采用五大数据库进行详尽的注释分析&#xff0…

算法--“汽车加油”问题.

def greedy():n 100 # 汽车满油后可行驶的最大距离d [50, 80, 39, 60, 40, 32] # 加油站的距离k len(d) # 加油站的数量# 检查是否有加油站距离超过汽车的最大行驶距离for dist in d:if dist > n:print(no solution)returnnum 0 # 加油次数current_position 0 # 当…

细说STM32单片机DMA中断收发RTC实时时间并改善其鲁棒性的方法

目录 一、DMA基础知识 1、DMA简介 (1)DMA控制器 (2)DMA流 (3)DMA请求 (4)仲裁器 (5)DMA传输属性 2、源地址和目标地址 3、DMA传输模式 4、传输数据量的大小 5、数据宽度 6、地址指针递增 7、DMA工作模式 8、DMA流的优先级别 9、FIFO或直接模式 10、单次传输或突…

HTTP 缓存策略

文章目录 一、HTTP的缓存的过程是怎样的&#xff1f;二、什么时候触发强缓存或协商缓存强缓存ExpiresCache-Control 协商缓存 三、服务器如何判断资源是否新鲜Last-Modified/If-Modified-SinceETag/If-None-Match 四、整体缓存过程 一、HTTP的缓存的过程是怎样的&#xff1f; …

Leetcode234.回文链表(HOT100)

链接 代码&#xff1a; class Solution { public:bool isPalindrome(ListNode* head) {ListNode* slow head;ListNode* fast head;// while(slow&&fast){// slow slow->next;// fast fast->next;// if(fast)// {// fast fast->…

【Unity Dots之Ecs原理分析(无入门代码示例)】

Unity Ecs原理分析 前言一、ECS是什么&#xff1f;Entity是什么&#xff1f;Component是什么&#xff1f;System是什么&#xff1f;不得不提的Archetype为什么时16kb&#xff1f; 什么是Structural Change&#xff1f;ASpect有关ECS使用时的安全性Conversion World & Shado…

【pyspark学习从入门到精通14】MLlib_1

目录 包的概览 加载和转换数据 在前文中&#xff0c;我们学习了如何为建模准备数据。在本文中&#xff0c;我们将实际使用这些知识&#xff0c;使用 PySpark 的 MLlib 包构建一个分类模型。 MLlib 代表机器学习库。尽管 MLlib 现在处于维护模式&#xff0c;即它不再积极开发…

【大模型推理】all-reduce

https://andrew.gibiansky.com/blog/machine-learning/baidu-allreduce/#ref-4 1. ALL reduce , reduce, broadcast 概念 Introduction 在过去的几年中&#xff0c;神经网络已经被证明是解决各种问题的令人难以置信的有效工具&#xff0c;并且在规模和计算需求上都迅速增长。…

opencv(c++)---自带的卷积运算filter2D以及应用

opencv(c)—自带的卷积运算filter2D以及应用 #include <opencv2/opencv.hpp> #include<iostream>using namespace cv; using namespace std;int main() {Mat imgin, imgout;imgin imread("D:/1234.png");if (imgin.empty()){cout << "Could …

C++20中的Concepts与TypeScript

C20中的Concepts与TypeScript 大家好&#xff01;上一篇聊了C20中概念&#xff08;Concepts&#xff09;&#xff0c;这是一个非常赞的特性&#xff0c;极大简化了模板编程&#xff0c;但是如果跳出C去查看一下其他编程语言的特性&#xff0c;就会发现&#xff0c;这样类似的特…

联想thinkpad笔记本哪些配置可以安装win7_联想thinkpad笔记本装win7解析(支持新旧机型)

联想thinkpad笔记本哪些配置可以安装win7&#xff1f;联想ThinkPad L14在安装win7后usb键盘不能使用&#xff0c;并且bios中要关闭安全启动和开启CSM兼容模式&#xff0c;那么联想ThinkPad L14要怎么安装win7系统呢&#xff1f;下面小编就给大家介绍详细的联想ThinkPad L14装wi…

IDEA如何设置编码格式,字符编码,全局编码和项目编码格式

前言 大家好&#xff0c;我是小徐啊。我们在开发Java项目&#xff08;Springboot&#xff09;的时候&#xff0c;一般都是会设置好对应的编码格式的。如果设置的不恰当&#xff0c;容易造成乱码的问题&#xff0c;这是要避免的。今天&#xff0c;小徐就来介绍下我们如何在IDEA…

实习冲刺第二十五天

283.移动零 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例 输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0] 思路详解&#xff1a…

使用QTimer和SIGNAL/SLOT机制来实现系统时间的显示

在Qt中&#xff0c;使用QTimer和SIGNAL/SLOT机制来实现系统时间的显示是一个常见的做法。下面是如何实现这一功能的步骤&#xff1a; 创建定时器&#xff1a; 首先&#xff0c;你需要创建一个QTimer对象。QTimer是一个定时器类&#xff0c;可以在指定的时间间隔后发出信号。 QT…

Win11安装软件被系统阻止安装?解除限制的方法

Windows 11作为最新的操作系统&#xff0c;加入了许多安全性和稳定性的新特性。但也因此&#xff0c;一些用户在安装软件时可能遇到“安装被阻止”或“无法从此位置安装应用程序”的提示。这通常是由于系统的默认安全设置或权限限制导致的。本文将探讨这些限制的原因&#xff0…

三角波生成函数

% 设置时间范围和采样频率 t 0:0.01:2; % 时间从0到2秒&#xff0c;步长为0.01秒% 定义频率 f 和角频率 theta f 5; % 频率为5Hz theta 2 * pi * f * t;% 初始化输出向量 y zeros(size(t));% 根据给定的公式计算 y for k 1:fy y (-1)^(k-1)*(2 /(k * pi)) * sin(k * the…

sglang 部署Qwen2VL7B,大模型部署,速度测试,深度学习

sglang 项目github仓库&#xff1a; https://github.com/sgl-project/sglang 项目说明书&#xff1a; https://sgl-project.github.io/start/install.html 资讯&#xff1a; https://github.com/sgl-project/sgl-learning-materials?tabreadme-ov-file#the-first-sglang…

『大模型笔记』AI自动化编程工具汇总!

『大模型笔记』AI自动化编程工具汇总! 文章目录 一. Bolt.new(开源AI驱动全栈Web开发工具)1.1. Bolt.new介绍1.2. 编程小白如何打造自己的导航网站二. Cursor(人工智能代码编辑器)2.1. Cursor入门教程2.2. Cursor左侧布局设置和VSCode一样一. Bolt.new(开源AI驱动全栈Web开发工…