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

014枚举之指针尺取——算法备赛

news 来源：原创 2025/8/22 15:52:46

枚举是数据结构与算法中基本的操作，常用于解决序列的区间问题。算法界将"双指针"视为其重要分支，类似地当然还有"三指针"，“四指针”，最常见的还是“双指针”，我认为它们应统称为“指针尺取”。
双指针无疑就是定义两个变量记录内存空间位置（一般为线性数组下标）来进行枚举，常见的枚举策略有“反向扫描”，“同向扫描”。

反向扫描，两指针的枚举方向不同，又可分为“两端向中间收缩”，“中间向两边扩散”等。
正向扫描，两指针的枚举方向相同，起始位置或速度不同,常见的策略有“定右统左”。

定右统左

定右统左是双指针中的常用策略，即固定右端点，统计左端点，常用于区间统计。

子串简写

问题描述

规定长度大于等于k的字符串可以采用 用数值（中间字符数量）代替中间字符保留首尾字符的简写方法。

如k=4 “abjdjda” 可简写为 “a5a”

给定 k,字符串S，首尾字符c1，c2，问S有多少个首尾字符分别为c1,c2的子串可采用上述简写方法.

原题链接

思路分析

采用双指针(前指针i(初始为k-1)，后指针j(初始为0)) 遍历子串长度为k的首尾字符，当j遍历到首字符为c1时，c1_sum++,c1_sum为一个统计数值，表示长度等于k且首字符为c1的子串个数（长度大于等于k且首字符为c1的左边界个数）。每次统计后，i++，j++，保证了两指针始终相距k。

前项指针i遍历到尾字符为c2时，sum+=cl_sum, 表示i位置为右边界，后面跟有c1_sum个左边界符合条件。

以后前项指针i每次遍历到c2时，子串长度会更长，前面统计的左边界肯定都符合条件，直接加cl_sum即可。

代码

#include <bits/stdc++.h> 
using namespace std;
int K;
long long ans=0,c1_sum=0;
string S;
char c1,c2;
int main(){cin>>K>>S>>c1>>c2;for(int i=K-1,j=0;i<S.size();i++,j++){if(S[j]==c1) c1_sum++;if(S[i]==c2) ans+=c1_sum;}cout<<ans;return 0;
}

每种字符至少取k个

问题描述

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1 。

原题链接

思路分析

求最少分钟数就是求最少操作数，也就是最少取走的字符数。

由于每次只能取两侧的字符，最后保留的就是一个连续的子串。要使取走的字符数最少，相当于求最后满足条件的最长的子串。

遍历r，寻找满足条件的最小的l。

代码

int takeCharacters(string s, int k) {if(k==0)return 0;int n=s.size();int num[3]={0};for(int i=0;i<n;i++){++num[s[i]-'a'];  //频数统计，全部取走}if(num[0]<k||num[1]<k||num[2]<k) return -1;int l=-1;int maxL=0;  //求r，l的最大距离for(int r=0;r<n;r++){num[s[r]-'a']--;  //放回//求最小的满足条件的l，当r加一时，小于l的左边界肯定不符和条件，所以l不用从0开始重新遍历.//此法相当于两次遍历s，时间复杂度为O(n)while(l<r&&(num[0]<k||num[1]<k||num[2]<k)){l++;  num[s[l]-'a']++;  //取走}maxL=max(maxL,r-l);}return n-maxL;
}

统计定界子数组的数目

问题描述

给你一个整数数组 nums 和两个整数 minK 以及 maxK 。

nums 的定界子数组是满足下述条件的一个子数组：

子数组中的 最小值 等于 minK 。
子数组中的 最大值 等于 maxK 。

返回定界子数组的数目。

子数组是数组中的一个连续部分。

原题链接

思路分析

首先考虑一个简单的情况，nums 的所有元素都在 [minK,maxK] 范围内。

在这种情况下，问题相当于：

同时包含 minK 和 maxK 的子数组的个数。
核心思路：枚举子数组的右端点i，统计有多少个合法的左端点。

遍历 nums，记录 minK 离 i 最近的位置 minI，以及 maxK 离 i 最近的位置 maxI，当遍历到 nums[i] 时，如果 minK 和 maxK 都遇到过，则左端点在 [0,min(minI,maxI)]范围中的子数组，包含 minK 和 maxK，最小值一定是 minK，最大值一定是 maxK。

以 i 为右端点的合法子数组的个数为：min(minI,maxI)+1

回到原问题，由于子数组不能包含在 [minK,maxK] 范围之外的元素，我们需要额外记录在 [minK,maxK] 范围之外的离 i 最近的位置，记作 i0，则左端点在 [i0+1,min(minI,maxI)] 中的子数组都是合法的。

以 i 为右端点的合法子数组的个数为min(minI,maxI)−i0

代码

long long countSubarrays(vector<int>& nums, int minK, int maxK) {long long ans = 0;int min_i = -1, max_i = -1, i0 = -1;for (int i = 0; i < nums.size(); i++) {int x = nums[i];if (x == minK) {min_i = i; // 最近的 minK 位置}if (x == maxK) {max_i = i; // 最近的 maxK 位置}if (x < minK || x > maxK) {i0 = i; // 子数组不能包含 nums[i0]}ans += max(min(min_i, max_i) - i0, 0);  //若i0大于min(min_i, max_i)，则取不到合法子数组}return ans;
}
作者：灵茶山艾府

最高频元素的频数

问题描述

元素的频数是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

原题链接

思路分析

首先直接一点思考，枚举每个数作为最高频的那个数x，看看通过最多k次操作最多能有多少个数变成x，更新最大频数ans，最后的ans就是答案。因为操作是对选取的数加1，所以只需考虑操作比x小的数，选取的数应该小于x且尽量大，这样便可以尽可能操作更多的数。

对于以上分析，我们可以先对数组按升序排序，从左到右遍历，选取当前枚举数为最高频的数，再从当前数开始向左反向遍历确定操作后的最大频数，最后维护更新的ans就是答案。

代码

int maxFrequency(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int ans=1,n=nums.size();long long sum=0;int j=0;for(int i=1;i<n;i++){int t=k;for(int j=i-1;j>=0;j--){t-=nums[i]-nums[j];if(t>=0) ans=max(ans,i-j+1);else break;}}return ans;}

上述代码两次循环，最大复杂度还是来到了O(n^2)，数据规模大，最后超时了，需要优化.

上述代码中，每次枚举一个nums[i]都向左遍历，其实要计算以当前nums[i]为k的ans值，可以借助前一个计算的结果。

定义j指针为前一个nums[i]往左遍历的截止点，求nums[i+1]对应的j指针时，因为nums[i+1]大于等于nums[i],其对应的j指针不可能更小，只会更大(请读者自行分析)，因此只需在原有的j指针上往右移动即可。算法相当于对数组最多两次遍历，时间复杂度为O(n)。

代码

int maxFrequency(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int ans=1,n=nums.size();long long sum=0;int j=0;for(int i=1;i<n;i++){sum+=(long long)(nums[i]-nums[i-1])*(i-j);while(sum>k){sum-=nums[i]-nums[j];j++;}ans=max(i-j+1,ans);}return ans;}

两端向中间收缩

接雨水

接雨水问题可以称的上指针尺取法中反向扫描的经典例题

问题描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

例图

在这里插入图片描述

原题链接

思路分析

定义左右指针l，r，初始l=0，r=height.size()-1;

每次判断height[l]<height[r]则 l++，否则 r++，直到l==r;

当height[l]<height[r]时可以确定 l从左到右遍历过程中子数组[0,l]的最大值lmax<height[r]

此时对于下标l处表示的雨水量是 lmax(子数组[0,l]的最大值)-height[l]。

反之当height[l]>=height[r]时可以确定 r从右到左遍历过程中子数组[r,n-1]的最大值rmax<=height[l]

此时对于下标r处表示的雨水量是 rmax(子数组[r,n-1]的最大值)-height[r]。

代码

int trap(vector<int>& height) {int ans=0;int l=0,r=height.size()-1;int lmax=0,rmax=0;while(l<r){lmax=max(height[l],lmax);rmax=max(height[r],rmax);if(height[l]<height[r]){ans+=lmax-height[l];l++;}else{ans+=rmax-height[r];r--;}}return ans;}

中间向两端扩散

包含k下标元素的子数组的最大容量

问题描述

给你一个整数数组 nums **（下标从 0 开始）**和一个整数 k 。

一个子数组 (i, j) 的容量定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。

请你返回子数组（i，j）(i<=k<=j) 的最大可能容量。

1 <= nums.length <= 10^5
1 <= nums[i] <= 2 * 10^4
0 <= k < nums.length

原题链接

思路分析

由于子数组必须包含nums[k],可以定义两个指针left,right，初始时left=k-1，right=k+1，ans=k;

所有目标子数组中最大的min值为nums[k],最小的min值为数组nums的最小值，

从[1,nums[k]]范围中每次枚举最小值i,初始枚举nums[i],然后依次减1；

向左移动left，直到nums[left]<i或left<0

向右移动right，直到nums[right]<i或ritgh>=n(n为nums数组大小)

此时的子数组[left+1，right-1]是最小值为i的最长目标子数组，记录其容量（right-left-1)*i，用它更新历史最大容量。

当i继续减少，而指针没有移动时，此时（right-left-1)不变，i减少，ans=（right-left-1)*i比上阶段所求更小，所以历史最大容量不会改变。

直到枚举到left<0且ritgh>=n，此时的历史最大容量值即为正确答案。

时间复杂度O(n+C),C为nums中元素的取值范围。

代码

class Solution {
public:int maximumScore(vector<int>& nums, int k) {int n = nums.size();int left = k - 1, right = k + 1;int ans = 0;for (int i = nums[k];; --i) {while (left >= 0 && nums[left] >= i) {--left;}while (right < n && nums[right] >= i) {++right;}ans = max(ans, (right - left - 1) * i);if (left == -1 && right == n) {break;}}return ans;}
};

优化

上述代码效率较低的原因是在 i 比 (left,right) 中的最小值更小，但指针没有移动时，计算出的分数是没有意义的。

指针没有移动的原因是 nums[left] 和 nums[right] 都小于 i。

此时我们应当直接把 i 减小至二者的较大值，而不是每次减少 1，这样就可以保证每一次循环中都至少会移动一次指针，就可以将 C 从时间复杂度中移除，总时间复杂度为O(n)

细节

在减少 i 时，需要注意指针已经超出数组边界的情况。

代码

int maximumScore(vector<int>& nums, int k) {int n = nums.size();int left = k - 1, right = k + 1;int ans = 0;for (int i = nums[k];;) {while (left >= 0 && nums[left] >= i) {--left;}while (right < n && nums[right] >= i) {++right;}ans = max(ans, (right - left - 1) * i);if (left == -1 && right == n) {break;}i = max((left == -1 ? -1 : nums[left]), (right == n ? -1 : nums[right]));}return ans;}

指向不同容器的指针尺取

寻找右区间

问题描述

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都不同。

区间 i 的 右侧区间 是满足 startj >= endi，且 startj 最小的区间 j。注意 i 可能等于 j 。

返回一个由每个区间 i 对应的 右侧区间 下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

原题链接

代码

vector<int> findRightInterval(vector<vector<int>>& intervals) {vector<pair<int, int>> start;  //将intervals拆分为两个数组vector<pair<int, int>> end;int n = intervals.size();for(int i=0; i<n; i++){start.emplace_back(intervals[i][0], i);end.emplace_back(intervals[i][1], i);}sort(start.begin(), start.end());sort(end.begin(), end.end());vector<int> res(n, -1);auto e_iter = end.begin(), s_iter = start.begin();  //两个指针while(e_iter != end.end()){while(s_iter != start.end() && s_iter->first < e_iter->first){s_iter++;}if(s_iter == start.end()) break;res[e_iter->second] = s_iter->second;e_iter++;}return res;}

多指针

统计好三元组的数目

问题描述

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c

其中 |x| 表示 x 的绝对值。

返回 好三元组的数量 。

原题链接

代码

int countGoodTriplets(vector<int>& arr, int a, int b, int c) {int n=arr.size(),ans=0;vector<int>ids(n);ranges::iota(ids,0);ranges::sort(ids,{},[&](int i){return arr[i];});for(int j:ids){vector<int>left,right;for(int i:ids){if(i<j&&abs(arr[i]-arr[j])<=a) left.push_back(arr[i]);}for(int k:ids){if(k>j&&abs(arr[k]-arr[j])<=b) right.push_back(arr[k]);}int s1=0,s2=0;for(int value:left){while(s2<right.size()&&right[s2]-value<=c) s2++;while(s1<right.size()&&right[s1]-value<-c) s1++;ans+=s2-s1;}}return ans;
}

014枚举之指针尺取——算法备赛

枚举是数据结构与算法中基本的操作，常用于解决序列的区间问题。算法界将"双指针"视为其重要分支，类似地当然还有"三指针"，“四指针”，最常见的还是“双指针”，我认为它们应统称为“指针尺取”。双…...

编程日记 2025/8/22 15:52:46

Python小酷库系列：bidict，可以双向查询的dict

bidict，可以双向查询的dict 基本使用创建双向字典正向查找（key → value）反向查找（value → key）添加新项删除项进阶功能使用 ~ （.inverse）获取逆映射使用 namedbidict 创建具名双向字典批量更…...

编程日记 2025/8/19 14:13:25

Android Compose 中 CompositionLocal 的全面解析与最佳实践

CompositionLocal 在 Android Compose 中的详细总结核心概念 CompositionLocal 是 Jetpack Compose 提供的一种隐式数据传递机制，允许数据在组件树中向下传递，而无需显式地通过每个 Composable 函数的参数传递。两种创建方式 1. staticComposition…...

编程日记 2025/8/21 19:54:53

Qt开发：容器组控件的介绍和使用

文章目录一、Group Box（分组框）1.1 QGroupBox 简介1.2 基本用法1.3 设置为可勾选（可启用/禁用子控件）1.4 信号与槽连接（监控勾选状态）1.5 布局示例（完整） 二、Scroll Area&#xff…...

编程日记 2025/8/20 4:20:58

JS逆向入门案例1——集思录登录

JS逆向入门案例1——集思录登录前言声明网站流程分析总结前言由于这段时间本职工作比较繁忙，没有很多空余的时间去研究各大厂的加密风控了，想起来自己刚接触js逆向走过坎坷，所以决定出一期js入门案例分析，为刚接触js逆向的小伙…...

编程日记 2025/8/20 4:20:56

ARM子程序和栈

微处理器中的栈由栈指针指向存储器中的栈顶来实现，当数据项入栈时，栈指针向上移动，当数据项出栈时，栈指针向下移动。实现栈时需要做出两个决定：一是当数据项进栈时是向低位地址方向向上生长（图a和图b&a…...

编程日记 2025/8/20 4:20:54

笔试专题（十五）

文章目录排序子序列题解代码消减整数题解代码最长公共子序列(二)题解代码排序子序列题目链接题解 1. 贪心模拟 2. 1 2 3 2 2 应该是有两个排列子序列的，所以i n-1时ret 3. 把水平的位置和上升部分，水平位置和下降部分分为一个排列子序列代…...

编程日记 2025/8/19 10:46:52

使用OpenCV 和 Dlib 进行卷积神经网络人脸检测

文章目录引言1.准备工作2.代码解析2.1 导入必要的库2.2 加载CNN人脸检测模型2.3 加载并预处理图像2.4 进行人脸检测2.5 绘制检测结果2.6 显示结果 3.完整代码4.性能考虑5.总结引言人脸检测是计算机视觉中最基础也最重要的任务之一。今天我将分享如何使用dlib库中的CNN人脸检…...

编程日记 2025/8/20 4:20:50

某信服EDR3.5.30.ISO安装测试（一）

一、前言 1.某信服EDR3.5.30 以下简称“EDR3.5”，即统一端点安全管理系统aES(终端检测响应EDR)， 官网最新版：aES6.0.1R2，可下载的最低版本：EDR3.7.11R3， 下载地址：统一端点安全管理系统aES-…...

编程日记 2025/8/20 4:20:48

Dify 快速构建和部署基于LLM的应用程序

本文先对Dify做一个初步的认识，然后以一个实际的简单金融问答案例，配置chatflow 工作流。一、Dify简介如果你是第一次接触Dify，可以先创建一个简单的聊天助手，初步感觉一下，Dify在构建聊天问答类应用的过程。比如…...

编程日记 2025/8/19 10:40:54

精益数据分析（40/126）：移动应用商业模式的关键指标与盈利策略

精益数据分析（40/126）：移动应用商业模式的关键指标与盈利策略在创业和数据分析的探索之路上，我们持续挖掘不同商业模式的内在规律，以寻求更好的发展机遇。今天，我们依旧秉持共同进步的理念，深…...

编程日记 2025/8/20 2:52:58

JavaScript 实现输入框的撤销功能

在 Web 开发中，为输入框添加撤销功能可以极大地提升用户体验，方便用户快速回滚到之前的输入状态。本文将通过一段简单的 HTML、CSS 和 JavaScript 代码，详细介绍如何实现输入框的撤销功能。整体实现思路利用 JavaScript 监听输入框的inpu…...

编程日记 2025/8/20 4:20:43

【C++】类和对象(一)

前言类和对象第一部分知识包括定义访问限定符类域实例化this指针本人其他文章：恋风诗文章中的源码[gitte]：mozhengy 类和对象（一） 前言1. 类的定义引例1.1 类定义格式1.2 类的访问限定符1.3 类域 2. 实例化2.1 实例化概念2.2 …...

编程日记 2025/8/21 10:27:21

【Vue】Vue3源码解析与实现原理

个人主页：Guiat 归属专栏：Vue 文章目录 1. Vue 3 架构概览1.1 模块化设计1.2 整体流程 2. 响应式系统2.1 响应式原理2.2 ref 和 reactive2.3 依赖收集与触发更新 3. 渲染系统3.1 虚拟DOM设计3.2 渲染管线3.3 Patch算法与Diff优化 4. 组件系统4.1 组件创建…...

编程日记 2025/8/20 4:20:39

黑马点评day02(缓存)

2、商户查询缓存 2.1 什么是缓存? 前言:什么是缓存? 就像自行车,越野车的避震器举个例子:越野车,山地自行车,都拥有"避震器",防止车体加速后因惯性,在酷似"U"字母的地形上飞跃,硬着陆导致的损害,像个弹簧一样; 同样,实际开发中,系统也需要"避震…...

编程日记 2025/8/20 4:20:38

文章目录 1. 聚合函数1.1 COUNT() 函数1.2 SUM() 函数1.3 AVG() 函数1.4 MIN() 函数1.5 MAX() 函数 2. GROUP BY 子句2.1 使用 GROUP BY 进行数据分组2.2 结合聚合函数 3. HAVING 子句3.1 使用 HAVING 过滤分组数据3.2 HAVING 和 WHERE 的区别 4. 实践任务4.1 创建一个销售表4.…...

编程日记 2025/8/19 14:06:46

为React组件库引入自动化测试：从零到完善的实践之路

为什么我们需要测试？ 我们的ReactTypeScript业务组件库已经稳定运行了一段时间，主要承载各类UI展示组件，如卡片、通知等。项目初期，迫于紧张的开发周期，我们暂时搁置了自动化测试的引入。当时团队成员对组件逻辑了如指…...

编程日记 2025/8/19 14:57:01

数据结构——算法复杂度

一、数据结构定义数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构，如：线性表、树、图、哈希…...

编程日记 2025/8/20 4:20:32

Vue3响应式原理那些事

文章目录 1 响应式基础：Proxy 与 Reflect1.1 Proxy 代理拦截1.2 Reflect 确保 `this` 指向正确1.2.1 修正 `this` 指向问题1.2.2 统一的操作返回值1.3 与 Vue2 的对比2 依赖收集与触发机制2.1 全局依赖存储结构：WeakMap → Map → Set2.2 依赖收集触发时机2.3 依赖收集核心实…...

编程日记 2025/8/20 4:20:30

记9（Torch

目录 1、Troch 1、Troch 函数说明举例torch.tensor()torch.arange()创建张量创建一个标量：torch.tensor(42)创建一个一维张量：torch.tensor([1, 2, 3])创建一个二维张量：torch.tensor([[1, 2], [3, 4]])生成一维等差张量：语法&am…...

编程日记 2025/8/20 4:20:28

机器学习模型训练模块技术文档

一、模块结构概览 import numpy as np from sklearn.model_selection import cross_validate, learning_curve from sklearn.pipeline import make_pipeline from sklearn.svm import SVC from sklearn.neighbors import KNeighborsClassifier from sklearn.preprocessing imp…...

编程日记 2025/8/19 8:09:44

定右统左

子串简写

每种字符至少取k个

统计定界子数组的数目

最高频元素的频数

两端向中间收缩

接雨水

中间向两端扩散

包含k下标元素的子数组的最大容量

指向不同容器的指针尺取

寻找右区间

多指针

统计好三元组的数目

相关文章：