算法学习-双指针、离散化、合并区间

本文最后更新于：January 3, 2022 pm

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

双指针

应用

1.统计单词数量

将Vector换成Set即可实现统计不同单词的数量。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package acmtest;

import java.io.*;
import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		String str ;
		Vector<String> vStrings = new Vector<String>();
		str = sc.nextLine();
		int len = str.length();
		for(int i=0;i<len;++i) {
			int j = i;
			while(j<len&&str.charAt(j)!=' ') j++;
			vStrings.add(str.substring(i, j));
			i=j; //j当前处于空格处，所有还需要将i进行加1
		}
		cout.println(vStrings.size());
		cout.flush();
		
		closeAll();
		
	}
	
	public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

输入输出：

1
2
adsf wefaf fewaaef as fsd fwe far gdzsrwea ea
9

2.最长连续不重复子序列

题目链接1
题目链接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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package acmtest;

import java.io.*;
import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		String s1;
		s1=sc.next();
		int len = s1.length();
		int ans = 0;
		int[] flag = new int[100010];
		for(int i=0,j=0;i<len;++i) {
			flag[(int)s1.charAt(i)]++;
			while(flag[(int)s1.charAt(i)]>1) {
				flag[(int)s1.charAt(j)]--;
				j++;
			}
			ans=Math.max(ans, i-j+1);
		}
		cout.println(ans);
		cout.flush();
		
		closeAll();
		
	}
	
	public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

输入输出：

1
2
122356
4

数据离散化

离散化的步骤：

  • 1、排序

  • 2、去重

  • 3、索引

合并区间

  • 首先把数组排序，先按照起点升序排列，如果起点位置相同，按照结尾升序排序。

  • 设置start 和 end 为当前区间的开始和结尾。

  • 遍历数组，如果下一个的起点小于当前区间的结尾，那么就说明这两个区间有重叠，要进行合并，所以要更新结尾。

  • 如果下一个的起点，大于当前区间的结尾，说明这两个区间没有重叠。之前start，end是一个单独的区间，所以保存起来。保存之后，重新设置strat和end，继续向后进行合并。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    //    cin.ordinaryChars('0', '9') ;
    //    cin.wordChars('0', '9');
    public static void main(String[] args) throws Exception {

        int[][] a = new int[][]{{1, 3}, {2, 6}, {8, 10}, {14, 17}, {12, 15}};
        Arrays.sort(a, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
        List<int[]> res = new ArrayList<>();
        int start = a[0][0];
        int end = a[0][1];
        for (int i = 1; i < a.length; ++i) {
            if (a[i][0] <= end) { 
                end = Math.max(a[i][1], end);
            } else {
                res.add(new int[]{start, end});
                start = a[i][0];
                end = a[i][1];
            }
        }
        res.add(new int[]{start, end});
        int[][] ans = new int[res.size()][2];
        System.out.println("单独区间个数为：" + res.size());
        for (int i = 0; i < res.size(); ++i) {
            ans[i] = res.get(i);
        }
        System.out.println("区间分别是:");
        for (int i = 0; i < ans.length; ++i) {
            System.out.println(ans[i][0] + " " + ans[i][1]);
        }
        closeAll();
    }

    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }

    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }

    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }

    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }

    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

输入输出：

1
2
3
4
5
单独区间个数为：3
区间分别是:
1 6
8 10
12 17