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

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.lryc.cn/news/473470.html

相关文章:

  • 牛客网剑指Offer-树篇-JZ26 树的子结构
  • FFmpeg 4.3 音视频-多路H265监控录放C++开发六,使用SDLVSQT显示yuv文件
  • Spring 设计模式之适配器模式
  • 多传感器数字化分析系统
  • Java 基础教学:面向对象编程基础-封装、继承与多态
  • Ubuntu环境本地部署DbGate数据库管理工具并实现无公网IP远程访问
  • 【AI抠图整合包及教程】Meta SAM 2:视觉分割的革命性飞跃
  • 使用语言模型进行文本摘要的五个级别(llm)
  • ubuntu交叉编译libffi库给arm平台使用
  • 【jvm】空间分配担保策略
  • iQOO手机怎样将屏幕投射到MacBook?可以同步音频吗?
  • BUU usualCrypt1
  • 第十七章 标准库特殊设施
  • 【格言分享】程序员的经典名言解读
  • SpringBoot接收LocalDateTime参数
  • Typora配置GitHub图床--结合PicGo
  • 【书生.浦语实战营】——入门岛
  • WPF+MVVM案例实战(十四)- 封装一个自定义消息弹窗控件(下)
  • 嵌入式——STM32外设应用
  • HCIA(ACL)
  • react基础之reactHooks
  • Java基础0-Java概览
  • SW绘制曲面
  • css知识点梳理2
  • 攻防世界 MISC miao~详解
  • 使用 `tracert [options] <目标地址>` 命令的详细介绍
  • 闲一品交易平台:SpringBoot技术的新境界
  • 【深入浅出】深入浅出transformer(附面试题)
  • 苹果重大更新,macOS与iOS同时推出更新!功能真好用
  • 刘艳兵-DBA016-在您的数据库中,SALES表存在于SH用户中,并且启用了统一审计。作为DBA,您成功执行了以下指令: