东莞网站制作功能,临沂企业建站效果好,wordpress 免签约支付,手机上网网站建设目录
介绍#xff1a;
问题1#xff1a;双指针 剑指offer57 和为S的两个数字。
问题2#xff1a;剑指Offer 21. 调整数组顺序使奇数位于偶数前面
问题3#xff1a;连续奇数子串#xff08;笔试遇到的真题#xff09;
问题4#xff1a;滑动窗口的最大值 介绍#…目录
介绍
问题1双指针 剑指offer57 和为S的两个数字。
问题2剑指Offer 21. 调整数组顺序使奇数位于偶数前面
问题3连续奇数子串笔试遇到的真题
问题4滑动窗口的最大值 介绍
双指针的问题通常需要理解问题的核心然后选择合适的双指针策略来解决问题。以下是一种通用的解决方法
首先对数组进行排序这样相同的元素会在一起并且可以更好地控制数组的遍历。定义两个指针一个快指针和一个慢指针。通常快指针是慢指针的两倍速度。从数组的两侧开始遍历比较两个指针指向的元素之和与目标值的大小。根据和的大小调整指针的位置例如如果和等于目标值则将两个指针都向后移动一位。如果和小于目标值则慢指针向后移动一位快指针向前移动两位。如果和大于目标值则慢指针向前移动一位快指针向后移动两位。当快指针和慢指针相遇时就找到了解。
这种解决方案适用于很多问题但是具体实现需要根据问题的具体要求进行调整。
问题1双指针 剑指offer57 和为S的两个数字。
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/?envTypestudy-plan-v2envIdcoding-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:vectorint twoSum(vectorint nums, int target){vectorint 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/?envTypestudy-plan-v2envIdcoding-interviews。
输入nums [1,2,3,4]
输出[1,3,2,4]
注[3,1,2,4] 也是正确的答案之一
class Solution11 {
public:vectorint exchange(vectorint nums) {int left0;int right0;while(rightnums.size()){if(nums[right]%2!0){swap(nums[left],nums[right]);}else{right;}}return nums;}};
问题3连续奇数子串笔试遇到的真题
若有一组最小值大于0数目大于1的连续的奇数的和等于指定正整5数
字那么此连续的奇数序列称为此正整数数字的一个奇序列。如数字12总共能找出一个奇序列 (57)数字16 能找出两个奇序列 (135,7)和(79)
数字17 找不出那么12的奇序列数为116的奇序列数为217的奇序列数为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请找出所有滑动窗口里的最大值。
示例:
输入: 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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {int nnums.size();priority_queuepairint,int q;for(int i0;ik;i){q.emplace(nums[i],i);}vectorint ans{q.top().first};for(int ik;in;i){q.emplace(nums[i],i);//离开了滑动窗口里面了永久移除了while(q.top().secondi-k){q.pop();}ans.push_back(q.top().first);}return ans;}}; 待补充
