当前位置: 首页 > article >正文

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)。

http://www.kler.cn/a/447475.html

相关文章:

  • flink实现复杂kafka数据读取
  • Word图片嵌入格式不正确的解决办法
  • Windows安全中心(病毒和威胁防护)的注册
  • 深入了解Bootstrap:打造响应式网站的利器
  • C++ 引用的基本用法
  • ios 混合开发应用白屏问题
  • 基于Transformer的自编码器模型在故障检测中的应用
  • springmvc的拦截器,全局异常处理和文件上传
  • 蓝桥杯 2024 国 B【选数概率】(AC)
  • 【java面向对象编程】第六弹----封装、继承、多态
  • Androidstudio点击按钮播放声音
  • 如何优雅的关闭GoWeb服务器
  • RK3588 , mpp硬编码yuv, 保存MP4视频文件.
  • TDesign:NavBar 导航栏
  • 未来趋势系列 篇五:自主可控科技题材解析和股票梳理
  • SpringCloud微服务开发(六)ElasticSearch/RESTful风格
  • 如何在Qt中应用html美化控件
  • 进入 Cosmic Red:第十周游戏指南
  • Linux中的mv命令深入分析
  • RAG开发中,如何用Milvus 2.5 BM25算法实现混合搜索
  • 如何深入学习JVM底层原理?
  • 火山引擎声音复刻API-2.0
  • 【从零开始入门unity游戏开发之——C#篇18】C#面向对象的封装——构造函数、`this()`构造函数链、析构函数(方法)
  • 如果模块请求http改为了https,测试方案应该如何制定,修改
  • 云手机:小红书矩阵搭建方案
  • 电商新品发布自动化:RPA 确保信息一致性与及时性【rap.top】