首页 > 其他分享 >代码随想录刷题记录——双指针篇

代码随想录刷题记录——双指针篇

时间:2023-09-07 21:44:53浏览次数:41  
标签:slow ListNode nums int 随想录 fast next 刷题 指针

27. 移除元素

题目链接

  • 快慢指针,最终返回index值为移除元素后的数组末尾元素下标+1.
#include<vector>
using namespace std;

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //快慢指针
        int nums_length = nums.size();
        int index = 0;//慢指针
        for (int i=0;i<nums_length;i++){//i为快指针
            if(nums[i]!=val){
                nums[index]=nums[i];
                index++;
            }
        }
        return index;
    }
};

344. 反转字符串

题目链接

class Solution {
public:
    void reverseString(vector<char>& s) {
        int len = s.size();
        for(int i=0, j=len-1;i<j;i++,j--){
            // int temp = s[i];
            // s[i] = s[j];
            // s[j] = temp;
            swap(s[i],s[j]);
        }
        return ;
    }
};

 

题目:剑指Offer 05.替换空格

题目链接

  • C++中string字符串replace函数,str.replace(start_index, length, "%20")
class Solution {
public:
    string replaceSpace(string s) {
        string c = "%20";
        for(int i=0;i<s.size();i++){
            if(s[i]==' '){
                s.replace(i,1,c);
            }
        }
        return s;
    }
};

 

151.翻转字符串里的单词

题目链接

class Solution {
public:
    string reverseWords(string s) {
        vector<string> a;
        string ans = "";
        for(int i=0;i<s.size();i++){
            if(s[i]!=' '){
                ans += s[i];
            }
            if(s[i] ==' '&&ans!=""){
                a.push_back(ans);
                ans = "";
            }
        }
        if(ans!=""){
            a.push_back(ans);
        }
        ans = "";
        for(int i=a.size()-1;i>=0;i--){
            if(i==0){
                ans += a[i];
            }
            else{
                ans += a[i] + ' ';
            }
        }
        return ans;
    }
};

 

206. 反转链表

题目链接

  • 双指针:pre、cur
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr, *cur = head, *temp;
        while(cur){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

19.删除链表的倒数第N个节点

题目链接

  • 虚拟头结点dummyHead
  • 先行指针fast、后行指针slow,fast先走n+1步,当fast为null时,slow->next即为要删除的节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode *slow = dummyHead, *fast = dummyHead;
        while(n+1){
            fast = fast->next;
            n--;
        }
        while(fast){
            fast = fast->next;
            slow = slow->next;
        }
        ListNode *temp = slow->next;
        slow->next = temp->next;
        delete temp;
        return dummyHead->next;
    }
};

 

 

面试题 02.07. 链表相交

题目链接

 

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA, *curB = headB;
        int lenA = 0, lenB = 0;
        while(curA){
            lenA++;
            curA = curA->next;
        }
        while(curB){
            lenB++;
            curB = curB->next;
        }
        //指针复位
        curA = headA, curB = headB;
        int gap = lenA > lenB ? lenA-lenB : lenB - lenA;
        //这里默认链表A更长
        if(lenA < lenB) swap(curA, curB);
        while(gap){
            curA = curA->next;
            gap--;
        }
        while(curA){
            if(curA == curB) return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

 

 

142.环形链表II

题目链接

  • 快慢指针判断链表是否有环:fast每次两步,slow每次一步
  • 当有环时,p1指向head,p2指向相遇点,当p1、p2相遇时,即为环的入口节点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while(fast&&fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow){
                ListNode *p1 = head, *p2 = slow;
                while(p1!=p2){
                    p1 = p1->next;
                    p2 = p2->next;
                }
                return p1;
            }
        }
        return nullptr;
    }
};

 

 

第15题. 三数之和

题目链接

  • 剪枝
  • 去重
  • 双指针
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());//原地排序
        vector<vector<int>> ans;
        for(int i=0;i<nums.size();i++){//a+b+c中的a
            if(nums[i]>0){
                return ans;
            }
            //a去重,因为答案中不可以包含重复三元组
            if(i>0 &&nums[i]==nums[i-1]){
                continue;
            }
            for(int left=i+1, right=nums.size()-1;left<right;){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }
                else if(sum<0){
                    left++;
                }
                else if(sum==0){
                    ans.push_back({nums[i],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;
    }
};

 

 

第18题. 四数之和

题目链接

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        // for(int i=0;i<nums.size()-3;i++){   //a+b+c+d,遍历a
        for(int i=0;i<nums.size();i++){   //a+b+c+d,遍历a
            //剪枝
            if(nums[i]>target&&nums[i]>=0){
                break;
            }
            //a去重
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            // for(int j=i+1;j<nums.size()-2;j++){     //遍历b
            for(int j=i+1;j<nums.size();j++){     //遍历b
                //剪枝
                if(nums[i]+nums[j]>target&&nums[j]>=0){     //这里a+b不会溢出,int:2^31-1==2.e9;
                    break;
                }
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                for(int left=j+1, right=nums.size()-1;left<right;){
                    //双指针
                    long sum = (long)nums[i]+nums[j]+nums[left]+nums[right];//防溢出
                    if(sum>target){
                        right--;
                    }
                    else if(sum<target){
                        left++;
                    }
                    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;
    }
};

 

 

双指针总结

  • 对于数组,不真正删除,只覆盖,采用双指针
  • 对于字符串,头尾双指针
  • 对于链表,快慢双指针

 

标签:slow,ListNode,nums,int,随想录,fast,next,刷题,指针
From: https://www.cnblogs.com/daxiawan2022/p/17686066.html

相关文章

  • 代码随想录个人笔记——字符串篇
    344.反转字符串 题目链接#include<bits/stdc++.h>usingnamespacestd;classSolution{public:voidreverseString(vector<char>&s){intlen=s.size();for(inti=0,j=len-1;i<j;i++,j--){//第一种//i......
  • 代码随想录算法训练营第二天
    代码随想录算法训练营第二天|LeetCode977(有序数组的平方)LeetCode209(长度最小的子数组)LeetCode59(螺旋矩阵II)977:有序数组的平方LeetCode977(有序数组的平方)思路:方法一:暴力方法直接原地平方后,直接调用数组排序方法二:双指针前后遍历,构造结果数组,保证有序方法......
  • 【C++】C++ 引用详解 ⑦ ( 指针的引用 )
    文章目录一、二级指针可实现的效果二、指针的引用1、指针的引用等同于二级指针(重点概念)2、引用本质-函数间接赋值简化版本3、代码示例-指针的引用一、二级指针可实现的效果指针的引用效果等同于二级指针,因此这里先介绍二级指针;使用二级指针作为参数,可......
  • 【C++】C++ 引用详解 ④ ( 函数返回 静态变量 / 全局变量 的 引用 / 指针 )
    文章目录一、函数返回静态变量/全局变量的引用/指针1、函数返回局部变量引用或指针无意义2、函数返回静态变量/全局变量的引用或指针3、代码示例-函数返回静态变量/全局变量的引用或指针一、函数返回静态变量/全局变量的引用/指针1、函数返回局部变量引用或指针......
  • 【刷题笔记】
    题目Givenacollectionofcandidatenumbers(candidates)andatargetnumber(target),findalluniquecombinationsin candidates wherethecandidatenumberssumsto target.Eachnumberin candidates mayonlybeused once inthecombination.Note:All......
  • 代码随想录算法第一天704
    代码随想录算法第一天|704.二分查找、27.移除元素学习(复习)数组理论基础:​ (https://programmercarl.com/数组理论基础.html)​ 新了解到Java中数组地址不是连续的。704.二分查找题目题目链接:https://leetcode.cn/problems/binary-search/文章讲解:https://programmercarl.......
  • 代码随想录算法训练营第一天
    代码随想录算法训练营第一天|LeetCode704(二分查找)LeetCode35(搜索插入位置)LeetCode34(在排序数组中查找元素的第一个和最后一个位置 )LeetCode27(移除元素)数组理论基础数组是存放在连续内存空间上的相同类型数据的集合要点:数组下标都是从0开始的数组内存空间......
  • 算法刷题:一步步优化系列01.最长连续序列
    题目链接:最长连续序列目录暴力解法(超时)优化内层查找(On->O1但超时)问题:重复的边界会重新迭代优化重复迭代:在值域而非定义域迭代,去重(超时)问题:值域大且元素离散度大时,会大量迭代到不存在的元素,空迭代优化空迭代:HashSet去重,每次迭代的元素都存在(26ms)从左边界重......
  • 【Leetcode刷题记录】1、统计参与通信的服务器;2、统计二叉树中好节点的数目;3、从两个
    1、统计参与通信的服务器题目:这里有一幅服务器分布图,服务器的位置标识在 m*n 的整数矩阵网格 grid 中,1表示单元格上有服务器,0表示没有。如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。请你统计并返回能够与至少一台其他服务器进行通信的服务器的......
  • 【C语言进阶】指针数组 —— 数组指针
    (文章目录)......