广州网站建设 中网科技,android手机软件开发教程,西安网站建设有限公司,mvc5网站开发之六文章目录 题目移动零复写零两数之和N数之和(2个数) 答案讲解移动零复写零两数之和N数之和 题目
力扣
移动零 1、移动零:题目链接 复写零 2、复写零:题目链接 两数之和 3、两数之和题目链接 N数之和(2个数) 4、N数之和(三个数、四个数) 三个数:题目链接 四个数题目链接… 文章目录 题目移动零复写零两数之和N数之和(2个数) 答案讲解移动零复写零两数之和N数之和 题目
力扣
移动零 1、移动零:题目链接 复写零 2、复写零:题目链接 两数之和 3、两数之和题目链接 N数之和(2个数) 4、N数之和(三个数、四个数·····) 三个数:题目链接 四个数题目链接 答案讲解
移动零
思路 移动零这个题目是利用双指针算法 双指针不一定是用2个指针可以是下标或者值来代替 拿案例1来讲 让一个left指向-1 这个位置 让一个right指向0 这个位置 让right 走 如果right下标的数不为0 那么left swap(nums[left],nums[right]) 让right继续走 如果遇到0 那么 left不动 那么left的下一个数必定为0 交换完之后 0就会到后面去 代码
class Solution {
public:void moveZeroes(vectorint nums) {int cur 0;int dest -1;while(curnums.size()){if(nums[cur]!0){dest;swap(nums[cur],nums[dest]);}cur;}}
};复写零
思路 复写零 同样也是用双指针 先找到要复写之后最后一个数 这么找 用下标 一个定义cur为0 dest为-1 cur和dest同时 如果cur下标的数为0 那么dest多一次 如果dest走到最后一个元素那么就结束 cur位置就是最后复写的数 但是有一个小细节 因为如果最后一个要复写的数(cur位置为size-2的位置)并且为0 那么dest可能越界 所以要判断一下dest是否会越界 如果是这个情况 让数组最后一个数置为0 另一个0 因为越界了所以不用管 并且让cur–dest-2 这样子他们就不会越界了 找到需要复写的数下标cur之后 从后往前遍历 把cur下标位置的值赋值到dest位置下 如果cur下标位置为0 那么就让dest位置2次并且复写2次0 代码
class Solution {
public:void duplicateZeros(vectorint arr) {vectorint s;int cur 0;int dest -1;while(curarr.size()){if(arr[cur]){dest;}else{dest2;}if(destarr.size()-1){break;}cur;}if(destarr.size()){arr[arr.size()-1]0;cur--;dest-2;}while(cur0){if(arr[cur]){arr[dest--]arr[cur--];}else{arr[dest--]arr[cur];arr[dest--]arr[cur];cur--;}}}
};
两数之和
思路 同样是双指针算法 这个是升序的数组 定义一个下标为0的left和一个数组长度-1的数right 还有定义一个vector 用来接受最后的2个数 用下标left的数下标为right的数 一个数 如果这个数大于target 那么吧right-- 因为是升序把大的干掉 如果小于 把left 把小的干掉 代码 :
class Solution {
public:vectorint twoSum(vectorint price, int target) {vectorint s;int left 0,right price.size()-1;while(leftright){if(price[left]price[right]target){right--;}else if(price[left]price[right]target){left;}else{s.push_back(price[left]);s.push_back(price[right]);break;}}return s; }
};N数之和
三个数 题目解析: 要3个数相加0 并且不能重复 思路 因为要找出三个数的和为0 优质解法是双指针 先定一个i让i指向下标为0这个数 然后在[1,nums.size()-1]中定义一个left 指向i1这个位置 right 指向 size()-1这个位置 让一个数B接收 i下标位置的数并改成 他的相反数 这有一个小细节如果 i下标位置0那么 他后面的数都不用算了因为0的数相加肯定大于0 然后让一个数来接受left下标和right下标的数的和 如果这个和大于B 那么把大的干掉 如果小于 那么把小的干掉 找到之后吧他插入到vector中 然后left right– 去重(★) 如果left 位置和他的前一个位置 left-1的值相同 那么就 因为如果 相同那么都判断过了 他插入也是插入重复的 题目不要重复的 所以直接一直到不重复的为止 right也是一样 不过right是判断和他1位置的值如果相等那么– 四个数就是定2个数然后再后面的区间找 代码:
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());//排序吧数组变成有序vectorvectorint arr;for(int i 0;inums.size();){int left i1,right nums.size()-1;int a -nums[i];if(nums[i]0){//如果大于0 那么就说明后面的都是正数 正数正数 比他们两个小的正数break;}while(leftright){if(nums[left]nums[right]a){right--;}else if(nums[left]nums[right]a){left;}else{//{}扩起来的内容会形成一个vector 的数组扔到里面arr.push_back({nums[i],nums[left],nums[right]});left;right--;//去重操作while(leftright nums[left]nums[left-1]){left;}while(leftright nums[right]nums[right1]){right--;}}}//对nums[i]这个位置去重i;while(inums.size() nums[i]nums[i-1]){i;}}return arr; }
};
