Heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class demo {
    public static void main(String[] args) {
        // 默认小根堆
        PriorityQueue<Integer>heap1 = new PriorityQueue<>();
       Collections.addAll(heap1,1,2,3,4);
       heap1.stream().forEach(s-> System.out.println(s));

        // 通过传入比较器 使其成为大根堆
        // 比较器使用lambda 进行简化
        PriorityQueue<Integer>heap2 = new PriorityQueue<>((o1,o2) -> o2 - o1);
        Collections.addAll(heap2,9,2,3,4);
        heap2.stream().forEach(s-> System.out.println(s));

    }
}


ArrayList 初始化

最简单的直接初始化

1
ArrayList<Integer> arrayList = new ArrayList<>();

赋初始值初始化

1
ArrayList<Integer>arrayList = new ArrayList<>(Arrays.asList(1,3,4,5));

Arrays类相关

这些主要处理 java 中int[] 和 Integer 不好转换的问题
比如题目要求返回int[] 但实际算法中需要用到动态数组 ArrayList

1
2
3
4
5
6

/**
 *  主要应对场景:
 *  要返回的数组长度 只占算法操作后数组长度部分的情况
 */
Arrays.copyOfRange(原数组，开始拷贝下标 , 拷贝结束下标); // 左开右边

java二分

建议手动实现

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
public class demo {
    public static void main(String[] args) {
        int [] arr = new int[]{1,3,3,3,5,5,7,8,10};
        var t1 = binary1(3,arr);
        var t2 = binary2(3,arr);
        var t3 = binary1(2,arr);
        var t4 = binary2(2,arr);

        // 输出 1
        System.out.println(t1);
        // 输出 3
        System.out.println(t2);
        // 输出 1
        System.out.println(t3);
        // 输出 0
        System.out.println(t4);
    }

    // 要查找的数 以及数组
    // 这种写法 相同元素时返回的是 第一个数的索引  即第一个>= x 的数
    // 如果没找到 那么 返回的是第一个大于的这个数的位置 这个相对来说会更符合平常元素的逻辑
    // 这种写法用的最多
    public static int binary1(int x,int [] arr){
        int l = 0 , r = arr.length - 1;
        while (l < r){
            int mid = l + r >> 1;
            if(arr[mid] >= x){
                r = mid;
            }else{
                l = mid + 1;
            }
        }

        return l;
    }

    // 这种写法 相同元素时 返回最后一个数的索引 即第一个 < x + 1 的数
    // 如果没找到 返回的是 返回的是第一个小于这个数的位置
    public static int binary2(int x,int [] arr){
        int l = 0 , r = arr.length - 1;
        while (l < r){
            int mid = l + r  + 1 >> 1;
            if(arr[mid] <= x){
                l = mid ;
            }else {
                r = mid - 1;
            }
        }
        return l;
    }

}


实在上面的记不住 再用库函数(但也可以直接切c++)

二分库函数(不推荐使用)

基于Array库实现
Arrays.binarySearch 返回的是 索引下标

方法的返回值有几种：
1、找到的情况下：如果key在数组中，则返回搜索值的索引。
2、找不到的情况下：
[1] 搜索值不是数组元素，且在数组范围内，从1开始计数，得 “- 插入点索引值”；

  • [2] 搜索值是数组元素，从0开始计数，得搜索值的索引值；
  • [3] 搜索值不是数组元素，且大于数组内元素，索引值为 – (length + 1);
  • [4] 搜索值不是数组元素，且小于数组内元素，索引值为 – 1。
1
2
3
4
int [] arr = new int[]{1,3,5,7};
var t = Arrays.binarySearch(arr,7);
var t = Arrays.binarySearch(arr,8);
var t = Arrays.binarySearch(arr,2);

上面这种情况
key = 7 搜到了直接返回下标3
key = 8 不是数组元素 且大于数组元素 返回 -(length + 1) 即 -5
key = 2 返回 -2 (因为从1开始计数) 那么实际插入的位置应该是 -(-2 + 1) = 1

1
2
int [] arr = new int[]{1,3,3,3,3,3,3,5,5,7};
var t = Arrays.binarySearch(arr,3);

上面情况 返回3的位置是随机的

所以Java的二分库不太好用 也不太推荐用