LeetCode双指针

面试10.01 合并排序的数组

题目

分析

1.最简单的方法：a数组从m之后开始讲b的放进去之后排序即可。
2.双指针可以确定插入位置然后进行挪，这种方法复杂度会低很多。

代码

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
public class HeBingArr {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m=input.nextInt();
        int n=input.nextInt();
        int[] a=new int[n+m];
        int[] b=new int[n];
        for(int i=0;i<m;i++) {
            a[i] = input.nextInt();
        }
        for(int i=0;i<n;i++) {
            b[i] = input.nextInt();
        }
        merge(a,m,b,n);
        System.out.println(Arrays.toString(a));
    }

    public static void merge(int[] a, int m, int[] b, int n) {
        int j=0;
        for(int i=m;i<m+n;i++){
            a[i]=b[j++];
        }
        Arrays.sort(a);
    }

}

结果

面试10.09 排序矩阵查找(双指针控制行和列)

题目

分析

1. 设置h和l双指针，从第0行和第m-1列开始，控制范围满足：h<matrix.length&&l>=0
2. 通过while循环然后有三种情况：
    2.1 如果当前值比target小： 说明这行前面的都比target小 就换下一行 h++
    2.2 如果当前值比target大： 说明这列下面的都比target大 就换前一行 l--
    2.3 如果相等就直接返回true  所以外面方法默认返回就写成false

代码

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
public class ShengXu {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m=input.nextInt();
        int n=input.nextInt();
        int[][] a=new int[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                a[i][j] = input.nextInt();
            }
        }
        int target=input.nextInt();
        System.out.println(searchMatrix(a,target));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0){ //一定要有判断数组是否存在 不然后面的l这个指针就会异常
            return false;
        }
        int h=0;  //行指针
        int l=matrix[0].length-1; //列指针
        while(h<matrix.length&&l>=0){
            if(matrix[h][l]==target){
                return true;
            }
            if(matrix[h][l]<target){
                h++;  //这行前面的都比这个小 换下一行
            }else{
                l--; //这列下面的都比这个大 所以换前一列
            }
        }
        return false;
    }

}

结果

面试16.06 最小差(ab排序后指针控制移)

题目

分析

1. 主要是先将a和b排序之后我们就可以双指针进行移动
2. 思路：
    int diff = a[i] - b[j]
    如果 diff < 0 ，表示 a[i] 小于 b[j] ，a 尽可能接近 b，那么 i++
    如果 diff > 0 ，表示 a[i] 大于 b[j] ，b 尽可能接近 a，那么 j++

    特殊情况：
    a = {1,2,3,4,5}
    b = {6,7,8,9,10}
    如果 a 数组最大值比 b 数组最小值还小，那么 a 数组 i 会一直右移，直到到达边界 break
    */

代码

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
38
39
40
public class ZuiXiaoCha {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m=input.nextInt();
        int n=input.nextInt();
        int[] a=new int[m];
        int[] b=new int[n];
        for(int i=0;i<m;i++) {
            a[i] = input.nextInt();
        }
        for(int i=0;i<n;i++) {
            b[i] = input.nextInt();
        }
        System.out.println(smallestDifference(a,b));
    }

    public static int smallestDifference(int[] a, int[] b) {
        int alen = a.length;
        int blen = b.length;
    //a和b排序之后方便查找相近的值在哪
        Arrays.sort(a);
        Arrays.sort(b);
    //给最小值最好赋给其他特定值 如果是数组的内容有可能会报错
        int minVal = Integer.MAX_VALUE;
        int i=0;
        int j=0;
        while(i<alen&&j<blen){  //i和j分别是控制a和b数组的变化
           // 使用 long，防止 -2147483648 转正数后还是 -2147483648
            long cha=a[i]-b[j]; //计算出当前两个数组值的差
            minVal = (int)Math.min(Math.abs(cha), minVal); //minVal放的就是最后的结果
            if(cha<0){
                i++;  //a数组的比b数组的小  a数组的值要尽可能靠近b
            }else{
                j++;  //相反b的小 就要往a靠近
            }
        }
        return minVal;
    }

}

结果

面试17.11 单词距离(list集合存放出现位置然后比较)

题目

分析

使用两个list集合分别存放单词出现位置，然后循环遍历得到最小值

代码

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
38
39
public class DanCiLen {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m=input.nextInt();
        String[] a=new String[m];
        for(int i=0;i<m;i++) {
            a[i] = input.next();
        }
        String word1=input.next();
        String word2=input.next();
        System.out.println(findClosest(a,word1,word2));
    }

    public static int findClosest(String[] words, String word1, String word2) {
        int min=Integer.MAX_VALUE;
        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>();
        for(int i=0;i<words.length;i++)
        {
            if(word1.equals(words[i]))
            {
                list1.add(i); //list1存放单词word1出现的位置
            }
            if(word2.equals(words[i])) {
                list2.add(i); //list2存放单词word2出现的位置
            }
        }
        for(int j=0;j<list1.size();j++)
        {
            for(int k=0;k<list2.size();k++)
            {
                int cha=list1.get(j)-list2.get(k); //看
                min=Math.min(min,Math.abs(cha));
            }
        }
        return min;
    }

}

结果

面试17.21 接雨水(低动高不动/木桶效应由最短的决定)

题目

分析

1. 核心思路：缓存两端最大值，从最大值较小的一边进行储水结算、移动，并更新最大值。

代码

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
public class JieYuShui {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m=input.nextInt();
        int[] a=new int[m];
        for(int i=0;i<m;i++) {
            a[i] = input.nextInt();
        }
        System.out.println(trap(a));
    }

    public static int trap(int[] height) {
        int l=0;  //左指针
        int r=height.length-1; //右指针
        int lmax=height[l]; //左边最大值
        int rmax=height[r]; //右边最大值
        int res=0;
        while(l<r){
            if(lmax<rmax){   //左边低 算左边的高度
                res+=lmax-height[l];
                l++;
                lmax=Math.max(height[l],lmax); //更新左边最大值
            }else{  //右边低 算右边的高度
                res+=rmax-height[r];
                r--;
                rmax=Math.max(height[r],rmax);  //更新右边最大值
            }
        }
        return res;
    }

}

结果

面试48. 最长不含重复字符的子字符串(双指针/动态规划)

题目

分析

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/

1. 哈希表统计：遍历字符串s时，使用哈希表记为dic统计各字符最后一次索引位置。
2. 左边界i获取：遍历s[j]时，可通过访问哈希表dic[s[j]]获取最近的相同字符的索引i 。

代码

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
public class ZuiChangZiString {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s=input.next();
        System.out.println(lengthOfLongestSubstring(s));
    }

    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
		// getOrDefault代表当哈希表包含键key时返回对应value，不包含时返回默认值default。
            int left = map.getOrDefault(s.charAt(j),-1); 

            map.put(s.charAt(j), j); // 更新哈希表(将对应的字母和下标放入)

            if(tmp<(j-left)){
                tmp++;
            }else{
                tmp=j-left;
            }
            res = Math.max(res, tmp); // res一直是每一次变化之后的最大值
        }
        return res;
    }

}

结果

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:LeetCode双指针

文章作者:Larkkkkkkk

发布时间:2020年06月14日 - 12时28分

最后更新:2020年06月15日 - 17时26分

原始链接:https://larkkkkkkk.github.io/2020/06/14/LeetCode%E5%8F%8C%E6%8C%87%E9%92%88/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 面试10.01 合并排序的数组
    1. 1.1. 题目
    2. 1.2. 分析
    3. 1.3. 代码
    4. 1.4. 结果
  2. 2. 面试10.09 排序矩阵查找(双指针控制行和列)
    1. 2.1. 题目
    2. 2.2. 分析
    3. 2.3. 代码
    4. 2.4. 结果
  3. 3. 面试16.06 最小差(ab排序后指针控制移)
    1. 3.1. 题目
    2. 3.2. 分析
    3. 3.3. 代码
    4. 3.4. 结果
  4. 4. 面试17.11 单词距离(list集合存放出现位置然后比较)
    1. 4.1. 题目
    2. 4.2. 分析
    3. 4.3. 代码
    4. 4.4. 结果
  5. 5. 面试17.21 接雨水(低动高不动/木桶效应由最短的决定)
    1. 5.1. 题目
    2. 5.2. 分析
    3. 5.3. 代码
    4. 5.4. 结果
  6. 6. 面试48. 最长不含重复字符的子字符串(双指针/动态规划)
    1. 6.1. 题目
    2. 6.2. 分析
    3. 6.3. 代码
    4. 6.4. 结果
,