3354. 使数组元素等于零

3354、[简单] 使数组元素等于零

1、题目描述

给你一个整数数组 nums

开始时,选择一个满足 nums[curr] == 0 的起始位置 curr ,并选择一个移动 方向 :向左或者向右。

此后,你需要重复下面的过程:

  • 如果 curr 超过范围 [0, n - 1] ,过程结束。
  • 如果 nums[curr] == 0 ,沿当前方向继续移动:如果向右移,则 递增 curr ;如果向左移,则 递减 curr
  • 如果 nums[curr] > 0:
    • nums[curr] 减 1 。
    • 反转 移动方向(向左变向右,反之亦然)。
    • 沿新方向移动一步。

如果在结束整个过程后,nums 中的所有元素都变为 0 ,则认为选出的初始位置和移动方向 有效

返回可能的有效选择方案数目。

2、解题思路

  1. 问题描述:

    • 从一个初始位置 curr 开始,选择方向(左或右),按题目要求依次处理元素。

    • 如果结束时 nums 所有元素为 0,则此方案有效。

    • 我们需要统计满足条件的方案数目。

  2. 核心逻辑:

    • 遍历所有满足 nums[curr] == 0 的起始位置 curr

    • 针对每个起始位置,尝试两种移动方向(左、右),模拟过程并验证是否满足条件。

    • 使用辅助数组 temp 保存当前模拟的状态,避免修改原始数组。

  3. 模拟移动:

    • 如果当前位置值是 0,继续沿当前方向移动。

    • 如果当前位置值是 >0:

      • 减少当前值 1
      • 反转方向。
      • 移动一步。
    • 如果当前位置越界(curr < 0curr >= n),结束模拟。

  4. 优化点:

    • 尽量减少不必要的模拟操作。

    • 当发现某个状态无法满足条件时立即终止。

3、代码实现

class Solution {
public:int countValidSelections(vector<int>& nums) {int n = nums.size();int result = 0;// 遍历所有可能的起始位置for (int start = 0; start < n; ++start) {if (nums[start] != 0)continue;// 两个方向:1 表示向右,-1 表示向左for (int direction : {1, -1}) {vector<int> temp = nums; // 临时数组用于模拟int curr = start;bool valid = true;while (curr >= 0 && curr < n) {if (temp[curr] == 0) {// 当前位置为 0,继续移动curr += direction;} else if (temp[curr] > 0) {// 当前位置值 > 0temp[curr]--;           // 减少当前值direction = -direction; // 反转方向curr += direction;      // 移动一步} else {// 理论上不会出现这种情况valid = false;break;}}// 如果数组所有元素都变为 0,则该方案有效if (valid && all_of(temp.begin(), temp.end(), [](int x) { return x == 0; })) {result++;}}}return result;}
};

4、复杂度分析

  • 时间复杂度
    • 遍历所有起始位置 O(n)
    • 每个起始位置模拟两种方向,最多访问每个元素一次,因此单次模拟的复杂度为 O(n)
    • 总复杂度为 O(n2)。
  • 空间复杂度
    • 额外使用了一个数组 temp,大小为 O(n)。

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

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

相关文章

大腾智能CAD:国产云原生三维设计新选择

在快速发展的工业设计领域&#xff0c;CAD软件已成为不可或缺的核心工具。它通过强大的建模、分析、优化等功能&#xff0c;不仅显著提升了设计效率与精度&#xff0c;还促进了设计思维的创新与拓展&#xff0c;为产品从概念构想到实体制造的全过程提供了强有力的技术支持。然而…

设计模式の享元模板代理模式

文章目录 前言一、享元模式二、模板方法模式三、代理模式3.1、静态代理3.2、JDK动态代理3.3、Cglib动态代理3.4、小结 前言 本篇是关于设计模式中享元模式、模板模式、以及代理模式的学习笔记。 一、享元模式 享元模式是一种结构型设计模式&#xff0c;目的是为了相似对象的复用…

Linux网络功能 - 服务和客户端程序CS架构和简单web服务示例

By: fulinux E-mail: fulinux@sina.com Blog: https://blog.csdn.net/fulinus 喜欢的盆友欢迎点赞和订阅! 你的喜欢就是我写作的动力! 目录 概述准备工作扫描服务端有那些开放端口创建客户端-服务器设置启动服务器和客户端进程双向发送数据保持服务器进程处于活动状态设置最小…

用人话讲计算机:Python篇!(十五)迭代器、生成器、装饰器

一、迭代器 &#xff08;1&#xff09;定义 标准解释&#xff1a;迭代器是 Python 中实现了迭代协议的对象&#xff0c;即提供__iter__()和 __next__()方法&#xff0c;任何实现了这两个方法的对象都可以被称为迭代器。 所谓__iter__()&#xff0c;即返回迭代器自身 所谓__…

小程序快速实现大模型聊天机器人

需求分析&#xff1a; 基于大模型&#xff0c;打造一个聊天机器人&#xff1b;使用开放API快速搭建&#xff0c;例如&#xff1a;讯飞星火&#xff1b;先实现UI展示&#xff0c;在接入API。 最终实现效果如下&#xff1a; 一.聊天机器人UI部分 1. 创建微信小程序&#xff0c…

【Android】unzip aar删除冲突classes再zip

# 解压JAR文件 jar xf your-library.jar # 解压AAR文件&#xff08;AAR实际上是ZIP格式&#xff09; unzip your-library.aar # 删除不需要的类 rm -rf path/to/com/example/unwanted/ # 对于JAR打包 jar cf your-library-modified.jar -C path/to/unzipped/ . # 对于AAR打包…

使用C语言编写UDP循环接收并打印消息的程序

使用C语言编写UDP循环接收并打印消息的程序 前提条件程序概述伪代码C语言实现编译和运行C改进之自由设定端口注意事项在本文中,我们将展示如何使用C语言编写一个简单的UDP服务器程序,该程序将循环接收来自指定端口的UDP消息,并将接收到的消息打印到控制台。我们将使用POSIX套…

你的第一个博客-第一弹

使用 Flask 开发博客 Flask 是一个轻量级的 Web 框架&#xff0c;适合小型应用和学习项目。我们将通过 Flask 开发一个简单的博客系统&#xff0c;支持用户注册、登录、发布文章等功能。 步骤&#xff1a; 安装 Flask 和其他必要库&#xff1a; 在开发博客之前&#xff0c;首…

Vue(二)

1.Vue生命周期 Vue生命周期就是一个Vue实例从 创建 到 销毁 的整个过程。生命周期四个阶段&#xff1a; 创建阶段&#xff1a;创建响应式数据。 挂载阶段&#xff1a;渲染模板。 更新阶段&#xff1a;修改数据&#xff0c;更新视图。 销毁阶段&#xff1a;销毁Vue实例。 …

macOS 配置 vscode 命令行启动

打开 vscode 使用 cmd shift p 组合快捷键&#xff0c;输入 install 点击 Install ‘code’ command in PATH Ref https://code.visualstudio.com/docs/setup/mac

python coding(二) Pandas 、PIL、cv2

Pandas 一个分析结构化数据的工具集。Pandas 以 NumPy 为基础&#xff08;实现数据存储和运算&#xff09;&#xff0c;提供了专门用于数据分析的类型、方法和函数&#xff0c;对数据分析和数据挖掘提供了很好的支持&#xff1b;同时 pandas 还可以跟数据可视化工具 matplotli…

期权VIX指数构建与择时应用

芝加哥期权交易 所CBOE的波动率指数VIX 是反映 S&P 500 指数未来 30 天预测期波动率的指标&#xff0c;由于预期波动率多用于表征市场情绪&#xff0c;因此 VIX 也被称为“ 恐慌指数”。 VIX指数计算 VIX 反映了市场情绪和投资者的风险偏好&#xff0c; 对于欧美市场而言…

一区牛顿-拉夫逊算法+分解+深度学习!VMD-NRBO-Transformer-GRU多变量时间序列光伏功率预测

一区牛顿-拉夫逊算法分解深度学习&#xff01;VMD-NRBO-Transformer-GRU多变量时间序列光伏功率预测 目录 一区牛顿-拉夫逊算法分解深度学习&#xff01;VMD-NRBO-Transformer-GRU多变量时间序列光伏功率预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.中科院一区…

Elasticsearch:什么是提示工程 - prompt engineering?

提示工程流程定义 提示工程是一种工程技术&#xff0c;用于设计生成式 AI 工具&#xff08;generative AI tools&#xff09;的输入&#xff0c;以调整大型语言模型并优化输出。 提示&#xff08;prompts&#xff09;被称为输入&#xff0c;而由生成性 AI 工具生成的答案是输…

html <a>设置发送邮件链接、打电话链接 <a href=“mailto:></a> <a href=“tel:></a>

1.代码 <ul><li>电话&#xff1a;<a href"tel:18888888888">188-8888-8888</a></li><li>邮箱&#xff1a;<a href"mailto:10000qq.com">10000qq.com</a></li><li>邮箱&#xff1a;<a hre…

前端关于pptxgen.js个人使用介绍

官方文档链接:Quick Start Guide | PptxGenJS git地址&#xff1a;https://github.com/gitbrent/PptxGenJS/ 1. 安装命令 npm install pptxgenjs --save yarn add pptxgenjs 2. 示例demo import pptxgen from "pptxgenjs"; // 引入pptxgen // 1. Create a Presenta…

【机器人】机械臂位置、轨迹和转矩控制概要

仍旧以 RRR&#xff08;三连杆&#xff09;为例&#xff0c;实现控制&#xff0c;可以采用以下步骤。这里的控制包括 位置控制轨迹控制 轨迹跟踪控制&#xff0c; 具体根据应用需求选择。以下是实现 RRR 机械臂控制的完整过程&#xff1a; 1. 定义机器人模型 通过 Denavit-H…

Python tkinter写的《电脑装配单》和 Html版 可打印 可导出 excel 文件

Python版 样图&#xff1a; 说明书&#xff1a; markdown # 电脑配置单使用说明书 ## 一、软件简介 电脑配置单是一个用于创建和比较两套电脑配置方案的工具软件。用户可以选择各种电脑配件,输入数量和价格,软件会自动计算总金额,并支持导出和打印配置单。 ## 二、主要功能 1. …

android studio更改应用图片,和应用名字。

更改应用图标&#xff0c;和名字 先打开AndroidManifest.xml文件。 更改图片文件名字&#xff08; 右键-->构建-->重命名&#xff08;R&#xff09;&#xff09;

Vue Web开发(十)

1. 用户管理新增&#xff0c;搜索&#xff0c;编辑&#xff0c;删除 本节课完成用户列表表单设计&#xff0c;使用table组件&#xff0c;同样模块化组件&#xff0c;CommonTable.vue组件&#xff0c;并且在User页面中引入&#xff0c;mock实现数据模拟&#xff0c;最终完成用户…