目录
介绍:
问题1:双指针 剑指offer57 和为S的两个数字。
问题2:剑指Offer 21. 调整数组顺序使奇数位于偶数前面
问题3:连续奇数子串(笔试遇到的真题)
问题4:滑动窗口的最大值
介绍:
双指针的问题通常需要理解问题的核心,然后选择合适的双指针策略来解决问题。以下是一种通用的解决方法:
- 首先,对数组进行排序,这样相同的元素会在一起,并且可以更好地控制数组的遍历。
- 定义两个指针,一个快指针和一个慢指针。通常,快指针是慢指针的两倍速度。
- 从数组的两侧开始遍历,比较两个指针指向的元素之和与目标值的大小。
- 根据和的大小调整指针的位置,例如,如果和等于目标值,则将两个指针都向后移动一位。如果和小于目标值,则慢指针向后移动一位,快指针向前移动两位。如果和大于目标值,则慢指针向前移动一位,快指针向后移动两位。
- 当快指针和慢指针相遇时,就找到了解。
这种解决方案适用于很多问题,但是具体实现需要根据问题的具体要求进行调整。
问题1:双指针 剑指offer57 和为S的两个数字。
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/?envType=study-plan-v2&envId=coding-interviews
tag:easy.
// 输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
示例 1:因为已经排序完成了,定义了两个指针.从两侧进行即可。
输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]
示例 2:
输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]
class Solution10
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
vector<int> ans;
int left = 0, right = nums.size() - 1;
while (left <= right)
{
if (nums[left] + nums[right] == target)
{
ans.push_back(nums[left]);
ans.push_back(nums[right]);
break;
}
else if (nums[left] + nums[right] > target)
{
right--;
}
else
{
left++;
}
}
return ans;
}
};
问题2:剑指Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。
https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/?envType=study-plan-v2&envId=coding-interviews。
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一
class Solution11 {
public:
vector<int> exchange(vector<int>& nums) {
int left=0;
int right=0;
while(right<nums.size()){
if(nums[right]%2!=0){
swap(nums[left++],nums[right++]);
}
else{
right++;
}
}
return nums;
}
};
问题3:连续奇数子串(笔试遇到的真题)
若有一组最小值大于0,数目大于1的连续的奇数的和等于指定正整5数
字,那么此连续的奇数序列称为此正整数数字的一个奇序列。如数字12,总共能找出一个奇序列 (5,7),数字16 能找出两个奇序列 (1,3,5,7)和(7,9)
数字17 找不出,那么12的奇序列数为1,16的奇序列数为2,17的奇序列数为0。
输入 17
输入 0
输入 16
输出 2
输入 12
输出 1
函数用于计算奇序列数 从1 开始 加到 n/2,计算累计和超过n进入while 循环. 如果等于就是+2, 否则就停止。
1 3 5 7 9 11
3 5 7 9
5 7 9 。。。小于n就可以了。
int main()
{
int n;
cin >> n;
int start = 0;
int count = 0;
int sum = 0;
int i = 0;
for (start = 1; start < n / 2; start += 2)
{
i = start;
sum = 0;
while (sum < n)
{
sum += i;
i += 2;
}
if (sum == n)
{
count++;
}
}
cout << count << endl;
system("pause");
return 0;
}
问题4:滑动窗口的最大值
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums
和滑动窗口的大小 k
,请找出所有滑动窗口里的最大值。
示例:文章来源:https://www.toymoban.com/news/detail-699469.html
输入: nums =[1,3,-1,-3,5,3,6,7]
, 和 k = 3 输出:[3,3,5,5,6,7] 解释:
滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n=nums.size();
priority_queue<pair<int,int>> q;
for(int i=0;i<k;i++){
q.emplace(nums[i],i);
}
vector<int> ans={q.top().first};
for(int i=k;i<n;i++){
q.emplace(nums[i],i);
//离开了滑动窗口里面了,永久移除了
while(q.top().second<=i-k){
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};
======================待补充===========================文章来源地址https://www.toymoban.com/news/detail-699469.html
到了这里,关于双指针的问题解法以及常见的leetcode例题。的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!