👉 day03 双指针

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

难度中等970

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

蛮力法

遍历链表 ,使用数组存储下每个值出现的次数, 然后再次遍历,

造一个新的链表, 返回即可

  • 注意题目的数据 : -100<=val<=100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode pre=new ListNode(-1);
        ListNode cur=head;
        int []nums=new int[200];
        while(cur!=null){
            nums[cur.val+100]++;
            cur=cur.next;
        }
        ListNode res=new ListNode(-1);
        head=res;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==1){
                res.next=new ListNode(i-100);
                res=res.next;
            }
        }
        return head.next;
    }
}

🎈15. 三数之和

难度中等5138

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

**注意：**答案中不可以包含重复的三元组。

双指针

思路:

  1. 对数组进行排序

  2. 先设定一个前置的值

    • 然后定义两个指针, 指向当前的值得后面的元素 l=i+1 , r=len-1 , 这里类似于二分的思想
    • 随后遍历数组 , 移动指针, 根据情况来调整 l r 的位置,

  3. 注意对结果的

    去重

    • 数组的相邻两项相同
    • 左右指针的前后两项相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
思路:
1, 对数组进行排序
2, 先设定一个前置的值
   - 然后定义两个指针, 指向当前的值得后面的元素  l=i+1 , r=len-1   , 这里类似于二分的思想
   - 随后遍历数组 , 移动指针, 根据情况来调整 l r 的位置, 
3, 注意对结果的去重 
*/
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums==null||nums.length<3) return null;
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0) return res;
             // 如果 当前的 数值> 0 ,  那么和一定>0 , 因为是排序过的数组, 右面的两个L R位置的元素一定比nums[i]大
             if(i>0&&nums[i]==nums[i-1]) continue;  //去重
            int L=i+1;
            int R=nums.length-1;
            while(L<R){
                int sum=nums[i]+nums[L]+nums[R];
                if(sum==0){
                    res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    // 注意下面的两个while循环需要满足 L<R , 不然可能出现 L>R 的情况
                    while(L<R&&nums[L]==nums[L+1]) L++; // 去重  结果不=不能返回相同的值
                    while(L<R&&nums[R]==nums[R-1]) R--; // 去重
                    // 同时R左移 , L右移
                    L++;
                    R--;
                }
                else if(sum<0) L++;
                else if(sum>0)  R--;
            }
        }
        return res;
    }
}

👉day04 双指针

844. 比较含退格的字符串

难度简单494

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意如果对空文本输入退格字符，文本继续为空。

双指针

字符数组定义两个指针,

一个slow用来统计有效的字符, 一个fast用来遍历字符数组

  • 遇到正常的字符就直接统计进去 chars[++slow]=chars[fast]

  • 如果遇到了 #, 那么就需要 “退格” : slow--

    • 注意, 这一步的操作, slow必须>=0 , 否则后面统计字符的时候就会导致下标异常
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean backspaceCompare(String s, String t) {
        return BackSpace(s).equals(BackSpace(t));
    }
    public String BackSpace(String s){
        char[]chars=s.toCharArray();
        int slow=-1,fast=0;
        while(fast<chars.length){
            if(chars[fast]!='#') chars[++slow]=chars[fast]; // 普通字母直接统计
            else{// 遇到#考虑退格(注意slow只统计非#的字符,并不会覆盖掉fast)
                if(slow>=0) slow--; // 没有字符的时候就不需要在slow--了
            }
            fast++;
        }
        //slow位索引就是最后一个字母位置,索引+1就是个数->生成String (String 的这个构造器的第三个参数是字符的个数)
        return new String(chars,0,slow+1);// new String(char[]chars, int offSet, int count); 
    }
}

986. 区间列表的交集

难度中等317

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

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

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

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

本题需要求的是 , 两个区间的数组的展开的所有的交集

双指针

  1. 定义p1,p2 两个指针, 分别指向两个二维数组

  2. 比较两个区间

    • 对于左边界, 对应的是 两个区间的较大值int l=Math.max(arr1[0],arr2[0]);
    • 对于右边界, 对应的是两个区间的较小值 int r=Math.min(arr1[1],arr2[1]);

  3. 我们比较两个区间的右边界, 将右边界较小的那个二维数组的指针右移

    • 可以考虑一种比较极端的情况来辅助理解:

    在上面的这种情况中, secondList 的范围远大于firstList , 通过这个不难理解为什么我们要将右边界较小的那个二维数组的指针右移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> res=new ArrayList<>();
        int len1=firstList.length, len2=secondList.length;
        int p1=0,p2=0;
        while(p1<len1&&p2<len2){
            int []arr1=firstList[p1];
            int []arr2=secondList[p2];
            int l=Math.max(arr1[0],arr2[0]);
            int r=Math.min(arr1[1],arr2[1]);
            if(l<=r){
            // 区间满足 , 注意, 这个区间满足了, 极端情况可能 某个区间特别大, 甚至包括 另外一个区间集的所有区间,因此我们需要
            //判断大小然后 选择哪个区间右移
                res.add(new int[]{l,r});
            }
            if(arr1[1]<arr2[1]) p1++;
            else p2++;
        }
       return res.toArray(new int[res.size()][]);
    }
}
// 0 2   5 10   13 23   24 25
// 1 5   8 12   15 24   25 26
//所有的区间的列表的交集
/*
   1 2 
   5 5
   8 10 
   15 23
   24 24
   25 25 
*/

🎈11. 盛最多水的容器

难度中等3724

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

思路:

面积 :math.min(height[i],height[j])*( j-i)

双指针:

  1. 定义左右两个指针, 分别指向数组左右两侧

  2. 每次向里面收缩 i ,j 中的较短的那个板, 维护res

    • i, j 相遇时结束

  3. 最会返回res

  • 注意(j-i)*height[i++] 以及(j-i)*height[j--] 的相乘的顺序, 需要吧 j-i 放到前面, 否则会少乘

每次收缩短板的原因:

  • 若向内 移动短板 ，水槽的短板 min(h[i],h[j])可能变大，因此下个水槽的面积 可能增大 。

  • 若向内 移动长板 ，水槽的短板min(h[i], h[j])不变或变小，因此下个水槽的面积一定变小

    • 注意 : 水槽的面积取决于短板以及底部的宽度 , 因此我们需要想办法让短板变得更大 , 所以说移动长板水槽的总面积一定会减小
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxArea(int[] height) {
        int res=0;
        int i=0,j=height.length-1;
        while(i<j){
            res=height[i]<height[j]?Math.max(res,(j-i)*height[i++]):Math.max(res,(j-i)*height[j--]);
        }
        return res;
    }
}