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

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

  print(nums[i]);

  }

  class Solution {public:    int removeElement(vector& 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            if(nums[fast]!=val){                nums[slow] = nums[fast];                slow++;            }        }        return slow;    }};public:    void reverseString(vector        // 双指针解决        int begin =0;        int end = s.size()-1;        while(begin            // 交换            char temp = s[begin];            s[begin] = s[end];            s[end] = temp;            begin++;            end--;        }    }};    string inputS;    cin  inputS;    int count = 0;    // 遍历原来数组,记录其中数字的个数    for (int i = 0; i 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 threeSum(vector& nums) {        // 先对数组排序        sort(nums.begin(),nums.end());        // 定义结果数组        vector result;        // 剪枝操作        if(nums[0]>0){            return {}; // 第一个元素都大于0了，说明不可能加起来等于0，直接返回空        }        for(int i=0;i            // 定义两个指针            int begin = i+1;            int end = nums.size()-1;            // 去重操作            if(i0&&nums[i]==nums[i-1]){                // 当前的i和i-1的元素是一样的                continue; // 跳过当前循环            }            while(begin                if((nums[i]+nums[begin]+nums[end])==0){                    result.push_back({nums[i],nums[begin],nums[end]});                    while(begin                        begin++;                    }                    while(begin                        end--;                    }                    begin++;                    end--;                }                else if((nums[i]+nums[begin]+nums[end])0){                    end--;                }                else{                    begin++;                }            }        }        return result;    }};public:    vector        // 先排序        sort(nums.begin(),nums.end());        // 定义最终返回数组        vector            // 剪枝            if(nums[0]=0&&nums[0]target){                break;            }            // 去重            if(i0&&nums[i]==nums[i-1]){                continue;            }            for(int j=i+1;j                // 剪枝                if(nums[i]+nums[j]target&&nums[j]=0){                    break;                }                // 去重                if(ji+1&&nums[j]==nums[j-1]){                    continue;                }                // 类似于三数之和                int begin = j+1;                int end = nums.size()-1;                while(begin                    if((long) nums[i]+nums[j]+nums[begin]+nums[end]==target){                        // 找到符合要求的数组，记录                        result.push_back({nums[i],nums[j],nums[begin],nums[end]});                        while(begin                            begin++;                        }                        while(begin                            end--;                        }                        begin++;                        end--;                    }                    else if((long)nums[i]+nums[j]+nums[begin]+nums[end]target){                        end--;                    }                    else{                        begin++;                    }                }            }        }        return result;    }};