集合框架

各种概念什么的就不讲了，主要是在题目中的体现

使用的一些细节

  1. 数组有Arrays类提供排序方法，集合用Collections 自定义排序的话只支持包装类，默认都是升序

    1
    2
    //可以通过拉姆达表达式简写
    Collections.sort(list,(o1,o2) -> o2-o1);

  2. isEmpty()方法，如果集合null都话会报空指针异常

例题讲解

  1. 实现对输入的值去重并排序

    直接使用set集合去重后转换为lsit集合排序，set中是无序的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    final Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); // 得到要遍历的数组长度
    int[] f = new int[n];
    Set<Integer> set = new HashSet<>();
       
    for (int i = 0; i < n; i++) {
        f[i] = sc.nextInt();
        set.add(f[i]); // 直接将元素添加到set中去重
    }
       
    // 将set转换为list进行排序
    ArrayList<Integer> list1 = new ArrayList<>(set);
    Collections.sort(list1); // 升序排序
       
    // 打印结果
    for (int x : list1) {
        System.out.print(x + " ");
    }
       
    sc.close(); // 关闭Scanner

  2. 计算出现频率最大的数，如果有多个数，从小到大排序

    利用map集合，将出现的数作为键，在判断下一次的数键是否存在，存在值++，第一次存入的时候值都唯一，遍历键值对找出值最大的键

    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
        Scanner in = new Scanner(System.in);
        final int n = in.nextInt();
        int [] arr = new int [n];
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<n;i++){
            arr[i] = in.nextInt();
            //一种方法
    //        if(map.containsKey(arr[i])){
    //            map.put(arr[i],map.get(arr[i])+1);
    //        }else{
    //            map.put(arr[i],1);
    //
    //        }
            //调用api的一种方法 //默认是1 如果有这个键则加1
            map.put(arr[i],map.getOrDefault(arr[i],1)+1);
        }
        // 找到最大频率
        int maxFrequency = Collections.max(map.values());

        List<Integer> list = new ArrayList<Integer>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(map.get(entry.getKey())==maxFrequency){
                list.add(entry.getKey());
            }
        }
        Collections.sort(list);
        for(int x:list){
            System.out.print(x+" ");
        }

  3. 判断括号串是否合法

    利用栈的结构来解决这个问题，先将所有的左括号都入栈，之后就是右括号的情况，如果栈不为空就弹出一个左括号，也就是有左括号且有右括号能对应的上的情况，如果为空则跳出循环，不合法，

    在判断有没有多余左括号，有的话也不合法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    Stack<Character> stack2 = new Stack<>();
    final Scanner sc = new Scanner(System.in);
    final String str = sc.next();
    final char[] charArray = str.toCharArray();
    boolean flag = true;
    for(char c : charArray){
        if(c == '('){
            stack2.push(c);
        }else{
            if(!stack2.isEmpty()){
                stack2.pop();
            }else{
                flag = false;
                break;
            }
        }
    }
    //有多余的括号
    if(!stack2.isEmpty()) flag = false;
    if(flag) System.out.println("yes");
    else System.out.println("no");

  4. 按照数位和排序

    这题我感觉挺有意思的，按照数位之和给数排序，两个数数位之和不同 数位和小的排在前面，数位和相等数值小的排在前面，给定正整数n,m 1到n采用这种方法排序，排在第m个的元素是多少 输入 13 5 输出 3

    利用二维数组模拟键值对 a[i][0]为数值，a[i][1]为数位和，在通过二维数组的排序得到答案

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] arr = new int[n][2];
            for (int i = 0; i < n; i++) {
                arr[i][0] = i+1;
                //直接通过+转换为字符串
                String str = arr[i][0]+"";
                for (int j = 0; j < str.length(); j++) {
                    arr[i][1] += str.charAt(j) - '0';
                }
                //这个二维数组的结构就相当于键值对
    //            System.out.println(arr[i][0]+":"+arr[i][1]);
           }
            //a b 表达的就是二维数组的一行 a[1] 里面放的就是数位和 数位和相同按照数值升序 数位和不同按照数位和升序
            Arrays.sort(arr,(a,b)-> a[1]==b[1]?a[0]-b[0]:a[1]-b[1]);
            System.out.println(arr[m-1][0]);

  5. 相邻数字首尾相接 组成一个最大数

    有n个正整数，将它们连接成一排，相邻数字首尾相接 组成一个最大数 输入 13 312 343 输出 34331213 ，

    通过将数字转换为字符串在通过字符串拼接的操作，进行字典序的比较，但是在比较的过程中要记得比较的字符串长度要相等

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    final Scanner sc = new Scanner(System.in);
    final int n = sc.nextInt();
    String[] a = new String[n];
    for (int i = 0; i < n; i++) {
        a[i] = sc.next();
       
    }
    //字符串数字比较大小 长度相等在进行字典序的比较
    Arrays.sort(a,(a1,a2)->(a2+a1).compareTo(a1+a2));
    StringBuilder str = new StringBuilder();
    for(String s : a){
        str.append(s);
    }
    System.out.println(str);

排序算法

感觉能明白又感觉明白不了

冒泡排序

最简单的排序算法 通过比较相邻两个元素的大小进行排序 时间复杂度为O(n2)

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
import java.util.*;
public class BubblingSorting {
	public static void main(String[] args) {
/* 题目 第一行输入数字n  输入的第二行包括n个数字，对输入的数字进行排序
 * 1<=n<=1000,1<=a[i]<=10e6
 * */
		
		//采用冒泡排序的方式解决  依次比较相邻的两个元素
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}
		for(int i = 0; i < a.length; i++) {
			for(int j = i+1; j < a.length; j++) {
				if(a[i] > a[j]) {
					int t = a[i];
					a[i] = a[j];
					a[j] = t;
				}
			}
		}
		for(int i = 0; i<a.length; i++) {
			System.out.print(a[i] + " ");
		}

	}

}

选择排序

找到最小元素放在首尾 在向下寻找放到已排序的末尾

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 0; i < a.length-1; i++) {
	int min = i;
	for(int j = i+1 ; j < a.length; j++) {
		if(a[j] < a[min])
			//记录当前最小元素的下标
			min = j;
	}
	if(i != min) {
		int t = a[i];
		a[i] = a[min];
		a[min] = t;
	}
}

插入排序

将第一个元素视为以排序元素 从第一个元素后面取出数字 将取出元素与已排序元素从后向前依次比较

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i < a.length; i++) {
	int t = a[i];
	int j = i;
	while(j > 0 && t < a[j-1]) {
		a[j] = a[j-1];
		j--;
	}
	//注意这里j已经是--过了
	if(j != i) 
		a[j] = t;
}

快速排序

时间复杂度小 数据越无序 性能越好

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
	//快排 采用递归实现 将要排序的分为左右两部分

	QuickSort(a,0,n-1);
	for(int i =0;i < a.length; i++)
		System.out.print(a[i] + " ");
	
}
private static  int[] QuickSort(int[]arr ,int left,int right) {
		if(left < right) { 
			int p = patition(arr,left,right);
			QuickSort(arr,left,p-1);
			QuickSort(arr,p+1,right);
		}
		return arr;

}
private static int patition(int []arr,int left,int right) {
	int p = left ; 
	int index = p + 1;
	for(int i = index; i <= right; i++) {
		if(arr[i] < arr[p]) {
			swap(arr,i,index);
			index++;
		}
	}
	swap(arr,p,index-1);
	return index-1;
}
private static void swap(int []arr,int i,int j) {
	int t = arr[i];
	 arr[i] = arr[j];
	 arr[j] = t;
}

桶排序

适用于数据量比数据的值域要大或者一样时的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
//桶排序 当排序的总数大于值域时，才比较适合用桶排序 O(n)  
//不用比较相当于一个数对应一个桶
public class bucketSort {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int MAX = n + 1;
		int[] bucket = new int[MAX];
		int[] arr = new int[n];
		for(int i =0; i < n; i++) {
			arr[i] = sc.nextInt();
			bucket[arr[i]]++;
		}
		for(int i = 0; i < n; i++) {
				for(int j = 0; j < bucket[i] ; j++) {
					System.out.print(i + " ");
				}
		}