【C++算法】双指针

简介: 【C++算法】双指针

移动零

  • 算法原理

这类题是属于数组划分、数组分开题型

  • 代码步骤:
  1. 使用cur遍历数组
  2. 当cur所指的元素等于0时,cur向后面移动
  3. 当cur所指的元素不等于0时,dest向后面移动,cur所指元素与dest移动后所指的元素交换
  4. 当cur指向最后一个元素的下一个时,结束。
  • 代码展示
class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        int dest = -1;
        for(int cur = 0; cur < nums.size(); ++cur)
        {
            //如果cur所指的元素非0,交换
            if(nums[cur] != 0)
            {
                swap(nums[++dest], nums[cur]);
            }
        }
    }
};

复写零

题目链接:

  • 算法原理

  • 代码步骤:

  • 代码展示
class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        //寻找复写的最后一个元素
        int cur = 0;
        int dest = -1;
        int n = arr.size();
        //注意arr.sizr()是size_t无符号类型
        //int(-1)比size_t整数大
        while(cur < n)
        {
            if(arr[cur])
            {
                ++dest;
            }
            else
            {
                dest += 2;
            }
            //注意这个判断条件需要在里面实现
            //如果在整个循环结束判断,cur的值无法保证
            if(dest >= n-1) break;
            cur++;
        }
        //特殊情况处理
        if(dest == n)
        {
            arr[n - 1] = 0;
            --cur;
            dest -= 2;
        }
        //进行从右向左的复写操作
        for(; cur >= 0; --cur)
        {
            if(arr[cur])
            {
                arr[dest--] = arr[cur];
            }
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
        }  
    }
};

快乐数

题目链接:

  • 算法原理

  • 代码步骤:

采用快慢双指针的思想:

  1. 定义快慢双指针
  2. 设置一个每个位置平方和的函数
  3. 慢指针每次向后移动一步
  4. 快指针每次向后移动俩步
  5. 判断快慢指针相遇的时候的值是否为1即可
  • 代码展示
class Solution {
public:
    //计算数每个位置上数字的平方和
    int SquareSum(int n)
    {
        int sum =0;
        while(n > 0)
        {
            int num = n % 10;
            sum += num * num;
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) 
    {
        int slow = n;
        int fast = SquareSum(n);
        while(slow != fast)
        {
            fast = SquareSum(SquareSum(fast));
            slow = SquareSum(slow);
        }
        if(slow == 1)
        {
            return true;
        }
        else 
        {
            return false;
        }
    }
};

盛最多水的容器

题目链接:

  • 算法原理

  • 代码步骤:
  1. 记录初始w最大时的初始容积
  2. left与right二者中较小者向里面移动,寻找比自己大的值
  3. 找到比自己大的值,记录面积,并与之前的面积比较大小
  4. 当left与right相遇的时候,结束
  • 代码展示
class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0;
        int right = height.size() - 1;
        //寻找边界的最小值
        int min = (height[left] < height[right]) 
        ? height[left] 
        : height[right];
        //起始容积
        int vmax = min * (right - left);
        while(left < right)
        {
            if(height[left] < height[right])
            {
                //记录此时的left
                int num = left;
                while(left < right)
                {
                    //比较看是否有比height[left]大的值
                    ++left;
                    if(height[num] < height[left])
                    {
                        break;
                    }
                }
            }
            else
            {
                //记录此时的left
                int num = right;
                while(left < right)
                {
                    //比较看是否有比height[left]大的值
                    --right;
                    if(height[num] < height[right])
                    {
                        break;
                    }
                }
            }
            min = (height[left] < height[right]) 
            ? height[left] 
            : height[right];
            int v = min * (right - left);
            vmax = (v > vmax) ? v : vmax; 
        }
        return vmax;
    }
};
class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0, right = height.size() - 1, vmax = 0;
        while(left < right)
        {
            int v = min(height[left], height[right]) * (right - left);
            vmax = max(vmax, v);
            if(height[left] < height[right]) ++left;
            else --right;
        }
        return vmax;
    }
};

有效三角形个数

题目链接:

  • 算法原理

  • 代码步骤:
  1. 对数组进行排序
  2. 设置三个指针,一个指向最大值,另外俩个形成单调双指针
  3. 当left + right < max时,个数为right-left,right--
  4. 当left + right >= max时,个数为0,left++
  • 代码展示
class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        int n = nums.size();
        //排序升序
        sort(nums.begin(), nums.end());
        int sum = 0;
        //最大值向前移动
        while(n >= 2)//确保right不越界
        {
            int max = nums[n - 1];
            int left = 0, right = n - 2;
            //利用单调性使用双指针
            while(left < right)
            {
                if(nums[left] + nums[right] > max)
                {
                    sum += (right - left);
                    right--;
                }
                else
                {
                    left++;
                }
            }
            --n;
        }
        return sum;
    }
};

三数之和

题目链接:

  • 算法原理

  • 代码步骤:
  1. 排序
  2. 固定一个数min(注意当min > 0的时候,也是可以直接结束的)
  3. 在该数的后面的区间之内,利用单调性使用双指针,快速找到俩个和等于-min的值
  4. 细节1:不漏数据
  5. 细节2:去重操作
  • 代码展示
class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> vv;
        //排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        //固定一个数
        int min = 0;
        for(int min = 0; min < n - 2; ++min)
        {
            //优化
            if(nums[min] > 0) break;
            int left = min + 1, right = n - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] < -nums[min])
                {
                    left++;
                }
                else if(nums[left] + nums[right] > -nums[min])
                {
                    right--;
                }
                else
                {
                    //添加数据
                    vv.push_back({nums[min], nums[left], nums[right]});
                    while(left < right && nums[left] == nums[left + 1])
                    {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right - 1])
                    {
                        right--;
                    }
                    if(left < right)
                    {
                        left++;
                        right--;
                    }
                }
            }
            while(min < n - 2 && nums[min] == nums[min + 1])
            {
                min++;
            }
        }
        return vv;
    }
};

四数之和

题目链接:

  • 算法原理

  • 代码步骤:

  • 代码展示
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> ret;
        //排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        //四数之和
        for(int minA = 0; minA < n;)
        {
            long targetA = target - nums[minA];
            //三数之和
            for(int minB = minA + 1; minB < n;)
            {
                long targetB = targetA - nums[minB];
                int left = minB + 1, right = n - 1;
                while(left < right)
                {
                    //利用单调性使用双指针
                    if(nums[left] + nums[right] < targetB)
                    {
                        left++;
                    }
                    else if(nums[left] + nums[right] > targetB)
                    {
                        right--;
                    }
                    else
                    {
                        ret.push_back({nums[minA], nums[minB], nums[left], nums[right]});
                        //left不重
                        while(left + 1 < right && nums[left] == nums[left + 1])
                        {
                            left++;
                        }
                        //right不重
                        while(left < right - 1 && nums[right] == nums[right - 1])
                        {
                            right--;
                        }
                        //不漏
                        if(left < right)
                        {
                            left++;
                            right--;
                        }
                    }
                }
                //minB不重
                while(minB + 1 < n && nums[minB] == nums[minB + 1])
                {
                    minB++;
                }
                ++minB;
            }
            //minA不重
            while(minA + 1 < n && nums[minA] == nums[minA + 1])
            {
                minA++;
            }
            ++minA;
        }
            return ret;
    }
};  


相关文章
|
1月前
|
缓存 安全 编译器
C++面试周刊(3):面试不慌,这样回答指针与引用,青铜秒变王者
《C++面试冲刺周刊》第三期聚焦指针与引用的区别,从青铜到王者级别面试回答解析,助你21天系统备战,直击高频考点,提升实战能力,轻松应对大厂C++面试。
201 79
C++面试周刊(3):面试不慌,这样回答指针与引用,青铜秒变王者
|
4月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
104 2
|
5月前
|
存储 算法 C++
Windows共享文件:探秘C++实现的B树索引算法奇境
在数字化时代,Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性,在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用,通过C++实现具体代码,展示其构建文件索引、优化数据存储的能力,提升文件检索效率。B树通过减少磁盘I/O操作,确保查询高效,为企业和个人提供流畅的文件共享体验。
|
1月前
|
存储 C++
C++语言中指针变量int和取值操作ptr详细说明。
总结起来,在 C++ 中正确理解和运用 int 类型地址及其相关取值、设定等操纵至关重要且基础性强:定义 int 类型 pointer 需加星号;初始化 pointer 需配合 & 取址;读写 pointer 执向之处需配合 * 解引用操纵进行。
155 12
|
6月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
174 15
|
6月前
|
运维 监控 算法
解读 C++ 助力的局域网监控电脑网络连接算法
本文探讨了使用C++语言实现局域网监控电脑中网络连接监控的算法。通过将局域网的拓扑结构建模为图(Graph)数据结构,每台电脑作为顶点,网络连接作为边,可高效管理与监控动态变化的网络连接。文章展示了基于深度优先搜索(DFS)的连通性检测算法,用于判断两节点间是否存在路径,助力故障排查与流量优化。C++的高效性能结合图算法,为保障网络秩序与信息安全提供了坚实基础,未来可进一步优化以应对无线网络等新挑战。
|
6月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
81 0
|
3月前
|
存储 机器学习/深度学习 算法
基于 C++ 的局域网访问控制列表(ACL)实现及局域网限制上网软件算法研究
本文探讨局域网限制上网软件中访问控制列表(ACL)的应用,分析其通过规则匹配管理网络资源访问的核心机制。基于C++实现ACL算法原型,展示其灵活性与安全性。文中强调ACL在企业与教育场景下的重要作用,并提出性能优化及结合机器学习等未来研究方向。
98 4
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
141 17

热门文章

最新文章