LeetCode-3191 使二进制数组全部等于1的最少操作次数

embedded/2024/10/19 15:05:41/

又来到了今天的每日一题,距离上次更新每日一题得有十天了。

主要原因是这十天的题要么简单到爆,要么难到爆,再要么就是最近学校安排实训,时间比较紧。

废话不多说,来看看今天的题目。

题目很简单,就是给个数组,数组里的元素要么是0要么是1(成都?)

我们每次可以把三个连续的元素翻转,也就是0变1,1 变0,问我们最少操作几次可以把数组里的元素全部变成1。

数组首尾不相连,所以我们能翻转的三个元素的起点索引是(0 ~ n-2 (n为数组长度))。

这道题的通过率有77%,所以它实际上就是看着唬人,实际上不难。

我们一步步思考,我们第一步应该先翻转哪里?

如果数组第一个元素就是0,那么第一个元素是肯定要翻转的,而我们只有从索引0的位置开始翻转才可以翻转到第一个元素,其他位置都不行,所以这个翻转是逃不掉的。

翻转完之后第一个元素就是1了,那么我们是不是可以先把它排除在外?

因为它已经是1了,而只有从索引0的位置开始翻转才能改变到它,为了保持它始终为1,我们应该不再从索引0的位置翻转,既然如此,我们自然是可以把它排除在外。

排除之后,我们把之前索引1的位置当成新的索引0,然后重复上述过程……

大家拿纸笔找个示例画一画就明白了。

我们“排除”的时候并不需要把这个元素从数组中删除,我们只需要移动索引指针即可,并且因为翻转的起点位置范围是0~n-2,所以要控制一下for循环的范围。

示例代码如下:

class Solution {
public:int minOperations(vector<int>& nums) {int n = nums.size();int res = 0;for(int i = 0; i < n - 2; ++i){if(nums[i] != 1){   // 如果不等于1,那么需要翻转++res;nums[i + 1] = nums[i + 1] == 1 ? 0 : 1;     // 翻转后两位nums[i + 2] = nums[i + 2] == 1 ? 0 : 1;}}// 若数组最后两位都为1,那么可以操作,反之无法都变成1.if(nums[n - 1] == 1 && nums[n - 2] == 1) return res;return -1;}
};

合理推测明天的每日一题是下面这道。

翻转三次改成了翻转剩余元素。

如果按照上一题的做法做的话是会超时的,因为翻转而循环的次数太多了,如果是剩余的元素都要翻转,实际上我们可以不去真的翻转。

具体怎么做明天再说,我还要水一篇文呢。


http://www.ppmy.cn/embedded/128767.html

相关文章

【从零到一的笔试突破】——day1笔试巅峰(6道笔试题)ACM模式让笔试更有感觉

文章目录 数字统计&#xff08;数学模拟&#xff09;两个数组的交集&#xff08;哈希&#xff09;点击消除&#xff08;栈&#xff09;牛牛的快递&#xff08;模拟&#xff09;最小花费爬楼梯&#xff08;动态规划&#xff09;数组中两个字符串的最小距离&#xff08;滑动窗口o…

使用RNN、LSTM和Transformer进行时间序列预测

文章目录 1 RNN & LSTMRNN结构LSTM结构样本和标签 2 Transformertransformer结构位置编码 1 RNN & LSTM RNN结构 LSTM结构 代码&#xff08;使用CPU&#xff09;&#xff1a; import numpy as np import torch from matplotlib import pyplot as plt from torch impo…

基于SpringBoot的大学生智能消费记账管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…

微信小游戏之隐私协议开发指南、用户信息获取

简介 因为微信规则修改了&#xff0c;想要获取新的信息需要阅读微信小游戏的规则&#xff0c;下面&#x1f447;&#x1f3fb;是最新通知文档&#xff0c;建议认真阅读。 阅读官方文档 官方隐私授权相关的API链接&#xff1a;wx.requirePrivacyAuthorize(Object object) | 微…

神经网络反向传播交叉熵 计算损失函数对隐藏层偏置b1的梯度

本文是交叉熵损失函数为代表的两层神经网络的反向传播量化求导计算公式中的一个公式&#xff0c;单独拿出来做一下解释说明。 公式 8-19 计算的是损失函数 L L L 对隐藏层偏置 b 1 b_1 b1​ 的梯度。这个步骤是反向传播算法中的关键部分&#xff0c;用来更新隐藏层偏置 b 1 …

计算机毕业设计Python深度学习房价预测 房源可视化 房源爬虫 二手房可视化 二手房爬虫 递归决策树模型 机器学习 深度学习 大数据毕业设计

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 房地产是促进我国经济持续增…

OpenHarmony 入门——ArkUI 自定义组件内同步的装饰器@State小结(二)

文章大纲 引言一、组件内状态装饰器State1、初始化2、使用规则3、变量的传递/访问规则说明4、支持的观察变化的场景5、State 变量的值初始化和更新机制6、State支持联合类型实例 引言 前一篇文章OpenHarmony 入门——ArkUI 自定义组件之间的状态装饰器小结&#xff08;一&…

优化漏洞扫描流程以保障企业数字化业务安全

漏洞扫描技术历经二十余年发展&#xff0c;已从人工搜索演进至开源及商业扫描平台&#xff0c;其应用紧随IT环境与数字业务变迁而不断革新。为有效提升漏洞检测效果&#xff0c;确保企业数字化业务安全运行&#xff0c;安全专家建议遵循以下关键步骤实施漏洞扫描&#xff1a; …