双指针练习（lc26&lc19)

双指针练习（lc26&lc19)

快排，快速排序就是双指针的一个运用

[TOC]

lc 26

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

自己想到的双指针做法↓
for循环遍历完数组，其中i相当于右指针

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int left=1;
        int right=1;
        if(nums.size()==0)
            return 0;
        for(int i=1;i<nums.size();i++){
            if(nums[i]==nums[i-1]&&left==0){
                left=i;//等待被写的位置
            }else if(nums[i]==nums[i-1]&&left!=0){
                continue;
            }else{
                nums[left++]=nums[i];
            }
        }
        return left;

    }
};

↓之前的一种麻烦的做法

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int left = 0;
        int right = left+1;
        if(nums.size()<=1)
            return nums.size();
        int dul=0;
        while(right<nums.size()){
            if(nums[right]==nums[left]){
                right+=1;
                dul+=1;
            }else if(dul==0){
                left+=1;
                right+=1;
            }else{
                nums[left+1]=nums[right];
                left+=1;
                right+=1;
                // dul-=1;
            }
        }
        return left+1;

        return nums.size();

    }
};

实际的双指针做法↓

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-tudo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路清奇版：

取一个极值，重复的元素都标记。

然后再遍历一遍，把不重复的元素都移到前面去。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //重复的给1e5
        //然后循环标记位置
        if(nums.size()==0)
        return 0;
        int a = nums[0];
        for(int i=1;i<nums.size();i++){
            
            if(nums[i]==a){
                nums[i]=1e5;
            }else{
                a=nums[i];
            }
        }
        int index=0;
        for(int i=1;i<nums.size();i++){
            if(nums[i]==1e5&&index==0){
                index=i;
            }else if(nums[i]==1e5){continue;}
            else if(index!=0){
                nums[index]=nums[i];
                nums[i]=1e5;
                while(index<=i&&nums[index]!=1e5){
                    index+=1;
                }
                if(index>i){
                    index=0;
                }
            }
        }
        int res=nums.size();
        for(int i=nums.size()-1;i>=0;i--){
            if(nums[i]!=1e5)
                return i+1;
        }
        return nums.size();

    }
};

lc19

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这里标准解法也是用双指针。
删除倒数第几个，就让两个指针直接隔多少个数。

/**
 * 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(n==0)
            return head;
        ListNode* now = new ListNode(-1,head);
        ListNode* left = now;
        ListNode* right = head;

        int index=1;
        while(index<n){
            right=right->next;
            index+=1;
        }
        
        while(right->next){
            right = right->next;
            left=left->next;
        }

        left->next=left->next->next;
        ListNode* res = now->next;
        delete now;//官方解法想到删指针。
        return res;
    }
};

说到一遍遍历，我立刻想到了map指针的做法，之前面试时某面试官出的题目，一种神奇的思路。但是觉得也很合理。

/**
 * 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) {
        ListNode* now = new ListNode(-1,head);
        ListNode* current = now;
        //一遍扫描，用map实现坐标和listnode的映射。
        int index=0;
        map<int,ListNode*> cunchu;
        while(current->next){
            cunchu[index]=current;
            index+=1;
            current=current->next;
        }
        if(index-n<0)
            return now->next;
        cunchu[index-n]->next=cunchu[index-n]->next->next;
        return now->next;
    }
};