【大战蓝桥杯】 算法·每日一题(详解+多解)-- day10

简介: 【大战蓝桥杯】 算法·每日一题(详解+多解)-- day10

【大战蓝桥杯】 算法·每日一题(详解+多解)-- day10


✨博主介绍

0 和 1 个数相同的子数组

解题思路

💫点击直接资料领取💫


✨博主介绍


🌊 作者主页:苏州程序大白


🌊 作者简介:🏆CSDN人工智能域优质创作者🥇,苏州市凯捷智能科技有限公司创始之一,目前合作公司富士康、歌尔等几家新能源公司


💬如果文章对你有帮助,欢迎关注、点赞、收藏


💅 有任何问题欢迎私信,看到会及时回复

💅关注苏州程序大白,分享粉丝福利


0 和 1 个数相同的子数组


给定一个二进制数组 nums , 找到含有相同数量的 0 和1的最长连续子数组,并返回该子数组的长度。


示例 1:

输入: nums = [0,1]

输出: 2

说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。


示例 2:

输入: nums = [0,1,0]

输出: 2

说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。


提示:


提示:
1 <= nums.length <= 105
nums[i] 不是 0 就是 1


解题思路


错误的思路:滑动窗口,双指针


一开始打算运用双指针的想法,但是就实际而言是难以行通的。


对于[0,0,0,1,1,1,0]最后可能为误判为0。但是实际是6


总结一下,当不能明确得知可以淘汰的某些值时候就最好不要使用双指针。


前面那些0并不能直接判断是否需要淘汰,需要根据后面很多数来确定


public int findMaxLength(int[] nums) {
    int res=0;
    int n=nums.length;
    int slow=0, fast=0;
    int zeroNum=0, oneNum=0;
    while (fast<n){
        for (int i=0; i<2 && fast<n; i++){
            if (nums[fast++]==0) zeroNum++;
            else oneNum++;
        }
        if (oneNum==zeroNum) res = Math.max(res, fast-slow);
        else {
            if (nums[slow++]==0) zeroNum--;
            else oneNum--;
        }
    }
    return res;
}


前缀和+哈希表


把0当做-1处理,这里就转变为了求和为0的子数组的问题


key=前缀和,value=第一次出现过的位置


遍历数组,记录某个前缀和第一次出现的位置,设置初始值为map[0] = -1


当前缀和sum在此前出现过,则说明这两个前缀和区间差构成的所有元素和为0,满足条件更新res的值,否则记录到map中


2c8e5e23cb3944a4a17961a58748cd87.png


class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0, res = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i] == 1 ? 1 : -1;
            if (map.containsKey(sum)) {
                res = Math.max(res, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return res;
    }
}



相关文章
|
27天前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
20天前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
37 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
5月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
53 3
|
6月前
|
存储 算法 Java
蓝桥杯递归算法
蓝桥杯中的递归算法涉及将问题分解为子问题,通过函数自身调用来求解。优点是简洁易懂,但效率低且可能引发栈溢出。示例包括:数组求和、数的阶乘、斐波那契数列及最大公约数计算,以及字符串翻转。代码展示了各种递归场景的Java实现,如`f3`计算数组和,`f`求阶乘,`f1`计算斐波那契数,`f2`找最大公约数,和`f1`字符串反转。
34 1
|
5月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
8天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
26天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
5天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
6天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。
|
11天前
|
存储
基于遗传算法的智能天线最佳阵列因子计算matlab仿真
本课题探讨基于遗传算法优化智能天线阵列因子,以提升无线通信系统性能,包括信号质量、干扰抑制及定位精度。通过MATLAB2022a实现的核心程序,展示了遗传算法在寻找最优阵列因子上的应用,显著改善了天线接收功率。