中山精品网站建设行情,广告设计制作公司简介,长沙网站建设开发,网页设计范例目录 1. 双指针1.1 移动 01.2 复写 01.3 快乐数#xff08;快慢指针#xff09;1.4 盛水最多的容器#xff08;单调性原则#xff09;1.5 有效三角形个数1.6 两个数之和1.7 三数之和1.8 四数之和 1. 双指针
1.1 移动 “0” 题目信息#xff1a; … 目录 1. 双指针1.1 移动 01.2 复写 01.3 快乐数快慢指针1.4 盛水最多的容器单调性原则1.5 有效三角形个数1.6 两个数之和1.7 三数之和1.8 四数之和 1. 双指针
1.1 移动 “0” 题目信息 题目链接 移动 “0” 思路演示 补充 [0, dest]区间内的元素都为0[dest 1, cur]区间内的元素都不为0cur指针遍历完数据调整结束 class Solution
{
public:void moveZeroes(vectorint nums) {int dest -1;int cur 0;while(cur nums.size()){if(nums[cur]){swap(nums[cur], nums[dest]);}cur;}}
};1.2 复写 “0” 题目信息 题目链接 复写0 思路演示 注意 寻找最后未覆盖结点时可能回导致dest越界从而导致逆向复写的过程中出现越界错误。 例[0, 0, 0] 因此需要对此种越界情况做特殊处理。 class Solution
{
public:void duplicateZeros(vectorint arr) {//找结点int cur -1;int dest -1;int size arr.size();while (dest size - 1){cur;if (arr[cur] 0){dest 2;}else{dest;}}//越界可能while(cur 0){if(arr[cur] 0){//特殊处理if(dest size - 1){arr[--dest] arr[cur];}else{arr[dest] arr[cur];arr[--dest] arr[cur];}}else{//特殊处理if(dest size - 1){arr[--dest] arr[cur];}else{arr[dest] arr[cur];}}dest--;cur--;}}
};1.3 快乐数快慢指针 题目信息 题目链接 快乐数 过程演示 注 无论数n是否为快乐数其进行快乐数的判断逻辑一定都会进入一个循环。我们将每次运算得出的结果视为结点平方和的运算步骤视为链表的一步。那么上述问题就可以理解为链表循环问题。是否为只有1的环 class Solution
{
public:int gethappy(int num){int sum 0;while(num){sum (num % 10) * (num % 10);num / 10;}return sum;}bool isHappy(int n) {//环状链表快慢指针int quick n;int slow n;do{//快慢指针//走一步slow gethappy(slow);//走两步quick gethappy(quick);quick gethappy(quick);}while(slow ! quick);if(slow 1){return true;}return false;}
};1.4 盛水最多的容器单调性原则 题目信息 题目链接 盛水最多的容器 过程演示 思路1求出所有的容积然后在其中选出最大暴力求解 思路2单调性原则 容器的的高是由短边决定的因此可以确定在高不变的情况下移动长边只会导致底变短所以可以确定当前的搭配是以短边为高一组中容积最大的 只需记录每组中最大的容积算法时间复杂度优化为O(n) class Solution {
public:int maxArea(vectorint height) {//单调性原则//将小边丢掉int left 0;int right height.size() - 1;vectorint area;while(left right){if(height[left] height[right]){area.push_back((right - left) * height[left]);left;}else{area.push_back((right - left) * height[right]);right--;}}int max area[0];for(auto e : area){if(e max){max e;}}return max;}
};1.5 有效三角形个数 题目信息 题目链接 有效三角形个数思路 1 先将所给数组进行排序升序 2 判断三个数是否能够组成三角形的三个边任意两边之和大于第三边 3 指针对撞法优化暴力求解 过程演示
class Solution
{
public:int triangleNumber(vectorint nums) {//任意两边之和大于第三边//优化先排序再判断sort(nums.begin(), nums.end());int times 0;int count nums.size() - 1;int left 0;int right count - 1; while(count 2){while(right 1){while(left right nums[right] nums[left] nums[count]){left;}if(left right){times (right - left);}right--;}left 0;count--;right count - 1;}return times;}
};1.6 两个数之和 题目信息 题目链接 两数之和思路 1 若两数之和大于等于指定数移动右指针 2 若两数之和小于指定数移动左指针 直至两指针相撞 过程演示
class Solution
{
public:vectorint twoSum(vectorint price, int target) {vectorint goods;//大挪右小挪左int left 0;int right price.size() - 1;while(left right price[left] price[right] ! target){if(price[left] price[right] target){right--;}if(price[left] price[right] target){left;}}if(left right){goods.push_back(price[left]);goods.push_back(price[right]);}return goods;}
};1.7 三数之和 题目信息 题目链接 三数之和思路 1 将整个数组排序固定一个数num创建两个指针left最左则与right固定数num的前一个元素 2 左右指针开始遍历数组arr[left] arr[right] numleft指针右移arr[left] arr[right] numright指针左移当arr[left] arr[right] num时记录此次搭配。重复遍历步骤直至left right结束此次遍历 3 重复步骤2直至num 2 过程演示
class Solution
{
public:vectorvectorint threeSum(vectorint nums){//排序//去重//单调性vectorvectorint v1;sort(nums.begin(), nums.begin() nums.size());int cur nums.size() - 1;int right 0;int left 0;while (cur 1){right cur - 1;left 0;//一次遍历while (right left){//判断同时去重if ((right cur - 1 nums[right] nums[right 1]) || nums[right] nums[left] -nums[cur]){right--;}else if ((left 0 nums[left] nums[left - 1]) || nums[right] nums[left] -nums[cur]){left;}else{//记录vectorint v2;v2.push_back(nums[left]);v2.push_back(nums[right]);v2.push_back(nums[cur]);v1.push_back(v2);right--;}}//去重do{cur--;} while (cur 1 nums[cur] nums[cur 1]);}return v1;}
};1.8 四数之和 题目信息 题目链接 四数之和思路在三指针的基础上再套一层注int类型存在数据溢出的风险 class Solution
{
public:vectorvectorint fourSum(vectorint nums, int target){sort(nums.begin(), nums.end());vectorvectorint vv;int end nums.size() - 1;int a 0;while (end - a 1 4){int b a 1;while (end - b 1 3){int left b 1;int right end;while (left right){int sum nums[left] nums[right];long long goal (long long)target - nums[a] - nums[b];//去重if ((right end nums[right 1] nums[right]) || sum goal){right--;}else if ((left b 1 nums[left - 1] nums[left]) || sum goal){left;}else{vectorint v;v.push_back(nums[a]);v.push_back(nums[b]);v.push_back(nums[left]);v.push_back(nums[right]);vv.push_back(v);left;}}do{b;} while (end - b 1 3 nums[b - 1] nums[b]);}do{a;} while (end - a 1 4 nums[a - 1] nums[a]);}return vv;}
};
