从现在开始，开辟一个新的专题----算法，这篇文章介绍双指针，滑动窗口，二分查找这几种算法以及附有相应的练习题。
1.双指针
常见的双指针形式有两种，一种是对撞指针，一种是同向双指针。下面是三种对应情况
（1）对撞指针的两端指针向中间移动，结束条件一般是两边指针相遇，而对撞双指针通常是需要利用区间单调性决定移动左边还是右边。（问题1.4，1.5）
（2）同向双指针中的快慢指针（问题1.3）让两个指针以不同的速度移动，它不仅可以处理环形链表的问题，更是一种思想，解决循环往复的问题，这类问题可能结束条件不好判断，可以考虑快慢指针。
（3）同向双指针中以一个遍历指针，另一个指针在不同情况下指向不同的移动操作，也可以用于作为一个分割指针，使得该指针两边的元素性质不同。（问题1.1，1.2）
1.1 283. 移动零 - 力扣（LeetCode）
给定⼀个数组 nums ，编写⼀个函数将所有0移动到数组的末尾，同时保持⾮零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进⾏操作。
示例:
输⼊:nums = [0,1,0,3,12] 输出:[1,3,12,0,0]
思路：情况（3）的思路，一个分隔指针从数组-1的位置开始，它前面的位置均是非零元素，如果遍历指针指向元素是零，遍历指针++，分割指针不动，如果遍历指针指向元素是非0，分割指针++，交换两个指针指向的值，遍历指针++，当遍历到数组末尾时，循环结束。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// pivot 指向最后一个非0元素
int pivot=-1;
for(auto &x:nums)
{
if(x!=0)
{
//如果该元素是0
pivot++;
swap(x,nums[pivot]);
}
}
}
};1.2 1089. 复写零 - 力扣（LeetCode）
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
示例 1：
输入：arr = [1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4] 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
思路：这个题目要采取两个同向双指针去完成。
第一步要找到开始复写的位置，如示例中的4的位置，这个采取cur走一步，dest在cur为0时走两步，cur为非零元素时走一步的方式。
第二步就是处理边界情况，因为可能最后一个复写的元素是0，dest就超过了数组最大长度
第三步也是同向双指针，将cur位置的元素给dest位置的元素，如果是非0，之间赋值即可，如果是0则dest和dest-1的值全都赋值为0，同时dest向前走两步。
class Solution
{
public:
void duplicateZeros(vector<int>& arr)
{
// 1. 先找到最后⼀个数
int cur = 0, dest = -1, n = arr.size();
while(cur < n)
{
if(arr[cur]) dest++;
else dest += 2;
if(dest >= n - 1) break;
cur++;
}
// 2. 处理⼀下边界情况
if(dest == n)
{
arr[n - 1] = 0;
cur--; dest -=2;
}
// 3. 从后向前完成复写操作
while(cur >= 0)
{
if(arr[cur]) arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};1.3 202. 快乐数 - 力扣（LeetCode）
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
思路：使用快慢指针，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。我们把操作即为bitsum，执行该操作之后，数字变化一次，快指针一次执行两次操作，慢指针一次执行一次，它们必定会相遇，如果相遇位置slow或者fast的值是1 ，那么这个数⼀定是快乐数，否则就不是快乐数。
1.4 11. 盛最多水的容器 - 力扣（LeetCode）
思路1：暴力求解，思路：枚举出能构成的所有容器，找出其中容积最⼤的值。采取两个指针i，j分别指向容器左端和右端，j不懂，i依次向右移动到j-1的位置，求出每一次的容积，然后j到j-1的位置，然后i依次向右移动到j-2的位置，求出每一次的容积，取所有容积的最大值。（超时）
思路2：在暴力求解上优化，如果左边界高度小于右边界高度，只需要移动左边界即可，反之只需要移动右边界
class Solution {
public:
int maxArea(vector<int>& height) {
if(height.size()<=1)
{
return 0;
}
int left=0;
int right=height.size()-1;
vector<int> maxArray; //也可以不需要数组
while(left<right)
{
int w=right-left;
int h=min(height[left],height[right]);
int s=w*h;
maxArray.push_back(s);
if(height[left]<=height[right])
{
left++;
}
else
{
right--;
}
}
int ret=0;
for(int i=0;i<maxArray.size();i++)
{
if(maxArray[i]>ret)
{
ret=maxArray[i];
}
}
return ret;
}
};1.5 611. 有效三角形的个数 - 力扣（LeetCode）
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3
解法1：三层for循环枚举出所有的三元组，并且判断是否能构成三⻆形。虽然说是暴⼒求解，但是还是想优化⼀下，如果能构成三⻆形，需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。 因此我们可以先将原数组排序，然后从⼩到⼤枚举三元组，⼀⽅⾯省去枚举的数量，另⼀⽅⾯⽅便判断是否能构成三角形。 （超时）
解法2：排序+对撞双指针。固定最长边i，区间 [left, right] i位置左边的区间（也就是比它小的区)
如果nums[left] + nums[right] > nums[i] :说明 [left, right - 1] 区间上的所有元素均可与 nums[right] 构成比nums[i] ⼤的⼆元组，满⾜条件的有right - left 种，right--
如果nums[left] + nums[right] <= nums[i] ：说明left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件的⼆元组 left 位置的元素可以舍去，left++
class Solution {
public:
// 利用单调性，可以做双指针算法，指针可以指的是一个数字
int triangleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int count=0;
for(int i=0;i<nums.size();i++)
{
for(int j=i+1;j<nums.size();j++)
{
for(int k=j+1;k<nums.size();k++)
{
//如果可以构成三角形，count++；
if(nums[i]+nums[j]>nums[k])
{
count++;
}
}
}
}
return count;
}
};1.6 15. 三数之和 - 力扣（LeetCode）
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
思路1：暴力，三重for循环，i,j,k三个指针开始时分别指向0，1，2三个位置，然后往后遍历所有三元组，符合情况放到一个vector容器当中。
思路2：先排序，然后固定⼀个数a ，在这个数后⾯的区间内，使用对撞双指针算法快速找到两个数之和等于-a 即可。但是要注意的是，这道题⾥⾯需要有去重操作，找到⼀个结果之后， left 和right 指针要跳过重复的元素；当使⽤完⼀次双指针算法之后，固定的a 也要跳过重复的元素。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> ret;
for(int end=nums.size()-1;end>=2;end --)
{
int left=0;
int right=end -1;
while(left<right)
{
if(nums[left]+nums[right]+nums[end]==0)
{
vector<int> v; // 每次都会定义一遍
v.push_back(nums[left]);
v.push_back(nums[right]);
v.push_back(nums[end]);
ret.push_back({nums[left],nums[right],nums[end]});//用数组构造v，两种写法都可以
left++;
right--; //找到一个结果之后，继续循环找
//处理去重
while(left<right&&nums[left]==nums[left-1])
{
left++;
}
}
else if(nums[left]+nums[right]+nums[end]>0)
{
right--;
}
else
{
left++;
}
}
while(end>=2&&nums[end]==nums[end-1])
{
end--;
}
}
// vector<vector<int>> vec(ret);
// std::sort(vec.begin(), vec.end());unique()会把重复数据放在 容器末尾
// vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
//ret.earse(unique(ret.begin(),ret.end()),ret.end());
return ret;
}
};其中四数之和和两数之和与之类似。
18. 四数之和 - 力扣（LeetCode）四数之和思路依次固定⼀个数 a ，在这个数a 的后面区间上，在a+1位置固定数b，再利用两数之和获取两个指针，使这两个数的和等于target- a-b 即可。
2.滑动窗口
滑动窗口可以看成一个特殊的同向双指针，它主要用来处理连续子数组，连续字符串问题。其主要就是三步：进窗口，判断，出窗口，更新结果，更新结果可能在判断时更新，也可能在出窗口时候更新。
2.1 209. 长度最小的子数组 - 力扣（LeetCode）
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
思路：滑动窗口，right指针不断向后走直到最后一个元素，当sum>=target时，我们需要出窗口加更新结果，此时left指针不断向前走，同时ret为窗口长度的最小值。
2.2 3. 无重复字符的最长子串 - 力扣（LeetCode）
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"所以其长度为 3。
思路：hash表加滑动窗口，每个right指针指向的元素都进入窗口，然后hash表来判断进入窗口的元素是否与前面元素重复，如果重复，则一直将left指向元素出窗口直到窗口内无重复元素，最后更新结果。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ret=0;
int hash[128]={0};
for(int left,right=0;right<s.size();right++)
{
//进入窗口
hash[s[right]]++;
//出窗口
while(hash[s[right]]>1&&left<right)
{
hash[s[left]]--;
left++;
}
//更新结果
ret=max(ret,right-left+1);
}
return ret;
}
};2.3 1004. 最大连续1的个数 III - 力扣（LeetCode）
思路：该题维护一个合法窗口，使得里面0的数量小于k,我们可以使用一个变量zero统计窗口内0的数量，在窗口内只需要将其维护好即可。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int ret=0;
for(int left=0,right=0,zero=0;right<nums.size();right++)
{
//进窗口
if(nums[right]==0) zero++;
while(zero>k)
{
if(nums[left]==0) zero--;
left++;
}
ret=max(ret,right-left+1);
}
return ret;
}
};2.4 1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
示例 1：
输入：nums = [1,1,4,2,3], x = 5 输出：2 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
求一个连续窗口内值的和为target，其中target = sum(nums) - x 。如果target < 0 ，问题⽆解；初始化左右指针 l = 0 ,r = 0，r 指向元素进入窗口,记录当前滑动窗内数组元素和n，如果n>sum,则左边元素不断出窗口。如果n==target，则记录当前满足条件数组的最⼤区间⻓度maxLen = -1 。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum=0;
for(auto &e:nums)
{
sum+=e;
}
if(sum<x) return -1;
int ret=-1; //窗口长度
int target=sum-x;
for(int left=0,right=0,n=0 ;right<nums.size();right++)
{
//进窗口
n+=nums[right];
while(n>target)
{
n-=nums[left];
left++;
}
if(n==target)
ret= max(right-left+1,ret);
}
//进窗口 判断 出窗口
return ret==-1?-1:nums.size()-ret;
}
};2.4 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
因为字符串p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串s 中构造⼀个⻓度为与字符串p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；当窗⼝中每种字⺟的数量与字符串p 每种字⺟的数量相同时，则说明当前窗⼝为字符串 p的异位词。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int hash1[26]={0};
int hash2[26]={0};
for(int i=0;i<p.size();i++)
{
hash1[p[i]-'a']++;
}
for(int left=0,right=0,count=0;right<s.size();right++)
{
//进入窗口
hash2[s[right]-'a']++;
//维护count ，即有效字符的个数
if(hash2[s[right]-'a']<=hash1[s[right]-'a'])
{
count++;
}
//判断 什么时候left需要向右移动
if(right - left + 1 > p.size())
{
//进入的是无效字符,count--
if(hash2[s[left]-'a']<=hash1[s[left]-'a'])
{
count--;
}
hash2[s[left]-'a']--;
left++;
}
//判断条件是 count和大小相等，并没有考虑窗口的大小
if(count==p.size())
{
ret.push_back(left);
}
}
return ret;
}
};3.二分查找
它是O(logn)的算法，或者递增(非递减)序列，如果出现这样的字眼，考虑二分查找。
普通的二分查找，找一个值，while(left<=right)，大于小于两种情况下对应left和mid分别不同的移动，如果相等，则找到了，则返回该值即可。
边界查找：当某个元素的左边（或右边）严格满足某种性质时，可以用二分查找解决该题，结束条件是while(left<right)
二分查找左边界：mid取左值，同时判断情况是这个数小于target时，左边所有值全部排除
二分查找右边界：mid取右值，同时判断情况是这个数大于target时，右边所有值全部排除
3.1 704. 二分查找 - 力扣（LeetCode）
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入:nums= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 出现在nums中并且下标为 4
class Solution {
public:
int search(vector<int>& nums, int target) {
//暴力解法每次干掉一个数字
int ret=-1;
int left=0;
int right=nums.size()-1;
while(left<=right)
{
// 数组有二段性，摒除一个区间的数字
int mid=(left+right)/2;
if(nums[mid]<target)
{
left=mid+1;
}
else if(nums[mid]>target)
{
right=mid-1;
}
else
{
ret=mid;
break;
}
}
return ret;
}
};3.2 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0)
{
return {-1,-1};
}
int leftret=-1;
int rightret=-1;
int left=0;
int right=nums.size()-1;
//寻找左边界
while(left<right)
{
int mid=left+(right-left)/2; //当两个数时，取左边值
if(nums[mid]<target) // mid左边所有值全部排除，在[mid+1,right]找左边界
left=mid+1;
else
right=mid;
}
//此时left==mid等于左边界
if(nums[left]==target)
{
leftret=left;
}
right=nums.size()-1;
//寻找右边界
while(left<right)
{
int mid=left+(right-left+1)/2;
if(nums[mid]>target)
right=mid-1;
else
left=mid;
}
if(nums[right]==target)
{
rightret=right;
}
return {leftret,rightret};
}
};3.2 35. 搜索插入位置 - 力扣（LeetCode）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
思路：找到插入 目标值的左边界，如果左边界等于target，则返回左边界（左边所有值都是小于nums[left]），如果该值小于left，证明这个区间所有值都是小于target，它插入数组最后一个位置，返回left+1。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
//寻找左右边界，如果相等则返回
//右边界
int left=0;
int right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid] < target) left = mid + 1;
else
{
right=mid;
}
}
if(nums[left]<target)
{
return left+1;
}
return left;
}
};3.3 69. x 的平方根 - 力扣（LeetCode）
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
在一段区间内，分析左右两边元素的特征，假设index即为x的算术平方根则
▪ [0, index] 之间的元素，平⽅之后都是⼩于等于x 的；
▪ [index + 1, x] 之间的元素，平⽅之后都是⼤于 x 的。因此此题目选用找右边界的解法比较好，但是本人采用左边界做法，此时需要多加一层结果的判断。
class Solution {
public:
int mySqrt(int x) {
//一个数字，左边平方比它大，右边平方比他小
//找到左边界
if(x<1) return 0;
int left=1;
int right=x;
while(left<right)
{
long long mid=left+(right-left)/2;
if(mid*mid<x) left=mid+1;
else
right=mid;
}
if(x/left==left) return left; //多一层判断，如果x正好是整数平方根存在返回left
return left-1;
}
};3.4 852. 山脉数组的峰顶索引 - 力扣（LeetCode）
给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
输入：arr = [0,1,0] 输出：1
思路：找左边界即可。如果 mid位置呈现上升趋势，即arr[mid] > arr[mid - 1]，说明我们接下来要在 [mid + 1, right] 区间继续搜索；
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
//采取寻找左边界的方式
int left=1;
int right=arr.size()-2;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid]<arr[mid+1]) left=mid+1; //上升数据
else right=mid;
}
return left;
}
};3.5 LCR 173. 点名 - 力扣（LeetCode）
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例 1:
输入: records = [0,1,2,3,5] 输出: 4
思路：利用性质的两端性，在该元素左边，i和nums[i]严格相等，因此可以采用寻找左边边界的方法求解。
class Solution {
public:
int takeAttendance(vector<int>& records) {
int left=0;
int right=records.size();
while(left<right)
{
int mid=left+(right-left)/2;
if(mid==records[mid]) //该元素左边严格满足mid=nums[mid]
left=mid+1;
else
right=mid;
}
return left;
// 暴力解法
// int i=0;
// for(i=0;i<records.size();i++)
// {
// if(i!=records[i])
// {
// return i;
// }
// }
// return i;
}
};本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » 算法(C++实现)
发表评论 取消回复