北京建设网站的公司哪家好,菠菜网站怎么做排名,3步打造seo推广方案,58同城代运营光是话不行#xff0c;要紧的是做。 ——鲁迅
目录 一.什么是双指针问题#xff1f;
二.最接近的三数之和
第一种暴力法#xff1a;
第二种双指针#xff1a;
三.移除元素
第一种暴力法#xff1a;
第二种双指针#xff1a;
四.盛最… 光是话不行要紧的是做。 ——鲁迅
目录 一.什么是双指针问题
二.最接近的三数之和
第一种暴力法
第二种双指针
三.移除元素
第一种暴力法
第二种双指针
四.盛最多水的容器 一.什么是双指针问题
双指针指的是在遍历对象的过程中不是普通的使用单个指针进行访问而是使用两个相同快慢指针或者相反方向对撞指针的指针进行扫描从而达到相应的目的。 换言之双指针法充分使用了数组有序这一特征从而在某些情况下能够简化一些运算。
第一种快慢指针
快慢指针也是双指针但是两个指针从同一侧开始遍历数组将这两个指针分别定义为快指针fast和慢指针slow两个指针以不同的策略移动直到两个指针的值相等或其他特殊条件为止如 fast 每次增长两个slow 每次增长一个。
第二种对撞指针
对撞指针是指在数组中将指向最左侧的索引定义为左指针(left)最右侧的定义为右指针(right)然后从两头向中间进行数组遍历。
对撞数组适用于连续数组和字符串也就是说当你遇到题目给定连续数组和字符床时应该第一时间想到用对撞指针解题。
二.最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1 输入nums [-1,2,1,-4], target 1 输出2 解释与 target 最接近的和是 2 (-1 2 1 2) 。 示例 2 输入nums [0,0,0], target 1 输出0 做题链接最接近的三数之和
第一种暴力法
求最接近的三数之和使用三个循环依次遍历整个数组枚举出所有的可能从而推算出最接近的但是此算法时间复杂度为O(N^3)。力扣上是运行不过的这里我们只是作为一个参考。
#includestdio.h
#includemath.h
int threeSumClosest(int* nums, int numsSize, int target)
{int i 0;int j 0;int k 0;int temp nums[0] nums[1] nums[2];for (i 0; i numsSize; i){for (j i 1; j numsSize; j){for (k j 1; k numsSize; k){int sum nums[i] nums[j] nums[k];if (abs(sum- target) abs(temp - target))//abs是绝对值的意思{//如果sum- target的绝对值更小说明sum更接近target的值temp sum;}}}}return temp;
}
int main()
{int nums[10] { 0 };int numsSize 0;int target 0;scanf(%d %d, numsSize, target);int i 0;for (i 0; i numsSize; i){scanf(%d, nums[i]);}int ret threeSumClosest(nums, numsSize, target);printf(%d, ret);return 0;
} 第二种双指针
此算法需要先把数组从小到大进行排序排好序之后。因为这里是三个数而双指针操作的是两个数这里我们就需要先定下一个数然后左指针指向定的下一个数右指针指向最右边的数。 int cmp_int(const void* a, const void* b)
{return *(int*)a - *(int*)b;
}
int threeSumClosest(int* nums, int numsSize, int target) {qsort(nums, numsSize, sizeof(int), cmp_int);//使用快排进行排序int best nums[0] nums[1] nums[2];for (int i 0; i numsSize; i){int left i 1;int right numsSize - 1;while (left right){int min nums[i] nums[left] nums[left 1];//先来算出最小值如果target比最小值还小后面代码就不用进行了直接breakif (target min){if (abs(min - target) abs(best - target)){best min;}break;}int max nums[i] nums[right] nums[right - 1];//如果target比最大值还大直接breakif (target max){if (abs(max - target) abs(best - target)){best max;}break;}int sum nums[i] nums[left] nums[right];if (sum target)//有可能会出现相等的情况相等了就直接返回{return target;}if (abs(sum - target) abs(best - target)){best sum;}if (sum target){right--;}else{left;}}}return best;
}
三.移除元素
给你一个数组 nums 和一个值 val你需要原地移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1 输入nums [3,2,2,3], val 3 输出2, nums [2,2] 解释函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums [2,2,3,3] 或 nums [2,2,0,0]也会被视作正确答案。 示例 2 输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3] 解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 做题链接移除元素
第一种暴力法
遍历数组如果在数组中找到了val则把数组后面的内容全部向前移动一位把val给覆盖掉依次类推直到把数组里面等于val的值全部给覆盖掉。
最坏的情况就是数组里面的值全是val则时间复杂度为O(N^2)。 int removeElement(int* nums, int numsSize, int val)
{int i 0;int j 0;int count 0;for (i 0; i numsSize; i){if (nums[i] val){for (j i; j numsSize-1; j){nums[j] nums[j 1];}i--;//使下一次判断时回到上次判断的位置numsSize--;//进入一次if语句则数组的大小就会减少一个}}return numsSize;
}
int main()
{int nums[10] { 0 };int numsSize 0;int val 0;scanf(%d %d, numsSize, val);int i 0;for (i 0; i numsSize; i){scanf(%d, nums[i]);}int ret removeElement(nums, numsSize,val);int j 0;for (j 0; j ret; j){printf(%d , nums[j]);}return 0;
} 第二种双指针 int removeElement(int* nums, int numsSize, int val)
{int dst0;int src0;while(dstnumsSize){if(nums[dst]!val){nums[src]nums[dst];src;}dst;}return src;
}
四.盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。 示例1 输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为7*7 49。 示例 2 输入height [1,1] 输出1 做题链接盛最多水的容器
这道题还是使用双指针的方法来求
int max(int x, int y)
{return x y ? x : y;
}
int min(int x, int y)
{return x y ? x : y;
}
int maxArea(int* height, int heightSize)
{int left 0;int right heightSize - 1;int maxarea 0;while (left right){maxarea max(maxarea, min(height[left], height[right]) * (right - left));//min是求装水的最大高度肯定以最低的那条线为准不然就漏水了//right-left就是底边的长if (height[left] height[right])//说明height[right]此时是短的那根线需要right--往前找其他的线right--;elseleft;}return maxarea;
}
你的点赞评论收藏加关注都是我前进的动力。感谢
