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) {
                        // 当前位置值 > 0
                        temp[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)。

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

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

相关文章

猪猪软件库

猪猪软件库&#xff0c;汇聚各类宝藏软件&#xff0c;宛如一座数字百宝箱。这里涵盖了实用工具、趣味游戏、高效办公软件等丰富资源&#xff0c;满足不同用户的多样需求。界面简洁直观&#xff0c;搜索便捷流畅&#xff0c;能让你迅速定位心仪软件。 所有资源都经过严格筛选&a…

端到端自动驾驶大模型:视觉-语言-动作模型 VLA

模型框架定义、模型快速迭代能力是考查智驾团队出活能力的两个核心指标。在展开讨论Vision-Language-Action Models(VLA)之前&#xff0c;咱们先来讨论端到端自动驾驶大模型设计。 目录 1. 端到端自动驾驶大模型设计 1.1 模型输入设计 1.2 模型输出设计 1.3 实现难点分析 …

Swin transformer 论文阅读记录 代码分析

该篇文章&#xff0c;是我解析 Swin transformer 论文原理&#xff08;结合pytorch版本代码&#xff09;所记&#xff0c;图片来源于源paper或其他相应博客。 代码也非原始代码&#xff0c;而是从代码里摘出来的片段&#xff0c;配上简单数据&#xff0c;以便理解。 当然&…

LLMs之rStar:《Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers》翻译与解读

LLMs之rStar&#xff1a;《Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers》翻译与解读 导读&#xff1a;这篇论文提出了一种名为rStar的自我博弈互推理方法&#xff0c;用于增强小型语言模型 (SLMs) 的推理能力&#xff0c;无需微调或依赖更强大的模型。rStar…

CS 144 check5: down the stack (the network interface)

Lectures Note 略 Exercises TCP片段传输到对等方的过程&#xff1a; TCP-in-UDP-in-IP. Linux 提供了一种接口&#xff08;即“数据报套接字”&#xff0c;UDPSocket&#xff09;&#xff0c;它允许应用程序仅提供用户数据报的有效载荷和目标地址&#xff0c;而内核则负责…

Llama 3 模型系列解析(一)

目录 1. 引言 1.1 Llama 3 的简介 1.2 性能评估 1.3 开源计划 1.4 多模态扩展 ps 1. 缩放法则 2. 超额训练&#xff08;Over-training&#xff09; 3. 计算训练预算 4. 如何逐步估算和确定最优模型&#xff1f; 2. 概述 2.1 Llama 3 语言模型开发两个主要阶段 2.2…

越疆科技营收增速放缓:毛利率未恢复,持续亏损下销售费用偏高

《港湾商业观察》施子夫 12月13日&#xff0c;深圳市越疆科技股份有限公司&#xff08;以下简称&#xff0c;越疆科技&#xff0c;02432.HK&#xff09;发布全球发售公告&#xff0c;公司计划全球发售4000万股股份&#xff0c;其中3800万股国际发售&#xff0c;200万股香港公开…

微信小程序实现画板画布自由绘制、选择画笔粗细及颜色、记录撤回、画板板擦、清空、写字板、导出绘图、canvas,开箱即用

目录 画板创建canvas绘制及渲染画笔粗细功能实现画笔颜色选择画笔痕迹撤回、板擦、画布清空canvas解析微信小程序中 canvas 的应用场景canvas 与 2D 上下文、webgl 上下文的关系图像的加载与绘制说明代码说明画板创建 canvas绘制及渲染 在wxml添加对应的canvas标签代码,并在j…

混合精度训练说明

什么是混合精度训练&#xff1f;混合精度训练有什么用&#xff1f; 这里总结一下。 本文总结自kapathy的build gpt2 通常在训练过程中&#xff0c;model里面的数据默认都是torch.float32类型&#xff0c; 也就是用32bit的float型数据表示变量。 比如特征提取中提取的特征&…

draw.io 导出svg图片插入word后模糊(不清晰 )的解决办法

通常我们将图片从draw.io导出为svg格式后插入word, 会发现字体不清晰&#xff0c;特别是使用宋体时&#xff0c;折腾了半天&#xff0c;得到如下办法&#xff1a; 方法1: 在draw.io中导出pdf文件&#xff0c;使用 PDF转SVG转换器 - SVGConverter 将其转换为svg, 完美呈现。 …

ARM学习(38)多进程多线程之间的通信方式

ARM学习(38)ARM学习(38)多进程多线程之间的通信方式 一、问题背景 笔者在调试模拟器的时候,碰到进程间通信的问题,一个进程在等另外一个进程ready的时候,迟迟等不到,然后通过调试发现,另外一个进程变量已经变化了,但是当前进程变量没变化,需要了解进程间通信的方式…

【动手学运动规划】 5.2 数值优化基础:梯度下降法,牛顿法

朕四季常服, 不过八套. — 大明王朝1566 道长 &#x1f3f0;代码及环境配置&#xff1a;请参考 环境配置和代码运行! 上一节我们介绍了数值优化的基本概念, 让大家对最优化问题有了基本的理解. 那么对于一个具体的问题, 我们应该如何求解呢? 这一节我们将介绍几个基本的求解…

24-12-22 pytorch学习 基础知识 帝乡明日到,犹自梦渔樵。

文章目录 pytorch学习 基础知识pytorch学习(1) Tensors1.1 初始化Tensor1.2 Tensor 的属性1.3 Tensors 的操作1.4 与 NumPy 的桥梁1.4.1 Tensor 到 NumPy 数组1.4.2 NumPy 数组 到 Tensor pytorch学习(2) 数据集和数据加载器2.1 加载一个数据集2.2 迭代和可视化数据集2.3 为你的…

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

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

M3D: 基于多模态大模型的新型3D医学影像分析框架,将3D医学图像分析从“看图片“提升到“理解空间“的层次,支持检索、报告生成、问答、定位和分割等8类任务

M3D: 基于多模态大模型的新型3D医学影像分析框架&#xff0c;将3D医学图像分析从“看图片“提升到“理解空间“的层次&#xff0c;支持检索、报告生成、问答、定位和分割等8类任务 论文大纲理解1. 确认目标2. 分析过程&#xff08;目标-手段分析&#xff09;核心问题拆解 3. 实…

【102. 二叉树的层序遍历 中等】

题目&#xff1a; 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]] 示例…

第四届电气工程与控制科学

重要信息 官网&#xff1a;www.ic2ecs.com 时间&#xff1a;2024年12月27-29日 简介 第四届电气工程与控制科学定于2024年12月27-29日在中国南京召开。主要围绕“电气工程“、”控制科学“、”机械工程“、”自动化”等主题展开&#xff0c;旨在为从电…

监控易在汽车制造行业信息化运维中的应用案例

引言 随着汽车制造行业的数字化转型不断深入&#xff0c;信息化类IT软硬件设备的运行状态监控、故障告警、报表报告以及网络运行状态监控等成为了企业运维管理的关键环节。监控易作为一款全面、高效的信息化运维管理工具&#xff0c;在汽车制造行业中发挥着重要作用。本文将结合…

大模型+安全实践之春天何时到来?

引子:距《在大模型实践旅途中摸了下上帝的脚指头》一文发布近一年,2024年笔者继续全情投入在大模型+安全上,深度参与了一些应用实践,包括安全大模型首次大规模应用在国家级攻防演习、部分项目的POC直到项目落地,也推动了一些场景安全大模型应用从0到3的孵化上市。这一年也…

大小端存储的问题

请你用C语言写一个简单的程序&#xff0c;判断你使用的主机是大端存储还是小端存储 #include <stdio.h> int main(){int x 0x11223344;char *p (char *)&x;if(0x44 *p){printf("小端\n");}else if(0x11 *p){printf("大端\n");}return 0; }