开源php企业网站,上海集团网站建设咨询,上海工程技术大学,淮安做网站的公司有哪些公司双指针应用场景#xff1a; 数组划分、数组分块 目录 一、移动0 二、复写0 从后向前 三、快乐数 链表带环 四、盛水最多的容器 单调性双指针
五、有效三角形个数 单调性双指针 六、和为s的两个数字
七、三数之和 细节多 需再练 一、移动0 class Solution {
public:void move… 双指针应用场景 数组划分、数组分块 目录 一、移动0 二、复写0 从后向前 三、快乐数 链表带环 四、盛水最多的容器 单调性双指针
五、有效三角形个数 单调性双指针 六、和为s的两个数字
七、三数之和 细节多 需再练 一、移动0 class Solution {
public:void moveZeroes(vectorint nums) {int dest -1;for(int cur 0;cur nums.size();cur){if(nums[cur]){swap(nums[dest],nums[cur]);}}}
}; 二、复写0 从后向前
c 细节当最后cur 0时要小心越界。 class Solution {
public:void duplicateZeros(vectorint arr) {int cur 0,dest -1;int n arr.size();while(cur arr.size()){if(arr[cur]) dest;else dest 2;if(dest n-1) break;cur;}if(dest n){arr[n - 1] 0;cur--;dest - 2;}while(cur 0){if(arr[cur]) arr[dest--] arr[cur--];else{arr[dest--] 0;arr[dest--] 0;cur--;}}}
}; 三、快乐数 链表带环 class Solution {
public:int bitSum(int n){int ret 0;while(n0){ret (n%10)*(n%10);n / 10;}return ret;}bool isHappy(int n) {int slow n, fast bitSum(n);while(slow ! fast){slow bitSum(slow);fast bitSum(bitSum(fast));}return slow 1;}
}; 四、盛水最多的容器 单调性双指针 注意高度由矮的决定。
class Solution {
public:int maxArea(vectorint height) {int n height.size();int left 0,right n-1;int ret 0;while(left right){int v min(height[left],height[right])*(right-left);ret max(ret,v);if(height[left] height[right]) left;else right--;}return ret;}
};
五、有效三角形个数 单调性双指针 核心两小边之和大于第三边就可以组成三角形。 class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int count 0;for(int m nums.size()-1;m 0;m--){int l 0,r m-1;while(l r){if(nums[l] nums[r] nums[m]) count (r-l),r--;else l;}}return count;}
}; 六、和为s的两个数字 出现上面这样的报错是因为编译器觉得可能没有返回值最后随便返回一个就行。
七、三数之和 细节多 需再练 注意要避免越界。
class Solution {
public:vectorvectorint threeSum(vectorint nums) {int n nums.size();sort(nums.begin(),nums.end());vectorvectorint ret;int i 0;while(i n){if(nums[i] 0)break;int left i1,right n-1,target -nums[i];while(left right){int sum nums[left]nums[right];if(sum target) left;else if(sum target) right--;else {ret.push_back({nums[i],nums[left],nums[right]});left,right--;while(left right nums[left] nums[left-1]) left;while(left right nums[right] nums[right1]) right--;} }i;while(i n nums[i] nums[i-1]) i;}return ret;}
};
