算法刷题Java技巧

Bertha 。 2024-03-26 13:16 157阅读 0赞

#### 文章目录 ####

*  1. 大根堆、小根堆
 *  2. 二维数组排序
 *  3.一维数组int\[\]排序
 *  4. 最大值最小值
 *  5. Map的便捷方法
 *  6. 栈的实现
 *  7. 数组默认值
 *  8. 异或
 *  9. Arrays
 *  10. JAVA的ArrayDeque,一个数据结构直接搞定栈队列

## 1. 大根堆、小根堆 ##

java可用优先队列 PriorityQueue  
在构造时就指定比较器即可

// 大根堆 即降序
     PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);

插入元素 add(E e) offer(E e)  
peek()/element() 队头元素  
poll()/remove() 弹出队头元素

## 2. 二维数组排序 ##

*  ① 实现Comparator接口 ：匿名内部类实现

int[][] arr = new int [n][2];
    		// 按照第二个元素升序排序
            Arrays.sort(arr,new Comparator<int[]>() {
        
                @Override
                // 如果返回值大于0，则交换两元素
                public int compare(int[] o1, int[] o2) {
        
                    return o1[1]-o2[1];
                }
            });

再补一个，先按第一列升序排序，若第一列相等，再按第二列升序排序

int[][] arr = new int [n][2];
    		// 按照第二个元素升序排序
            Arrays.sort(arr,new Comparator<int[]>() {
        
                @Override
                // 如果返回值大于0，则交换两元素
                public int compare(int[] o1, int[] o2) {
        
                	if(o1[0] == o1[1]){
        
                		return o1[1]-o2[1];
                	}
                	return o1[0]-o2[0];
                }
            });

*  ② lambda表达式实现

Arrays.sort(arr,(a,b)-> a[1]-b[1]);
    
     Arrays.sort(arr,(a,b)-> {
        
                if(a[0] == b[0]){
        
                    return a[1] - b[1];
                }
                return a[0]-b[0];
            });

## 3.一维数组int\[\]排序 ##

由于Arrays.sort里面的比较器只能用Integer，int\[\]数组是不可以的，所以只有2种方法

int[] nums = new int[]{
        ...};
    nums = IntStream.of(nums)
    		     .boxed()
    		     .sorted((o1, o2) -> o2-o1)
    		     .mapToInt(Integer::intValue).toArray();

或者自定义个List

List<Integer> list = new ArrayList<>();
            for (int num : nums) {
        
                list.add(num);
            }
    
            list.sort((a, b) -> b-a);

如果数组元素是Integer，直接

Arrays.sort(arr,(a, b) -> b-a);

## 4. 最大值最小值 ##

int min=Integer.MIN_VALUE;
    int max=Integer.MAX_VALUE;

## 5. Map的便捷方法 ##

> Map.getOrDefault(key，默认值)； 没有值就赋默认值  
> Map.putIfAbsent(key, value) 只有key不存在的时候才会覆盖  
> a = Map.computeIfAbsent(key, value) 返回map中当前key对应的值，即若key存在，返回旧值，key不存在，返回新值
> 
> 更快捷的  
> 比如如果pre的key存在，对应value+1,如果不存在，新建key为pre，value=1  
> 原本需要这样写，  
> map.put(pre,map.getOrDefault(pre,0)+1);  
> 但现在：

map.merger(pre,1,Integer::sum);
    如果没有pre的key，value为1，如果有，就相加
    或者 
    map.merge(pre,1,(o1,o2)-> o1+o2);  o1老数据 o2新数据

## 6. 栈的实现 ##

Deque<Integer> stack = new LinkedList();
    stack.peek(); 查看栈顶元素
    stack.pop(); 弹出栈顶元素
    stack.push(); 放入栈顶
    stack.isEmpty(); 栈是否为空

## 7. 数组默认值 ##

Arrays.fill(result,-1);//默认全部初始化为-1

## 8. 异或 ##

> 任何元素异或 0 都等于自己 x^0=x  
> 任何元素异或自己都等于0 x^x=0  
> 异或有交换律和结合律

// 用异或实现两个数的交换
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

## 9. Arrays ##

*  1）Arrays.toString()

int[] a = {
        1,2,3,4,5};
    System.out.println(Arrays.toString(a));
    // 输出格式：[1,2,3,4,5]

2）Arrays.sort()

*  Arrays.sort(数组名) 默认升序
 *  Arrays.sort(数组名，起始下标，结束下标) 左闭右开原则
 *  降序重写lamb表达式只能用包装类

1.  Arrays.equals()  
    比较两个数组内容是否相等
2.  Arrays.binarySearch()  
    在数组中查找元素  
    使用的前提是数组有序

> int Arrays.binarySearch( Datatype\[\], Datatype key)  
> // 若找到，则返回此值的下标， 若没找到，返回 -插入点-1；

5）Arrays.copyOf()  
第一个参数是原数组，第二个参数是拷贝长度，返回值是将原数组拷贝一份返回

## 10. JAVA的ArrayDeque,一个数据结构直接搞定栈队列 ##

注意：ArrayDeque无法插入NULL,若需要插入NULL使用LinkedList  
当作栈

> pop() 移除栈顶元素  
> peek() 获取栈顶元素  
> push() 添加栈顶元素

当作队列

> add() 队列尾部添加元素  
> offer() 队列尾部添加元素，返回是否成功  
> poll()/remove() 删除队列第一个元素 无元素poll()返回null remove()报异常  
> peek()/element() 获取队列第一个元素

通用操作

> addFirst() 在数组前面添加元素  
> addLast() 在数组后面添加元素  
> pollFirst()/removeFirst() 删除第一个元素，并返回删除元素的值  
> pollLast()/removeLast() 删除最后一个元素，并返回删除元素的值  
> getFirst() 获取数组第一个元素  
> getLast() 获取数组最后一个元素  
> offerFirst() 在数组前面添加元素,返回是否成功  
> offerLast() 在数组后面添加元素,返回是否成功

其他操作

> isEmpty() 是否为空  
> size() 容量  
> contains() 是否存在该元素