admin管理员组文章数量:1794759
【算法刷题指南】双指针
283.移动零
283.移动零
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int cur = 0;
int dest = 0; // 已经处理区间内非0元素的位置
// [0,dest](全是非0元素) [dest+1,cur-1]（全是0元素） [cur,n-1](待处理元素)
while (cur < n) {
if (nums[cur]) {
swap(nums[dest], nums[cur]);
dest++;
cur++;
} else {
cur++;
}
}
}
};1089.复写零
1089.复写零
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int n = arr.size();
int dist = -1, cur = 0;
// 先判断cur的位置
while (cur < n) {
if (arr[cur]) {
dist++;
} else {
dist += 2;
}
if (dist >= n - 1)
break;
cur++;
}
if (dist == n) {
arr[n - 1] = 0;
cur--;
dist -= 2;
}
while (cur >= 0) {
if (arr[cur]) {
arr[dist] = arr[cur];
cur--;
dist--;
} else {
arr[dist--] = 0;
arr[dist--] = 0;
cur--;
}
}
}
};202.快乐数
202.快乐数
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
int solve(int n) {
int sum = 0;
while (n) {
int t = n % 10;
sum += t * t;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n, fast = solve(n);
while (slow != fast) {
slow = solve(slow);
fast = solve(solve(fast));
}
return slow == 1;
}
};11.盛最多水的容器
11.盛最多水的容器
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
int maxArea(vector<int>& height) {
int n=height.size();
int left=0,right=n-1;
int ans=0,ret=0;
while(left!=right)
{
ans=min(height[left],height[right])*(right-left);
ret=max(ans,ret);
if(height[left]>=height[right]) right--;
else left++;
}
return ret;
}
};611.有效三角形的个数
611.有效三角形的个数
判断三角形方法：a+b>c&&a+c>b&&b+c>a 但是这种判断方法需要判断三次 更加优化的方法：三个数是排好序的，a<b<c，只需要判断a+b>c成立与否
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
int triangleNumber(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int ans = 0;
for (int i = n - 1; i >= 2; i--) {
int left = 0, right = i - 1;
while (left != right) {
if (nums[left] + nums[right] > nums[i]) {
ans += right - left;
right--;
} else {
left++;
}
}
}
return ans;
}
};15.三数之和
15.三数之和
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < n; i++) {
if (nums[i] > 0)
return ans;
if (i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1, right = n - 1;
int t = -nums[i];
while (left < right) {
if (nums[left] + nums[right] < t)
left++;
else if (nums[left] + nums[right] > t)
right--;
else {
ans.push_back({nums[i], nums[left], nums[right]});
while (right > left && nums[right - 1] == nums[right])
right--;
while (right > left && nums[left + 1] == nums[left])
left++;
left++;
right--;
}
}
}
return ans;
}
};18.四数之和
18.四数之和
代码语言：javascript代码运行次数：0运行复制class Solution {
typedef long long LL;
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < n; j++) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
int left = j + 1, right = n - 1;
LL t = (LL)target - nums[i] - nums[j];
while (left < right) {
if (nums[left] + nums[right] < t)
left++;
else if (nums[left] + nums[right] > t)
right--;
else {
ans.push_back(
{nums[i], nums[j], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right - 1])
right--;
left++;
right--;
}
}
}
}
return ans;
}
};本文标签： 算法刷题指南双指针
版权声明：本文标题：【算法刷题指南】双指针 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754640996a1704677.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论