leetcode双指针（进阶）

蔚落 2022-09-09 04:35 196阅读 0赞

1.  删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。  
输入：head = \[1,2,3,3,4,4,5\]  
输出：\[1,2,5\]  
输入：head = \[1,1,1,2,3\]  
输出：\[2,3\]

用i，j两个指针进行搜索，同时设置prei指针记录i的前驱位置。循环过程中，j先向后一格，若与i相同，则继续向后移动，直到走过了所有重复的节点。将prei.next指向j（删除了中间的重复），i也指向j。之后进入下一次循环，j再向后移动，直到结尾。  
答案返回的是头节点的位置，如果链表开头就是重复的数字，则需要调整头节点的位置到删除重复后的prei位置。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
        ListNode cur=new ListNode(0,head);
        ListNode i=new ListNode(1);
        ListNode prei=new ListNode(0);
        ListNode j=new ListNode(1);
        j=head;i=head;
        if(j==null){
        
            return null;
        }
        int flag=0;
        while(j.next!=null){
        
            j=j.next;
            if(i.val==j.val){
        
            while(j.val==i.val&&j.next!=null){
        
                j=j.next;
            }
            if(j.next==null&&j.val==i.val)//直到结尾的所有节点都是重复的
            {
        
            prei.next=null;}
            else{
        prei.next=j;}//不是特殊情况的话，则让prei指向不在重复的节点位置
            if(flag==0){
        cur=prei;//开始位置是重复的数字，移动头节点的位置到prei
            flag=1;}
            i=j;
            }
            else{
        
            flag=1;
            prei=i;
            i=i.next;
            }
        }
        return cur.next;
        }
    }

1.  比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 \# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。  
输入：S = “ab\#c”, T = “ad\#c”  
输出：true  
解释：S 和 T 都会变成 “ac”。

输入：S = “ab\#\#”, T = “c\#d\#”  
输出：true  
解释：S 和 T 都会变成 “”。

退格可以反向使用双指针进行遍历，遇到\#，设置skip变量+1，当遇到字母时，跳过skip值的格数。

class Solution {
        
        public boolean backspaceCompare(String S, String T) {
        
            int i = S.length() - 1, j = T.length() - 1;
            int skipS = 0, skipT = 0;
    
            while (i >= 0 || j >= 0) {
        
                while (i >= 0) {
        //找s中第一个需要比较的字母
                    if (S.charAt(i) == '#') {
        
                        skipS++;
                        i--;
                    } else if (skipS > 0) {
        
                        skipS--;
                        i--;
                    } else {
        
                        break;
                    }
                }
                while (j >= 0) {
        //找t中第二个需要比较的字母
                    if (T.charAt(j) == '#') {
        
                        skipT++;
                        j--;
                    } else if (skipT > 0) {
        
                        skipT--;
                        j--;
                    } else {
        
                        break;
                    }
                }
                if (i >= 0 && j >= 0) {
        
                    if (S.charAt(i) != T.charAt(j)) {
        
                        return false;
                    }
                } else {
        
                    if (i >= 0 || j >= 0) {
        
                        return false;
                    }
                }
                i--;
                j--;
            }
            return true;
        }
    }

1.  区间列表的交集

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList\[i\] = \[starti, endi\] 而 secondList\[j\] = \[startj, endj\] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。

形式上，闭区间 \[a, b\]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，\[1, 3\] 和 \[2, 4\] 的交集为 \[2, 3\] 。  
输入：firstList = \[\[0,2\],\[5,10\],\[13,23\],\[24,25\]\], secondList = \[\[1,5\],\[8,12\],\[15,24\],\[25,26\]\]  
输出：\[\[1,2\],\[5,5\],\[8,10\],\[15,23\],\[24,24\],\[25,25\]\]

观察可发现，交集等于，两个范围中左端较大值和右端较小的值，之后右端较小的切换下一个范围继续参与比较。

class Solution {
        
      public int[][] intervalIntersection(int[][] A, int[][] B) {
        
        List<int[]> ans = new ArrayList();
        int i = 0, j = 0;
    
        while (i < A.length && j < B.length) {
        
          int lo = Math.max(A[i][0], B[j][0]);
          int hi = Math.min(A[i][1], B[j][1]);
          if (lo <= hi)
            ans.add(new int[]{
        lo, hi});
          if (A[i][1] < B[j][1])
            i++;
          else
            j++;
        }
    
        return ans.toArray(new int[ans.size()][]);
      }
    }

1.  盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWJ5c3N3YXRjaGVyXzE_size_19_color_FFFFFF_t_70_g_se_x_16]  
盛水的值等于底的长度×左右两端较低的高度值，双指针初始在两端，搜索过程中会减小底的值，为了获取最大值，需要提高height才有更大的可能。  
若左边的的右侧一条边大于当前左边，则将其向右移动（反之右边）。

class Solution {
        
        public int maxArea(int[] height) {
        
        int size = height.length;
            int left=0, right=size-1;
            int ans = 0;
            while(left < right){
        
                ans = Math.max(ans, (right-left)*Math.min(height[left], height[right]));
                if(height[left] > height[right]) --right;
                else ++left;
            }
            return ans;
        }
    }

1.  三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。  
输入：nums = \[-1,0,1,2,-1,-4\]  
输出：\[\[-1,-1,2\],\[-1,0,1\]\]  
输入：nums = \[\]  
输出：\[\]

将三个数的和为0转化为两个数的和等于另一个数的负数，首先保证该数组有序，为了避免结果出现重复，则当前搜索的值不能与上一个相同。

class Solution {
        
        public List<List<Integer>> threeSum(int[] nums) {
        
            int n = nums.length;
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            // 枚举 a
            for (int first = 0; first < n; ++first) {
        
                // 需要和上一次枚举的数不相同，确定第一个数
                if (first > 0 && nums[first] == nums[first - 1]) {
        
                    continue;
                }
                // c 对应的指针初始指向数组的最右端
                int third = n - 1;
                int target = -nums[first];
                // 枚举 b
                for (int second = first + 1; second < n; ++second) {
        
                    // 需要和上一次枚举的数不相同
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
        
                        continue;
                    }
                    // 需要保证 b 的指针在 c 的指针的左侧
                    while (second < third && nums[second] + nums[third] > target) {
        
                        --third;
                    }
                    // 如果指针重合，随着 b 后续的增加
                    // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                    if (second == third) {
        
                        break;
                    }
                    if (nums[second] + nums[third] == target) {
        
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        ans.add(list);
                    }
                }
            }
            return ans;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAYWJ5c3N3YXRjaGVyXzE_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/2cf97c898ed94f4f94d460b01c280c61.png