devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯JAVA-31.双指针、离散化、合并区间_蓝桥杯离散化

作者：知新_RL | 2024-04-21 03:58:32

赞

踩

蓝桥杯离散化

个人博客
www.tothefor.com
蓝桥杯复习知识点汇总

目录

双指针

应用

1.统计单词数量

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

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
  • 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

输入输出：

adsf wefaf fewaaef as fsd fwe far gdzsrwea ea
9

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

题目链接1
题目链接2

连续是位置连续！

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
  • 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

输入输出：

122356
4

  • 1
  • 2

数据离散化

离散化的步骤：

  • 1、排序

  • 2、去重

  • 3、索引

合并区间

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

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

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

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

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
  • 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

输入输出：

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

  • 1
  • 2
  • 3
  • 4
  • 5
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/460921
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号