当前位置: 首页 > news >正文

【算法刷题指南】双指针

在这里插入图片描述

🌈个人主页: 南桥几晴秋
🌈C++专栏: 南桥谈C++
🌈C语言专栏: C语言学习系列
🌈Linux学习专栏: 南桥谈Linux
🌈数据结构学习专栏: 数据结构杂谈
🌈数据库学习专栏: 南桥谈MySQL
🌈Qt学习专栏: 南桥谈Qt
🌈菜鸡代码练习: 练习随想记录
🌈git学习: 南桥谈Git

🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
本科在读菜鸡一枚,指出问题及时改正

283.移动零

283.移动零

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.复写零

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.快乐数

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.盛最多水的容器

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成立与否

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.三数之和

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.四数之和

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.mrgr.cn/news/56282.html

相关文章:

  • YOLOv8-seg训练自己的分割数据集
  • Django项目实战-图书管理系统之项目搭建
  • OBOO鸥柏:引领液晶拼接大屏kvm集中控制系统的技术革新
  • 持续优化之路:Envoia许可证管理的轻松进阶
  • URL、URN和URI的区别
  • GJB438C-2021《软件需求规格说明》的一处修订
  • APIJSON 为零代码提供了新的思路
  • Python 应用可观测重磅上线:解决 LLM 应用落地的“最后一公里”问题
  • LeetCode 1750.删除字符串两端相同字符后的最短长度
  • 3.1.1ReactOS系统中搜索给定长度的空间地址区间函数的实现
  • 深度学习:Yolo系列 V1和V2的对比
  • Point2CAD: Reverse Engineering CAD Models from 3D Point Clouds 论文阅读
  • 【C++】用哈希桶模拟实现unordered_set和unordered_map
  • 【大模型】一个简单程序看透 RAG 的核心原理,理解优化 RAG 的关键要点
  • Redission分布式锁详解
  • YOLO目标检测理论详解,YOLOv1理论知识讲解,超w字精读(学习YOLO框架必备),全网最详细教程
  • 嵌入式 MCU 编程提速秘籍 —— 让你的程序飞起来!
  • 书生实战营第四期-第一关Linux+InternStudio
  • 肉桂酰辅酶A还原酶Cinnamoyl-CoA Reductases(CCR)表征及晶体-文献精读70
  • 0基础学java之Day12