leetcode每日一题-3101 交替子数组计数

暴力遍历:看起来像是回溯,实际上就是递归

class Solution {
private:
    long long _res = 0;
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        
        backtrack(nums, 0);
        return _res;
    }
    void backtrack(vector<int>& nums, long long start)
    {
        if(start>nums.size())
            return ;
        for(long long i=start; i<nums.size(); ++i)
        {
            // 单个元素必然是交替子数组
            if(i==start)
            {
                ++_res;
            }else if(nums[i]!=nums[i-1]){
                ++_res;
            }else{
                break;
            }
        }
        backtrack(nums, ++start);
    }
};

这种方法其实也是可以做的但是会超时哈哈哈。

注意题目给的条件,元素值只有0和1。把握这个点其实就非常好解题了。

假设现在有一个队列0101.....1,队列以元素1结尾说明那么当我们新加入一个元素队列元素总和变了,说明是元素值是1,鉴定重复,元素总和没变说明是0,就是不重复的。队列元素以0结尾情况就恰好相反了。

遍历数组,记录上一个数的数值和当前最长交替子数组的长度。如果当前数和之前的数不一样,则交替子数组的长度加一,否则交替子数组长度为一。
当前最长交替子数组的长度,即是以当前元素为结尾的交替子数组的个数,累加到答案当中。

class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        long long res = 0, cur = 0;
        int pre = -1;
        for (int a : nums) {
            cur = (pre != a) ? cur + 1 : 1;
            pre = a;
            res += cur;
        }
        return res;
    }
};

=========================================================================

上面是神智不清随便copy的官方题解,下面来说一下这个题目的本质规律。

举个实际的例子,[0, 1, 0, 1, 0]。

设总个数count=0,左边界left从0开始, 右边界right从0开始,那么则有:

left=0, right=0; [0], 满足条件, count+=1, count = 1

left=0, right=1; [0,1], 满足条件, count+=2, count = 3

left=0, right=2; [0,1, 0], 满足条件, count+=3, count = 6

left=0, right=3; [0,1, 0, 1], 满足条件, count+=4, count = 10

left=0, right=4; [0,1, 0, 1, 0], 满足条件, count+=5, count = 10

发现规律了没? count+=(left-right+1)。把握这个规律就可以进行高效的遍历,发现当前位置的元素不符合要求,直接把左边界left挪到当前位置再进行遍历即可。

看到这里如果只追求AC就可以结束了。

再深入的想一下,上述规律为什么是这样子的呢?能不能用数学语言描述一下呢?当然是可以的,聪明的GPT已经给出了答案。

这个题目的本质是在考察,一个长度为n的序列,不重复的子序列有多少?为了节省大家的时间直接截图!

GPT3.5做的,感觉比官方题解好点。

#include <vector>
using namespace std;

class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        long long count = 0;
        int left = 0;
        
        for (int right = 0; right < nums.size(); ++right) {
            if (right > 0 && nums[right] == nums[right - 1]) {
                left = right; // 出现相邻相同元素,更新左边界
            }
            count += (right - left + 1); // 加上以 right 为结尾的所有交替子数组数量
        }
        
        return count;
    }
};

这是一条吃饭博客,由挨踢零声赞助。学C/C++就找挨踢零声,加入挨踢零声,面试不挨踢!

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

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

相关文章

黑马|最新AI+若依 |初识项目

本章主要内容是&#xff1a; 1.快速搭建了若依前后端项目在本地 2.实现了单表的增删改查快速生成 文章目录 介绍1.若依介绍2.若依的不同版本3.项目运行环境 初始化前后端项目1.下载若依项目2.初始化后端a.把表导入到数据库中b.更改application.yml文件 3.初始化前端a.安装依赖…

【游戏引擎之路】登神长阶(六)——雅达利2600汇编学习,任天堂居然还真不是抄袭起家

5月20日-6月4日&#xff1a;攻克2D物理引擎。 6月4日-6月13日&#xff1a;攻克《3D数学基础》。 6月13日-6月20日&#xff1a;攻克《3D图形教程》。 6月21日-6月22日&#xff1a;攻克《Raycasting游戏教程》。 6月23日-7月1日&#xff1a;攻克《Windows游戏编程大师技巧》。 7…

基于海思Hi3403V100方案开发双目1600万拼接相机测试截图

海思Hi3403V100平台SOC内置四核A55&#xff0c;提供高效且丰富和灵活的CPU资源&#xff0c;以满足客户计算和控制需求&#xff0c;并且集成单核MCU&#xff0c;已满足一些低延时要求较高场景。 多目相机PE108CB板是针对该芯片设计的一款多目凭借相机PCBA&#xff0c;硬件接口支…

node.js_HTTP协议

Hypertext Transfer Protocol 超文本传输协议 1.HTTP报文 请求行 请求头 请求体 它的内容形式很灵活&#xff0c;可以设置任意内容 2.HTTP响应报文 响应状态码 响应状态的描述 遇到陌生的状态码可以参考一下这个网址&#xff1a; https://developer.mozilla.org/zh-C…

期末成绩发布方式

期末考试结束后&#xff0c;成绩单的发放总是让老师们头疼不已。想象一下&#xff0c;每个学生的成绩都需要老师一个个私信给家长&#xff0c;不仅耗时耗力&#xff0c;而且极易出错。 在传统的成绩单发放方式中&#xff0c;老师往往需要通过电子邮件、短信或者微信等方式&…

python爬虫入门(一)之HTTP请求和响应

一、爬虫的三个步骤&#xff08;要学习的内容&#xff09; 1、获取网页内容 &#xff08;HTTP请求、Requests库&#xff09; 2、解析网页内容 &#xff08;HTML网页结构、Beautiful Soup库&#xff09; 3、存储或分析数据 b站学习链接&#xff1a; 【【Python爬虫】爆肝两…

数据合并 26-30题(30 天 Pandas 挑战)

数据合并 1. 知识点1.27 左连接1.28 数据填充与交叉连接1.29 获取列值列表 题目2.26 合作过至少三次的演员和导演2.27 使用唯一标识码替换员工ID2.28 学生们参加各科测试的次数2.29 至少有5名直接下属的经理2.30 销售员 1. 知识点 1.27 左连接 datapd.merge(employees,employ…

什么是五级流水?银行眼中的“好流水”,到底是什么样的?

无论是按揭买房还是日常贷款&#xff0c;银行流水都是绕不开的一环。规划好你的流水&#xff0c;不仅能让你在申请贷款时更有底气&#xff0c;还可能帮你省下不少冤枉钱。今天&#xff0c;咱们就来一场深度剖析&#xff0c;聊聊如何在按揭贷款、个人经营抵押贷款前&#xff0c;…

什么是SysTick?

一&#xff0c;滴答定时器SysTick SysTick&#xff0c;即滴答定时器&#xff0c;是内核中一个特殊的定时器&#xff0c;用于提供系统级的定时服务。是一个24位递减计时器&#xff0c;具有自动重载值寄存器的功能 。当计数器到达自动重载值时&#xff0c;它会自动重新加载新的计…

深入探索Python库的奇妙世界:赋能编程的无限可能

在编程的浩瀚宇宙中&#xff0c;Python以其简洁的语法、强大的功能和广泛的应用领域&#xff0c;成为了众多开发者心中的璀璨明星。而Python之所以能够如此耀眼&#xff0c;很大程度上得益于其背后庞大的库生态系统。这些库&#xff0c;如同一块块精心雕琢的积木&#xff0c;让…

【Linux详解】进程等待 | 非阻塞轮询

引入&#xff1a; 为什么&#xff1f;是什么&#xff1f;怎么办 是什么&#xff1f; 进程等待是指父进程暂停自己的执行&#xff0c;直到某个特定的子进程结束或发生某些特定的事件。 为什么&#xff1f; 僵尸进程刀枪不入&#xff0c;不可被杀死&#xff0c;存在内存泄露…

安卓备忘录App开发

安卓备忘录APP开发,文章末尾有源码和apk安装包 目标用户: 普通安卓手机用户,需要一个简单易用的备忘录App来记录和管理日常事务。 主要功能: 用户注册: 用户可以创建一个账号,输入用户名和密码。 用户登录: 用户可以通过用户名和密码登录到应用。 用户信息存储: 用户名和…

【python】OpenCV—Feature Detection and Matching

参考学习来自OpenCV基础&#xff08;23&#xff09;特征检测与匹配 文章目录 1 背景介绍2 Harris角点检测3 Shi-Tomasi角点检测4 Fast 角点检测5 BRIEF 特征描述子6 ORB(Oriented Fast and Rotated Brief) 特征描述子7 SIFT(Scale Invariant Feature Transform) 特征描述子8 SU…

从一个(模型设计的)想法到完成模型验证的步骤

从有一个大型语言模型&#xff08;LLM&#xff09;设计的想法到完成该想法的验证&#xff0c;可以遵循以下实践步骤&#xff1a; 需求分析&#xff1a; 明确模型的目的和应用场景。确定所需的语言类型、模型大小和性能要求。分析目标用户群体和使用环境。 文献调研&#xff1a…

【全面讲解下iPhone新机官网验机流程】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

实现多数相加,但是传的参不固定

一、情景 一般实现的加法和减法等简单的相加减函数的话。一般都是写好固定传的参数。比如&#xff1a; function add(a,b) {return a b;} 这是固定的传入俩个&#xff0c;如果是三个呢&#xff0c;有人说当然好办&#xff01; 这样写不就行了&#xff01; function add(a…

protobuf及其使用

首先打开proto文件&#xff0c;定义一个类&#xff08;数据结构&#xff09;&#xff0c;并编写成员变量 使用protobuf编译器protoc编译proto文件为.pb.h和.pb.c文件(c) 看绿色注释部分&#xff1a;从左至右为&#xff0c;编译器&#xff0c;.proto文件的路径&#xff0c;编译的…

YOLO V7网络实现细节(2)—网络整体架构总结

YOLO V7网络整体架构总结 YOLO v7网络架构的整体介绍 不同GPU和对应模型&#xff1a; ​​​​​​​边缘GPU&#xff1a;YOLOv7-tiny普通GPU&#xff1a;YOLOv7​​​​​​​云GPU的基本模型&#xff1a; YOLOv7-W6 激活函数&#xff1a; YOLOv7 tiny&#xff1a; leaky R…

微深节能 煤码头自动化翻堆及取料集控系统 格雷母线

微深节能格雷母线高精度位移测量系统是一种先进的工业自动化位置检测解决方案&#xff0c;它被广泛应用于煤码头自动化翻堆及取料集控系统中&#xff0c;以实现对斗轮堆取料机等大型机械设备的精准定位和自动化控制。 系统原理简述&#xff1a; 格雷母线系统的工作原理基于电磁…

有趣的算法

目录&#xff1a; 1、百钱买百鸡 2、韩信点兵 1&#xff09;概述 2&#xff09;正常取余算法 3&#xff09;循环算法 1、百钱买百鸡 我国古代《算经》中的“百钱买百鸡”问题&#xff1a; 鸡翁一&#xff0c;值钱五&#xff1b;鸡母一&#xff0c;值钱三&#xff1b;鸡…