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

C++数据结构与算法——双指针法

news 来源：原创 2024/5/20 2:41:22

C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

文章目录

一、移除元素（力扣27）
二、反转字符串（力扣344）
三、替换数字（卡码网 54）
四、翻转字符串里的单词（力扣151）
五、反转链表（力扣206）
六、删除链表的倒数第 N 个结点（力扣19）
七、链表相交（力扣面试题 02.07）
八、环形链表 II（力扣142）
九、三数之和（力扣15）
十、四数之和（力扣18）

一、移除元素（力扣27）

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

class Solution {
public:int removeElement(vector<int>& nums, int val) {// 利用快慢指针进行删除// 1. 判断是否只有零个或一个元素，防止索引超出数组长度if(nums.size()==1){if(nums[0]==val){return 0;}else{return 1;}}if (nums.size()==0){return 0;}int slow =0;for(int fast=0;fast<nums.size();fast++){if(nums[fast]!=val){nums[slow] = nums[fast];slow++;}}return slow;}
};

在这里插入图片描述

二、反转字符串（力扣344）

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：
输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]
提示：
1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

class Solution {
public:void reverseString(vector<char>& s) {// 双指针解决int begin =0;int end = s.size()-1;while(begin<end){// 交换char temp = s[begin];s[begin] = s[end];s[end] = temp;begin++;end--;}}
};

在这里插入图片描述

三、替换数字（卡码网 54）

题目描述
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
输入描述
输入一个字符串 s,s 仅包含小写字母和数字字符。
输出描述
打印一个新的字符串，其中每个数字字符都被替换为了number
输入示例
a1b2c3
输出示例
anumberbnumbercnumber
提示信息
数据范围：
1 <= s.length < 10000。

#include <iostream>
using namespace std;int main() {string inputS;cin >> inputS;int count = 0;// 遍历原来数组,记录其中数字的个数for (int i = 0; i < inputS.length(); i++) {if (inputS[i] <= '9' && inputS[i]>='0') {count++;}}int FLength = inputS.length();// resize 原来的字符串inputS.resize(FLength + count * 5);// 替换原来字符串中的字符，从后向前替换int j = inputS.length()-1;for (int i = FLength - 1; j>i; i--,j--) {if (inputS[i] <= '9' && inputS[i]>='0') {// 是数字要替换inputS[j] = 'r';inputS[j-1] = 'e';inputS[j-2] = 'b';inputS[j-3] = 'm';inputS[j-4] = 'u';inputS[j-5] = 'n';j -= 5;}else {inputS[j] = inputS[i];}}cout << inputS << endl;system("pause");return 0;}

在这里插入图片描述

四、翻转字符串里的单词（力扣151）

给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

class Solution {
public:string reverseWords(string s) {// 去除空格removeSpace(s);// // 翻转整个句子reverse(s.begin(), s.end());// 翻转每个单词// 首先找到每个单词的位置int slow=0;for(int fast=0;fast<s.length();fast++){if(s[fast+1]==' ' || fast==s.length()-1){reverseWord(s,slow,fast);slow = fast+2;}}return s;}// 翻转每个单词void reverseWord(string& s, int begin, int end) {while (begin < end) {swap(s[begin], s[end]);begin++;end--;}}// 去除字符串中多余的空格void removeSpace(string& s) {// 快慢指针去除空格int slow = 0;for (int fast = 0; fast < s.length(); fast++) {if (s[fast] != ' ') {// 不为空格才进行下面的操作// 添加每个单词之间的空格，句子开头不加if (slow != 0) {s[slow] = ' ';slow++;}while (fast<s.size() && s[fast] != ' ') {s[slow] = s[fast];slow++;fast++;}}}s.resize(slow);}};

在这里插入图片描述

五、反转链表（力扣206）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==NULL||head->next==NULL){// 只有一个结点return head;}// 定义两个指针，一个指前面的，一指后面的ListNode *pre = NULL;ListNode *cur = head;while(cur!=NULL){// 用一个值去接收curListNode *temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}};

在这里插入图片描述

六、删除链表的倒数第 N 个结点（力扣19）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (head==NULL){return head;}ListNode * dummyNode = new ListNode(0);dummyNode->next = head;// 使用快慢指针ListNode* fast = dummyNode;ListNode* slow = dummyNode;while(n--){// 快指针先走n个fast = fast->next;}while(fast!=NULL&&fast->next!=NULL){fast = fast->next;slow = slow->next;}// 删除元素ListNode * temp = slow->next;slow->next = slow->next->next;delete temp; // 删除return dummyNode->next;}
};

在这里插入图片描述

七、链表相交（力扣面试题 02.07）

在这里插入图片描述

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 实际上是找相等的结点，不是值相等，而是 是同一个结点// 将两个链表右对齐// 求两个链表的长度if(headA==NULL||headB==NULL){return NULL;}int lenA =1;int lenB =1;ListNode * curA = headA;ListNode * curB = headB;while(curA->next!=NULL){lenA++;curA = curA->next;}while(curB->next!=NULL){lenB++;curB = curB->next;}// 找最短的链表int minLen =min(lenA,lenB);// AB需要移动的长度int needA= lenA-minLen;int needB = lenB - minLen;// 右对齐两个节点while(needA--){headA = headA->next;}while(needB--){headB = headB->next;}// 比较之后的链表是否相同while(headA!=NULL||headB!=NULL){if(headA== headB){return headA;}else{headA = headA->next;headB = headB ->next;}}return NULL;}
};

在这里插入图片描述

八、环形链表 II（力扣142）

在这里插入图片描述

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode * first = head;ListNode * slow = head;while(first!=NULL&&first->next!=NULL){first = first->next->next;slow = slow->next;if(first==slow){// 此时相遇ListNode * index1 = first;ListNode * index2 = head;// 找入环口while(index1!=index2){index1 = index1->next;index2 = index2->next;}return index1;}}return NULL;}
};

在这里插入图片描述

九、三数之和（力扣15）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 先对数组排序sort(nums.begin(),nums.end());// 定义结果数组vector<vector<int>> result;// 剪枝操作if(nums[0]>0){return {}; // 第一个元素都大于0了，说明不可能加起来等于0，直接返回空}for(int i=0;i<nums.size();i++){// 定义两个指针int begin = i+1;int end = nums.size()-1;// 去重操作if(i>0&&nums[i]==nums[i-1]){// 当前的i和i-1的元素是一样的continue; // 跳过当前循环}while(begin<end){if((nums[i]+nums[begin]+nums[end])==0){result.push_back({nums[i],nums[begin],nums[end]});while(begin<end&&nums[begin]==nums[begin+1]){begin++;}while(begin<end&&nums[end]==nums[end-1]){end--;}begin++;end--;}else if((nums[i]+nums[begin]+nums[end])>0){end--;}else{begin++;}}}return result;}
};

在这里插入图片描述

十、四数之和（力扣18）

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {// 先排序sort(nums.begin(),nums.end());// 定义最终返回数组vector<vector<int>> result;// 类似于三数之和，多了一层循环for (int i=0;i<nums.size();i++){// 剪枝if(nums[0]>=0&&nums[0]>target){break;}// 去重if(i>0&&nums[i]==nums[i-1]){continue;}for(int j=i+1;j<nums.size();j++){// 剪枝if(nums[i]+nums[j]>target&&nums[j]>=0){break;}// 去重if(j>i+1&&nums[j]==nums[j-1]){continue;}// 类似于三数之和int begin = j+1;int end = nums.size()-1;while(begin<end){if((long) nums[i]+nums[j]+nums[begin]+nums[end]==target){// 找到符合要求的数组，记录result.push_back({nums[i],nums[j],nums[begin],nums[end]});while(begin<end&&nums[begin]==nums[begin+1]){begin++;}while(begin<end&&nums[end]==nums[end-1]){end--;}begin++;end--;}else if((long)nums[i]+nums[j]+nums[begin]+nums[end]>target){end--;}else{begin++;}}}}return result;}
};