算法2:滑动窗口(上)

文章目录

  • 长度最小子数组
  • 无重复字符的最长子串
  • [最大连续 1 的个数III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)
  • 将x减到0的最小操作数

长度最小子数组

在这里插入图片描述

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = INT_MAX;
        int right = 0, left = 0;
        int sum = 0;
        while(left <= right && right < nums.size())
        {
            sum += nums[right++];//进窗口
            while(sum >= target) //判断
            {
                len = min(len, right - left);
                sum -= nums[left++]; // 出窗口
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};

无重复字符的最长子串

在这里插入图片描述

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int left = 0, right = 0;
        int hash[127] = {0};
        int res = 0;

        while (right < n) {
            hash[s[right]]++; // 进窗口,右端滑动
            if (hash[s[right]] > 1) {
                while (hash[s[left]] != hash[s[right]])
                    hash[s[left++]]--;
                hash[s[left++]]--;
            } else {
                res = max(res, right - left + 1);
            }
            right++;
        }
        return res;
    }
};

int max(int a, int b)
{
    return a > b ? a : b;
}
int lengthOfLongestSubstring(char * s){
    int n = strlen(s);
    int left = 0, right = 0, res = 0;
    int hash[127] = {0};
    while(right < n)
    {
        hash[s[right]]++;
        while(hash[s[right]] > 1)
            hash[s[left++]]--;
        res = max(res,right - left + 1);
        right++;
    }
    return res;
} 

解析:
在这里插入图片描述


最大连续 1 的个数III

在这里插入图片描述

在这里插入图片描述

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int res = 0,zero = 0;
        for(int left = 0,right = 0; right < nums.size();right++)
        {
            if(nums[right] == 0)    zero++;//进窗口
            while(zero > k)
            {
                if(nums[left++] == 0) zero--;
            }    
            res = max(res,right - left + 1);
        }
        return res;
    }
};
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, right = 0;
        int zero = 0, res = 0;
        while (right < nums.size()) {
            // 进窗口
            while (right < nums.size() && nums[right])
                right++;
            // 判断
            if (right < nums.size() && ++zero <= k) {
                right++;
                // 数据更新
                res = max(res, right - left);
            } else {
                // 数据更新
                res = max(res, right - left);
                // 出窗口
                while (left < right && nums[left])
                    left++;
                k--;
                left++;
                right++;
            }
        }
        return res;
    }
};

将x减到0的最小操作数

在这里插入图片描述

正难则反

该题从正面去解,一会儿左一会儿右全凭场景所变化,编码写起来非常繁琐;此时,运用数学思维反证法来解决会不会简单些呢?该题需要求最小操作数,那也就意味着剩下的数据量是最大的,而且因为每次操作都在最左或者最右边,那也就是说剩下的数据是原数据的连续子串;OK,现在我们只需要求出一个符合的尽可能保证数据量大其sum值等于sum(nums) - x连续子串即可.

那现在将符合要求数据看成一个窗口往后滑动即可。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for(int e : nums)   sum += e;
        if(x > sum) return -1;
        if(x == sum) return nums.size();
        int target = sum - x;
        int res = -1;
        for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
        {
            tmp += nums[right];//进窗口
            while(tmp >= target)
            {
                if(tmp == target)   res = max(res, right - left +1);//判断+记录长度
                tmp -= nums[left++];// 出窗口
            }
        }

        if(res == -1)
            return res;
        return nums.size() - res;
    }
};
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int e : nums)
            sum += e;
        if (x > sum)
            return -1;//细节
        int target = sum - x;
        int res = -1;
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) {
            tmp += nums[right]; // 进窗口
            while (tmp > target) // 判断
                tmp -= nums[left++]; // 出窗口
            if (tmp == target)
                res = max(res, right - left + 1); // 更新数据
        }

        if (res == -1)
            return res;
        return nums.size() - res;
    }
};

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

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

相关文章

SAP---成本中心采购跟消耗性采购的区别

1.常规库存采购业务的说明&#xff1a; 1.从业务层面分析&#xff0c;企业的常规库存物料采购是&#xff1a; 采购部门下采购订单后&#xff0c;供应商送货&#xff0c;当货物到厂后&#xff0c;由库管员执行收货操作&#xff0c;先将货物收到仓库中&#xff0c;再由各个需求…

APP广告变现,开启你的APP盈利新纪元

随着科技的飞速发展&#xff0c;智能手机已经成为了我们生活中不可或缺的一部分。而在这个数字化时代&#xff0c;APP应用更是如雨后春笋般层出不穷&#xff0c;为我们的生活带来了极大的便利。然而&#xff0c;对于APP开发者来说&#xff0c;如何在激烈的市场竞争中脱颖而出&a…

智能的PHP开发工具PhpStorm v2024.1全新发布——支持PHPUnit 11.0

PhpStorm是一个轻量级且便捷的PHP IDE&#xff0c;其旨在提高用户效率&#xff0c;可深刻理解用户的编码&#xff0c;提供智能代码补全&#xff0c;快速导航以及即时错误检查。可随时帮助用户对其编码进行调整&#xff0c;运行单元测试或者提供可视化debug功能。 立即获取PhpS…

Docker Portainer使用

Portainer是什么 Docker Portainer是一个轻量级的 Web UI 管理界面,可以用来管理Docker环境。它提供了一个直观的控制台,用户可以通过它来管理Docker主机、容器、网络、卷等Docker资源。 Portainer的主要功能和特点包括: 容器管理:可以查看、启动、停止、删除容器,以及查看容器…

SpringBoot中使用AOP实现日志记录功能

目录 一、SpringBoot框架介绍 二、什么是 AOP 三、日志记录的必要性 四、SpringBoot中如何使用AOP实现日志记录功能 一、SpringBoot框架介绍 SpringBoot是一个开源的Java开发框架&#xff0c;旨在简化基于Spring框架的应用程序的开发。它提供了一套开箱即用的工具&#xf…

WebGL的医学培训软件开发

开发基于WebGL的医学培训软件是一项复杂且技术性强的任务&#xff0c;需要结合医学专业知识和计算机图形学技术。以下是详细的开发流程和关键步骤。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1.需求分析与定义 目标用户&#xf…

【C语言】——函数栈帧的创建与销毁

函数栈帧的创建与销毁 本文主要讲解了函数调用过程中其栈帧的创建与销毁&#xff0c;内容干货较多&#xff0c;希望大家认真品味。 使用C语言进行函数调用时&#xff0c;是否会有很多疑问&#xff1a; 1.局部变量是如何创建的&#xff1f; 2.局部变量在未初始化的情况下&#x…

从ES5迈向ES6:探索 JavaScript 新增声明命令与解构赋值的魅力

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;JavaScript 精粹 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; ES5、ES6介绍 文章目录 &#x1f4af;声明命令 let、const&#x1f35f;1 let声明符&a…

代码生成器(一)---项目概述以及项目初始化

目录 一、项目概述 1.代码生成器解决的问题 2.代码生成器的实际应用 3.本地代码生成器的业务流程 4.实现思路 二、项目初始化 项目Gitee地址&#xff1a;Code-Generator: 代码生成器&#xff01;&#xff01;&#xff01; 一、项目概述 1.代码生成器解决的问题 代码生成器本…

使用vue和element_ui搭建后端页面

使用vue和element_ui搭建后台管理页面 效果顶部和左侧内容固定&#xff0c;中间内容滚动 <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"&g…

地理信息系统(GIS)软件开发

地理信息系统&#xff08;GIS&#xff09;软件开发是一项复杂且系统性很强的工程&#xff0c;涉及空间数据的采集、管理、分析和展示。以下是一个典型的GIS软件开发流程&#xff0c;包括各个步骤的详细说明。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#…

2024电工杯B题食谱评价与优化模型思路代码论文分析

2024年电工杯数学建模竞赛B题论文和代码已完成&#xff0c;代码为B题全部问题的代码&#xff0c;论文包括摘要、问题重述、问题分析、模型假设、符号说明、模型的建立和求解&#xff08;问题1模型的建立和求解、问题2模型的建立和求解、问题3模型的建立和求解&#xff09;、模型…

【STL专题】深入探索C++之std::string:不止于字符串【万字详解】

欢迎来到CILMY23的博客 &#x1f3c6;本篇主题为&#xff1a;深入探索C之std::string&#xff1a;不止于字符串 &#x1f3c6;个人主页&#xff1a;CILMY23-CSDN博客 &#x1f3c6;系列专栏&#xff1a;Python | C | C语言 | 数据结构与算法 | 贪心算法 | Linux &#x1f3…

Nginx - 一键实现Nginx的快速安装和优化配置

文章目录 思路实现二次优化 思路 初始化下载工具目录并下载依赖&#xff1a; 创建临时目录 /tmp/tools。下载 OpenSSL、PCRE 和 Zlib 的压缩包。解压这些依赖包到指定目录。 设置NGINX的用户和脚本&#xff1a; 添加 nginx 用户。创建目录和启动、停止、重载NGINX的脚本。 安装…

如何异地组网添加摄像机?

本文将介绍如何使用天联技术实现异地组网添加摄像机&#xff0c;并保障数据的安全性。 安防摄像机的应用愈发广泛&#xff0c;无论是家庭安防还是企业监控&#xff0c;摄像机都扮演着重要角色。在一些特殊场合或者特殊需求下&#xff0c;我们需要将摄像机添加到异地网络中进行监…

Web开发——HTMLCSS

1、概述 Web开发分前端开发和后端开发&#xff0c;前端开发负责展示数据&#xff0c;后端开发负责处理数据。 HTML&CSS是浏览器数据展示相关的内容。 1&#xff09;网页的组成部分 文字、图片、音频、视频、超链接、表格等等 2&#xff09;网页背后的本质 程序员写的前端…

神经网络基础结构

1. 神经网络 在神经网络中&#xff0c;每个神经元都有一个与之关联的权重和偏置&#xff0c;它们用于计算神经元的输出值。神经元接收来自上一层神经元的输入&#xff0c;并将这些输入与权重相乘并加上偏置&#xff0c;然后通过激活函数进行非线性处理&#xff0c;最终产生输出…

Qt案例练习(有源码)

项目源码和资源&#xff1a;Qt案例练习: qt各种小案例练习,有完整资源和完整代码 1.案例1 项目需求&#xff1a;中间为文本框&#xff0c;当点击上面的复选框和单选按钮时&#xff0c;文本框内的文本会进行相应的变化。 代码如下&#xff1a; #include "dialog.h" …

【全开源】智能名片系统源码(Fastadmin+ThinkPHP和Uniapp)

数字时代的新名片&#xff0c;连接未来的桥梁 引言 在数字化浪潮的推动下&#xff0c;传统名片已经逐渐淡出人们的视线。取而代之的是智能名片系统&#xff0c;它以其高效、便捷和智能化的特点&#xff0c;成为了商务交流的新宠。而智能名片系统源码&#xff0c;作为其核心驱…

nextcloud 安装部署

php版本不对 ubuntu nginx 配置php 网站-CSDN博客 抄自chatgpt ubuntu完全卸载干净某个包-CSDN博客 以及设置基本的php nginx环境参照上面两篇博文 然后参照官方文档 Example installation on Ubuntu 22.04 LTS — Nextcloud latest Administration Manual latest document…