Leetcode3192. 使二进制数组全部等于 1 的最少操作次数 II

Every day a Leetcode

题目来源:3192. 使二进制数组全部等于 1 的最少操作次数 II

解法1:遍历

由于 nums[i] 会被其左侧元素的操作影响,所以我们先从最左边的 nums[0] 开始思考。

分类讨论:

  • 如果 nums[0]=1,无需反转,问题变成剩下 n−1 个数如何操作。接下来考虑 nums[1]。
  • 如果 nums[0]=0,反转次数加一,问题变成剩下 n−1 个数(在修改次数是奇数的情况下)如何操作。接下来考虑 nums[1]。

对后续元素来说,由于反转偶数次等于没反转,所以只需考虑反转次数的奇偶性。

一般地,设反转次数的奇偶性为 k,分类讨论:

  • 如果 nums[i]≠k,无需反转,接下来考虑 nums[i+1]。
  • 如果 nums[i]=k,反转次数加一,接下来考虑 nums[i+1]。

代码:

/*
 * @lc app=leetcode.cn id=3192 lang=cpp
 *
 * [3192] 使二进制数组全部等于 1 的最少操作次数 II
 */

// @lc code=start
class Solution
{
public:
    int minOperations(vector<int> &nums)
    {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == 1 && ans % 2 == 1)
                ans++;
            if (nums[i] == 0 && ans % 2 == 0)
                ans++;
        }
        return ans;
    }
};
// @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(n),其中 n 是数组 nums 的长度。

空间复杂度:O(1)。

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

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

相关文章

Rust: duckdb和polars读csv文件比较

duckdb在数据分析上&#xff0c;有非常多不错的特质。1、快&#xff1b;2、客户体验好&#xff0c;特别是可以同时批量读csv&#xff08;在一个目录下的csv等文件&#xff09;。polars的性能比pandas有非常多的超越。但背后的一些基于arrow的技术栈有很多相同之类。今天想比较一…

YOLOv5改进 | 注意力机制 | 迈向高质量像素级回归的极化自注意力【全网独家】

秋招面试专栏推荐 &#xff1a;深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 &#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 专栏目录&#xff1a; 《YOLOv5入门 …

[数据集][目标检测]人员状态跑睡抽烟打电话跌倒检测数据集4943张5类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;4943 标注数量(xml文件个数)&#xff1a;4943 标注数量(txt文件个数)&#xff1a;4943 标注…

黑马点评DAY1|Redis入门、Redis安装

什么是Redis&#xff1f; redis是一种键值型数据库&#xff0c;内部所存的数据都是键值对的形式&#xff0c;例如&#xff0c;我们可以把一个用户数据存储为如下格式&#xff1a; 键值id$1600name张三age21 但是这样的存储方式&#xff0c;数据会显得非常松散&#xff0c;因…

qiankun微前端:qiankun+vite+vue3+ts(未完待续..)

目录 什么是微前端 目前现有的微前端 好处 使用 子应用的页面在主应用里显示 什么是微前端 微前端是一种多个团队通过独立发布功能的方式来共同构建现代化 web 应用的技术手段及方法策略。 我的理解就是将一个大型的前端应用拆分成多个模块&#xff0c;每个微前端模块可以由…

大淘客api实现多多进宝的商品查询PHP版

大家好&#xff0c;我是网创有方&#xff0c;今天教大家如何使用大淘客的api实现拼多多商品详情信息查询。这里用到的多多进宝&#xff0c;如果没有多多进宝的&#xff0c;先去多多进宝注册个账号吧&#xff01; 第一步&#xff1a;进入大淘客官方创建应用&#xff0c;并且下载…

AI降重新突破:chatgpt降重工具在学术论文中的应用与效果

论文降重一直是困扰各界毕业生的“拦路虎”&#xff0c;还不容易熬过修改的苦&#xff0c;又要迎来降重的痛。 其实想要给论文降重达标&#xff0c;我有一些独家秘诀。话不多说直接上干货&#xff01; 1、同义词改写&#xff08;针对整段整句重复&#xff09; 这是最靠谱也是…

.NET C# 使用OpenCV实现人脸识别

.NET C# 使用OpenCV实现模型训练、人脸识别 码图~~~ 1 引入依赖 OpenCvSHarp4 - 4.10.0.20240616 OpenCvSHarp4.runtime.win - 4.10.0.20240616 2 人脸数据存储结构 runtime directory | face | {id}_{name} | *.jpg id - 不可重复 name - 人名 *.jpg - 人脸照片3 Demo 3.…

stable-diffusion-webui-colab搭建SadTalker由图生成视频人

在这里选择一个stable-diffusion-webui-colab ​​​​​​​​​GitHub - camenduru/stable-diffusion-webui-colab: stable diffusion webui colab 这里我选择是&#xff1a; https://colab.research.google.com/github/camenduru/stable-diffusion-webui-colab/blob/main…

Webpack: 深入理解图像加载原理与最佳实践

概述 图形图像资源是当代 Web 应用的最常用、实惠的内容、装饰元素之一&#xff0c;但在 Webpack 出现之前对图像资源的处理复杂度特别高&#xff0c;需要借助一系列工具(甚至 Photoshop)完成压缩、雪碧图、hash、部署等操作。 而在 Webpack 中&#xff0c;图像以及其它多媒体…

JAVA课程复习

简答题65分(理解)❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀看本章小结 读程序写结果45分 填空102分(lambda) 编程310分(20~30行) ❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀-❀ 1~13章,11、13章重…

小时候的子弹击中了现在的我-hive进阶:案例解析(第18天)

系列文章目录 一、Hive表操作 二、数据导入和导出 三、分区表 四、官方文档&#xff08;了解&#xff09; 五、分桶表&#xff08;熟悉&#xff09; 六、复杂类型&#xff08;熟悉&#xff09; 七、Hive乱码解决&#xff08;操作。可以不做&#xff0c;不影响&#xff09; 八、…

Lr、LrC软件下载安装 Adobe Lightroom专业摄影后期处理软件安装包分享

Adobe Lightroom它不仅为摄影师们提供了一个强大的照片管理平台&#xff0c;更以其出色的后期处理功能&#xff0c;成为了摄影爱好者们争相追捧的必备工具。 在这款软件中&#xff0c;摄影师们可以轻松地管理自己的照片库&#xff0c;无论是按拍摄日期、主题还是其他自定义标签…

【JVM基础篇】垃圾回收

文章目录 垃圾回收常见内存管理方式手动回收&#xff1a;C内存管理自动回收(GC)&#xff1a;Java内存管理自动、手动回收优缺点 应用场景垃圾回收器需要对哪些部分内存进行回收&#xff1f;不需要垃圾回收器回收需要垃圾回收器回收 方法区的回收代码测试手动调用垃圾回收方法Sy…

Python | Leetcode Python题解之第206题反转链表

题目&#xff1a; 题解&#xff1a; # Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution:def reverseList(self, head: Optional[ListNode]) -> Optio…

QT事件处理及实例(鼠标事件、键盘事件、事件过滤)

这篇文章通过鼠标事件、键盘事件和事件过滤的三个实例介绍事件处理的实现。 鼠标事件及实例 鼠标事件包括鼠标的移动、按下、松开、单击和双击等。 创建一个MouseEvent项目&#xff0c;通过项目介绍如何获得和处理鼠标事件。程序效果如下图所示。 界面布局代码如下&#xff…

后端之路第三站(Mybatis)——入门配置

一、Mybatis是啥&#xff1f; 就是一个用java来操控数据库的框架语言 之前学的datagrip或者navicat这些软件里我们操作数据库&#xff0c;原理是我们编写完的操作语句发送到服务器传送到数据库系统&#xff0c;然后数据库执行完之后再发送给服务器返回给datagrip或者navicat显…

独立开发者系列(13)——示例理解面向对象与过程

专业术语晦涩难懂&#xff0c;特别是当你没有写过稍微大点的系统的时候&#xff0c;你要理解这里面的区别很难。 从最简单的早期我们学习开始&#xff0c;我们除了练习hello world掌握了入门函数之后&#xff0c;基本都再练习算法。比如水仙花数的获取&#xff0c;冒泡排序&…

phpMyAdmin | mysqli::real_connect(): (HY000/2002): No such file or directory

法一&#xff1a;第一次安装宝塔 第一次安装宝塔mysql服务是默认关闭的&#xff0c;需要手动打开&#xff0c;打开服务再次进入phpMyAdmin发现可以进入了 法二&#xff1a;第一种方法没解决用这种 出现mysqli::real_connect(): (HY000/2002): No such file or directory错误通…

Java | Leetcode Java题解之第206题反转链表

题目&#xff1a; 题解&#xff1a; class Solution {public ListNode reverseList(ListNode head) {if (head null || head.next null) {return head;}ListNode newHead reverseList(head.next);head.next.next head;head.next null;return newHead;} }