当前位置: 首页 > article >正文

C++算法第五天

本篇文章继续和大家一起刷算法题

第一题

题目链接

. - 力扣(LeetCode)

题目解析

 题目要求:

这是一个连续的子数组

计算子数组内元素的和,若数组内元素的和符合 >= target的值并且该子数组的长度是最短的,则返回该长度

代码原理

原理一:暴力枚举

原理二:滑动窗口

代码编写

对应原理一

class Solution {

public:

    int minSubArrayLen(int target, vector<int>& nums) {

        int len = INT_MAX;

        for(int left = 0; left < nums.size(); left++)

        {

            int sum = 0;

            for(int right = left; right < nums.size(); right++)

            {

                sum += nums[right];

                if(sum >= target)

                {

                    len = min(len, right - left + 1);

                    break;

                }

            }

        }

        if(len == INT_MAX)

        {

            len = 0;

        }

        return len;

    }

};

这里值得注意的是暴力枚举会超过时间限制,但并不是说这种方法是错误的

对应原理二

class Solution {

public:

    int minSubArrayLen(int target, vector<int>& nums) {

        int left = 0, right = 0, sum = 0, len = INT_MAX;

    while(right < nums.size())

    {

        sum += nums[right];//进窗口

        while(sum >= target)//判断

        {//4

            len = min(len, right + 1 - left);//更新结果

            sum -= nums[left++];//出窗口

        }

            right++;    

    }

    if(len == INT_MAX)

    {

        len = 0;

    }

    return len;

    }

};

本题总结

1. 首这个解法叫滑动窗口,本质是同向双指针

2. 使用这个解法的原因是利用了单调性

3.滑动窗口的正确性:利用的单调性,规避了没必要的枚举行为

4.枚举二字算是在博主的文章中第一次出现,那么我也解释枚举是什么意思,枚举就是将每一种情况都一一列举出来

第二题

题目链接

3. 无重复字符的最长子串 - 力扣(LeetCode)

题目解析

题目要求:返回字符串,且字符串内的字符不能有相同

代码原理

方法二:滑动窗口

总而言之,如果nums[right]若与hash表中的字符相同则出窗(即在哈希表中删除)

代码编写

方法二:滑动窗口

class Solution {

public:

    int lengthOfLongestSubstring(string s) {

        int n = s.size(),len = 0;

        int hash[128] = {0};

        for(int left = 0, right = 0; right < n; right++)

        {

            hash[s[right]]++;

            while(hash[s[right]] > 1)

            {

                hash[s[left++]]--;

            }

            len = max(len, right - left + 1);

        }

        return len;

    }

};

第三题

题目链接

数组中两个字符串的最小距离__牛客网

题目解析

代码原理

思路一:暴力枚举

思路二:贪心算法

代码编写

对应法二

#include <iostream>
#include<string>
using namespace std;

int main() {
    int n = 0;
    int prev1 = -1, prev2 = -1,min_distance = 0x3f3f3f3f;
    cin >> n;
    string strs, str1, str2;
    cin >> str1 >> str2;
    for(int i = 0; i < n; i++)
    {
        cin >> strs;
        if(strs == str1)
        {
            if(prev2 != -1)
            {
                min_distance = min(min_distance, i - prev2);
            }
            prev1 = i;
        }
        else if(strs == str2)
        {
            if(prev1 != -1)
            {
                min_distance = min(min_distance, i - prev1);
            }
            prev2 = i;
        }
    }
    if(min_distance == 0x3f3f3f3f) cout << -1 << endl;
    else cout << min_distance << endl;
return 0;
}
// 64 位输出请用 printf("%lld")

本篇文章的算法题就先讲到这里,我们下期文章再见。

都看到这了,给个三联再走呗,谢谢啦!!!


http://www.kler.cn/a/373227.html

相关文章:

  • 「C/C++」C++标准库之#include<fstream>文件流
  • Netron:神经网络模型可视化工具指南【全网最详细】
  • 基于SpringBoot+Vue+MySQL的房屋租赁系统
  • 开关灯问题(c语言)
  • java:入门基础(1)
  • 深度强化学习-学习笔记
  • 无人机产校融合,突破理论与实战代沟,快速转化市场价值
  • php解密,sg11解密-sg15解密 如何由sourceGuardian11-sourceGuardian15加密(sg11加密~sg15加密)的源码
  • Flutter主题切换
  • Apache Linkis:重新定义计算中间件
  • 事务的四大隔离级别、数据库中的共享锁与排他锁、MySQL 的行级锁与表级锁
  • C++虚函数(详解)
  • 无人机避障——路径规划篇(一) JPS跳点搜索算法A*算法对比
  • React四官方文档总结一UI与交互
  • 4.2-7 运行MR应用:词频统计
  • flutter VideoPlayer适配:保持视频的原始宽高比,缩放视频使它完全覆盖父容器
  • Vue生成名片二维码带logo并支持下载
  • 《人工智能炒股:变革与挑战》
  • 《YOLO 目标检测》—— YOLO v3详细介绍
  • Linux rabbitmq客户端 SimpleAmqpClient 源码编译
  • docker 数据目录迁移
  • 正确认识HTTP和HTTPS协议及其在Java Web项目中的应用!
  • 1_信息化项目实施方案
  • 数据结构:(OJ387)字符串中的第一个唯一字符
  • 恋爱脑学Rust之闭包三Traits:Fn,FnOnce,FnMut
  • [Mysql] 介绍一下PROCEDURE、TRIGGERS和EVENTS