【算法】经典算法题

文章目录

  • 专题一：双指针
    • 1. 移动零
    • 2. 复写零
    • 3. 快乐数
    • 4. 盛最多水的容器
    • 5. 有效三角形的个数
    • 6. 查找总价格为目标值的两个商品
    • 7. 三数之和
    • 8. 四数之和
  • 专题二：滑动窗口
    • 1. 长度最小的子数组
    • 2. 无重复字符的最长字串
    • 3. 最大连续1的个数 III
    • 4. 将 x 减到 0 的最小操作数

专题一：双指针

1. 移动零

在这里插入图片描述

题目解析
在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

// 写法一
class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 1、下标初始化
        int dest = -1, cur = 0;
        // 2、数组划分
        while(cur < nums.size())
        {
            if(nums[cur]) 
                swap(nums[++dest], nums[cur++]);
            else 
                ++cur;
        }
    }
};

// 写法二
class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
       for(int dest = -1, cur = 0; cur < nums.size(); ++cur)
            if(nums[cur]) // 处理 非0 元素
                swap(nums[++dest], nums[cur]);
    }
};

/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

2. 复写零

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    void duplicateZeros(vector<int>& nums) 
    {
        // 1、初始化
        int dest = -1, cur = 0, n = nums.size();
        // 2、找到最后一个复写的数
        while(true)
        {
            if(nums[cur]) dest += 1;
            else dest += 2;
            if(dest >= n - 1) break;
            ++cur;
        }
        cout << nums[cur] << endl;
        // 1.5、预处理 -> 让 dest 的下标有效
        if(dest == n)
        {
            if(nums[cur]) --cur, --dest;
            else 
            {
                nums[n - 1] = 0;
                dest -= 2;
                cur -= 1;
            }
        }
        // 2、双指针从后往前进行复写操作
        while(cur >= 0)
        {
            if(nums[cur]) nums[dest--] = nums[cur--];
            else
            {
                nums[dest--] = 0;
                nums[dest--] = 0;
                cur--;
            } 
        }
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

3. 快乐数

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
private:
    // 计算每个位置上的数字的平方和
    inline static int BitSum(int num)
    {
        int ret = 0;
        while(num)
        {
            int t = num % 10;
            ret += t * t;
            num /= 10;
        }
        return ret;
    }

public:
    bool isHappy(int n) 
    {
        int slow = n, fast = BitSum(n);
        while(slow != fast)
        {
            slow = BitSum(slow);
            fast = BitSum(BitSum(fast));
        }
        return slow == 1;
    }
};

4. 盛最多水的容器

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0, right = height.size() - 1;
        int ret = INT_MIN;
        while(left != right)
        {
            // 容积 = 长度 * 高度
            int v = (right - left) * min(height[left], height[right]);
            ret = max(ret, v);
            // 移动指针 - 谁小移动谁
            height[left] < height[right] ? ++left : --right;
        }
        return ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

5. 有效三角形的个数

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        // 1、优化
        sort(nums.begin(), nums.end());
        // 2、利用双指针解决问题
        int ret = 0, n = nums.size();
        for(int i = n - 1; i >= 2; --i)
        {
            int left = 0, right = i - 1;
            while(left < right)
            {
                // 当 a+b>c ，a下标属于 [left, right-1]时，都能和 b、c 构成三角形
                // 当 a+b<=c ，b下标属于[left-1, right]时，都不能和 a、c 构成三角形
                if(nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    --right;
                }
                else ++left;
            }
        }
        // 返回值
        return ret;
    }
};

/*
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
*/

6. 查找总价格为目标值的两个商品

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        // 1、数据初始化
        int left = 0, right = price.size() - 1;
        // 2、利用双指针解决问题
        while(left < right)
        {
            int sum = price[left] + price[right];
            if(sum < target) ++left;
            else if(sum > target) --right;
            else return {price[left], price[right]};
        }
        // 题目没有明确说明没有结果的话会怎么样，那么该题的测试用例应该都是有结果的
        // 为了照顾编译器要求一定要返回一个结果，所以我们最后返回一个空数组即可
        return {};
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

7. 三数之和

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        // 1、初始化
        int n = nums.size();
        vector<vector<int>> ret;
        // 2、排序
        sort(nums.begin(), nums.end());
        // 3、依次固定一个数
        for(int i = 0; i < n - 2;)
        {
            // 4、双指针算法找到两数之和等于 aim 的元素
            int left = i + 1, right = n - 1, aim = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < aim) ++left;
                else if(sum > aim) --right;
                else 
                {
                    ret.push_back( {nums[i], nums[left], nums[right]} );
                    ++left, --right; // 保证 left、right 选择的元素不漏
                    // 对 left、right 已经选择过的元素去重
                    while(left < right && nums[left] == nums[left - 1]) ++left;
                    while(left < right && nums[right] == nums[right + 1]) --right;
                }
            }
            // 保证 i 选择的元素不漏
            ++i; 
            // 对 i 已经选择过的元素去重
            while(i < n - 2 && nums[i] == nums[i - 1]) ++i;
        }
        // 5、返回最终结果
        return ret;
    }
};
/*
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
*/

8. 四数之和

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        // 1、初始化
        int n = nums.size();
        vector< vector<int> > ret;
        // 2、排序
        sort(nums.begin(), nums.end());
        // 3、依次固定一个数，然后使用“三数之和”解决问题
        for(int i = 0; i < n - 3;) 
        {
            // 4、再依次固定一个数，然后使用“双指针”解决问题
            for(int j = i + 1; j < n - 2;) 
            {
                int left = j + 1, right = n - 1;
                double aim = (double)target - nums[i] - nums[j];
                // 5、双指针算法找到两数之和等于 aim 的元素
                while(left < right)
                {
                    double sum = nums[left] + nums[right];
                    if(sum < aim) ++left;
                    else if(sum > aim) --right;
                    else
                    {
                        ret.push_back( {nums[i], nums[j], nums[left], nums[right]} );
                        ++left, --right; // 保证 left、right 选择的元素不漏
                        // 对 left、right 已经选择过的元素去重
                        while(left < right && nums[left] == nums[left - 1]) ++left;
                        while(left < right && nums[right] == nums[right + 1]) --right;
                    }
                }
                // 保证 j 选择的元素不漏
                ++j;
                // 对 j 已经选择过的元素去重
                while(j < n - 2 && nums[j] == nums[j - 1]) ++j;
            }
            // 保证 i 选择的元素不漏
            ++i;
            // 对 i 已经选择过的元素去重
            while(i < n - 3 && nums[i] == nums[i - 1]) ++i;
        }
        // 6、返回最终结果
        return ret;
    }
};
/*
- 时间复杂度：O(n^3)
- 空间复杂度：O(1)
*/

专题二：滑动窗口

1. 长度最小的子数组

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        // 1、初始化
        int n = nums.size();
        int minLength = INT_MAX;
        // 2、使用滑动窗口解决问题
        for(int left = 0, right = 0, sum = nums[0]; right < n;)
        {
            if(sum >= target) 
            {
                minLength = min(minLength, right - left + 1);
                sum -= nums[left++];
            }
            else 
            {
                if(++right < n)
                    sum += nums[right];
            }
        }
        // 3、返回值
        return minLength == INT_MAX ? 0 : minLength;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

2. 无重复字符的最长字串

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        // 1、初始化
        int n = s.size();
        vector<int> count(256);
        int left = 0, right = 0, ret = 0;
        // 2、滑动窗口
        int length = 0; //用来记录窗口长度
        while(right < n)
        {
            if(!count[s[right]]) //进窗口
            {
                ++count[s[right]];
                ++length;
                ++right;
                ret = max(ret, length); //更新结果
            }
            else //出窗口
            {
                --count[s[left]];
                --length;
                ++left;
            }
        }
        // 3、返回值
        return ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

3. 最大连续1的个数 III

在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        // 1、初始化
        int n = nums.size();
        int ret = INT_MIN;
        // 2、滑动窗口
        int left = 0, right = 0;
        int length = 0; // 当前子数组中最长连续 1 的长度
        int zero = 0;  // 当前子数组中 0 出现的次数
        while(right < n)
        {
            if(nums[right] != 0) // nums[right] 非 0，此时 right 一定入窗口
            {
                ret = max(ret, ++length);
                ++right;
            }
            else
            {
                if(zero + 1 <= k) 
                {
                    ret = max(ret, ++length);
                    ++zero;
                    ++right;
                }
                else
                {
                    if(nums[left++] == 0)  --zero;
                    --length;
                }
            }
        }
        // 3、返回值
        return ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

4. 将 x 减到 0 的最小操作数

在这里插入图片描述

题目解析
在这里插入图片描述

算法原理
在这里插入图片描述

代码编写

class Solution 
{
public:
    int minOperations(vector<int>& nums, int x) 
    {
        // 1、初始化
        int sum = 0;
        for(const auto e : nums) sum += e;
        int target = sum - x;
        // 2、细节处理(数组中所有元素都大于0，所以 target 小于 0 是不存在的)
        if(target < 0) return -1;
        // 3、滑动窗口
        int ret = -1;
        for(int left = 0, right = 0, tmp = 0; right < nums.size();)
        {
            // 进窗口
            tmp += nums[right++];
            // 出窗口
            while(tmp > target) tmp -= nums[left++];
            // 更新结果
            if(tmp == target) ret = max(ret, right - left);
        }
        // 4、返回结果
        return ret == -1 ? ret : nums.size() - ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

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

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

相关文章

请你说一下Vue中v-if和v-for的优先级谁更高

请你说一下Vue中v-if和v-for的优先级谁更高

v-if 与 v-for简介 v-ifv-forv-if & v-for使用 v-if 与 v-for优先级比较 vue2 中&#xff0c;v-for的优先级高于v-if 例子进行分析 vue3 v-if 具有比 v-for 更高的优先级 例子进行分析 总结 在vue2中&#xff0c;v-for的优先级高于v-if在vue3中&#xff0c;v-if的优先级高…
阅读更多...
61 权限提升-RedisPostgre令牌窃取进程注入

61 权限提升-RedisPostgre令牌窃取进程注入

目录 演示案例:Redis数据库权限提升-计划任务PostgreSQL数据库权限提升Windows2008&7令牌窃取提升-本地Windows2003&10进程注入提升-本地pinjector进程注入工具针对-win2008以前操作系统pexec64 32进程注入工具针对-win2008及后操作系统- (佛系) 涉及资源: postgersql是…
阅读更多...
2023亚太杯数学建模APMCM竞赛C题思路讲解：基于ARIMA与机理模型进行预测

2023亚太杯数学建模APMCM竞赛C题思路讲解：基于ARIMA与机理模型进行预测

本文针对6大问题,从多角度分析了我国新能源电动汽车发展形势与前景。文中针对不同问题,采用了层次分析法、时间序列模型、机理模型、回归模型等数学方法。并结合实例数据,对相关模型进行求解,以量化预测了新能源电动汽车在政策驱动、市场竞争、温室气体减排等多个方面的潜在贡献…
阅读更多...
OpenCV快速入门：图像分析——图像分割和图像修复

OpenCV快速入门：图像分析——图像分割和图像修复

文章目录 前言一、图像分割1.1 漫水填充法1.1.1 漫水填充法原理1.1.2 漫水填充法实现步骤1.1.3 代码实现 1.2 分水岭法1.2.1 分水岭法原理1.2.2 分水岭法实现步骤1.2.3 代码实现 1.3 GrabCut法1.3.1 GrabCut法原理1.3.2 GrabCut法实现步骤1.3.3 代码实现 1.4 Mean-Shift法1.4.1…
阅读更多...
【分布式】小白看Ring算法 - 03

【分布式】小白看Ring算法 - 03

相关系列 【分布式】NCCL部署与测试 - 01 【分布式】入门级NCCL多机并行实践 - 02 【分布式】小白看Ring算法 - 03 【分布式】大模型分布式训练入门与实践 - 04 概述 NCCL&#xff08;NVIDIA Collective Communications Library&#xff09;是由NVIDIA开发的一种用于多GPU间…
阅读更多...
Navicat 技术指引 | 适用于 GaussDB 的数据迁移工具

Navicat 技术指引 | 适用于 GaussDB 的数据迁移工具

Navicat Premium&#xff08;16.2.8 Windows版或以上&#xff09; 已支持对 GaussDB 主备版的管理和开发功能。它不仅具备轻松、便捷的可视化数据查看和编辑功能&#xff0c;还提供强大的高阶功能&#xff08;如模型、结构同步、协同合作、数据迁移等&#xff09;&#xff0c;这…
阅读更多...
基于element-ui后台模板，日常唠嗑

基于element-ui后台模板，日常唠嗑

后面会补充github地址 文章目录 目录 文章目录 案例说明 1.引入库 2.创建布局组件 3.创建布局组件 4.菜单效果展示 5.创建顶部组件 5.创建顶部面包屑组件 6.创建内容区域组件 7.效果总览 7.布丁&#xff08;实现一些小细节&#xff09; 前言一、pandas是什么&#xff1f;二、使…
阅读更多...
Android Studio记录一个错误：Execution failed for task ‘:app:lintVitalRelease‘.

Android Studio记录一个错误：Execution failed for task ‘:app:lintVitalRelease‘.

Android出现Execution failed for task :app:lintVitalRelease.> Lint found fatal errors while assembling a release target. Execution failed for task :app:lintVitalRelease解决方法 Execution failed for task ‘:app:lintVitalRelease’ build project 可以正常执…
阅读更多...
计算机网络之网络层

计算机网络之网络层

一、概述 主要任务是实现网络互连&#xff0c;进而实现数据包在各网络之间的传输 1.1网络引入的目的 从7层结构上看&#xff0c;网络层下是数据链路层 从4层结构上看&#xff0c;网络层下面是网络接口层 至少我们看到的网络层下面是以太网 以太网解决了什么问题&#xff1f; 答…
阅读更多...
python中一个文件（A.py）怎么调用另一个文件（B.py）中定义的类AA详解和示例

python中一个文件（A.py）怎么调用另一个文件（B.py）中定义的类AA详解和示例

本文主要讲解python文件中怎么调用另外一个py文件中定义的类&#xff0c;将通过代码和示例解读&#xff0c;帮助大家理解和使用。 目录 代码B.pyA.py 调用过程 代码 B.py 如在文件B.py,定义了类别Bottleneck&#xff0c;其包含卷积层、正则化和激活函数层&#xff0c;主要对…
阅读更多...
微信小程序实现【点击 滑动 评分 评星（5星）】功能

微信小程序实现【点击 滑动 评分 评星（5星）】功能

wxml文件&#xff1a; <view class"wxpl_xing"><view class"manyidu">{{scoreContent}}</view><view><block wx:for{{scoreArray}} wx:for-item"item"><view classstarLen bindtapchangeScore data-sy"{{…
阅读更多...
什么是LLC电路？

什么是LLC电路？

LLC电路是由2个电感和1个电容构成的谐振电路&#xff0c;故称之为LLC&#xff1b; LLC电路主要由三个元件组成&#xff1a;两个电感分别为变压器一次侧漏感(Lr)和励磁电感(Lm)&#xff0c;电容为变压器一次侧谐振电容(Cr)。这些元件构成了一个谐振回路&#xff0c;其中输入电感…
阅读更多...
程序员进阶高管指南，看懂工资最少加5k

程序员进阶高管指南，看懂工资最少加5k

从象牙塔毕业跨入社会大染缸&#xff0c;很多人都跟我谈过他们的职业困惑&#xff0c;其中有一些刚刚毕业&#xff0c;有些人已经工作超过10年。基本上是围绕着怎样持续提升&#xff0c;怎样晋升为高级管理者。那么这篇文章&#xff0c;我就来谈一谈程序员到高管的跃升之路。 …
阅读更多...
程序环境和预处理（详解版）

程序环境和预处理（详解版）

我们已经学到这里&#xff0c;这就是关于C语言的最后一个集中的知识点了&#xff0c;虽然它比较抽象&#xff0c;但是了解这部分知识&#xff0c;可以让我们对C代码有更深层次的理解&#xff0c;知道代码在每一个阶段发生什么样的变化。让我们开始学习吧! 目录 1.程序的翻译环…
阅读更多...
5个免费在线工具推荐

5个免费在线工具推荐

NSDT 三维场景建模工具GLTF/GLB在线编辑器Three.js AI自动纹理化开发包YOLO 虚幻合成数据生成器3D模型在线转换 1、NSDT 三维场景建模 访问地址&#xff1a;NSDT 编辑器 2、GLTF/GLB在线编辑器 访问地址&#xff1a;GLTF 编辑器 3、Three.js AI自动纹理化开发包 图一为原始模…
阅读更多...
C++类与对象(4)—日期类的实现

C++类与对象(4)—日期类的实现

目录 一、类的创建和方法声明 二 、输出&运算符重载 三、检查合法性 1、获取对应年月的天数 2、初始化 四、实现加等和加操作 1、先写再写 2、先写再写 3、两种方式对比 五、实现自增和--自减 1、自增 2、自减 六、 实现减等和减操作 1、减等天数 2、加负数…
阅读更多...
【数据结构/C++】线性表_双链表基本操作

【数据结构/C++】线性表_双链表基本操作

#include <iostream> using namespace std; typedef int ElemType; // 3. 双链表 typedef struct DNode {ElemType data;struct DNode *prior, *next; } DNode, *DLinkList; // 初始化带头结点 bool InitDNodeList(DLinkList &L) {L (DNode *)malloc(sizeof(DNode))…
阅读更多...
motionlayout的简单使用

motionlayout的简单使用

MotionLayout 什么是motionLayout&#xff1f; MotionLayout 是 Android 中的一个强大工具&#xff0c;用于创建复杂的布局动画和过渡效果。它是 ConstraintLayout 的一个子类&#xff0c;继承了 ConstraintLayout 的布局功能&#xff0c;同时添加了动画和过渡的支持。Motion…
阅读更多...
深度解析 Docker Registry：构建安全高效的私有镜像仓库

深度解析 Docker Registry：构建安全高效的私有镜像仓库

文章目录 什么是Docker Registry&#xff1f;Docker Hub vs. 私有RegistryDocker Hub&#xff1a;私有Registry&#xff1a; 如何构建私有Docker Registry&#xff1f;步骤一&#xff1a;安装Docker Registry步骤二&#xff1a;配置TLS&#xff08;可选&#xff09;步骤三&…
阅读更多...
Adobe xd有免费版可以使用吗？

Adobe xd有免费版可以使用吗？

Adobexd现在收费了吗&#xff1f;Adobexd是收费的。Adobexd在中国提供个人版和团队版两项收费政策。个人版每月订阅60元&#xff0c;每年订阅688元&#xff1b;团队版每月订阅112元/用户&#xff0c;每年订阅1288元/用户。 虽然AdobeXD的免费计划已经下线&#xff0c;但Adobe仍…
阅读更多...
最新文章

Copyright @ 2022~2023