系列文章

【英雄哥六月集训】第 01天:数组

【英雄哥六月集训】第 02天:字符串

【英雄哥六月集训】第 03天:排序

【英雄哥六月集训】第 04天:贪心

【英雄哥六月集训】第 05天: 双指针

【英雄哥六月集训】第 06天:滑动窗口

【英雄哥六月集训】第 07天:哈希

【英雄哥六月集训】第 08天:前缀和

【英雄哥六月集训】第 09天:二分查找

【英雄哥六月集训】第 10天: 位运算

【英雄哥六月集训】第 11天: 矩阵

【英雄哥六月集训】第 12天: 链表

【英雄哥六月集训】第 13天: 双向链表

【英雄哥六月集训】第 14天: 栈

【英雄哥六月集训】第 15天: 二叉树

【英雄哥六月集训】第 16天: 队列

【英雄哥六月集训】第 17天: 广度优先搜索

【英雄哥六月集训】第 18天: 树

【英雄哥六月集训】第 19天: 二叉树

【英雄哥六月集训】第 20天: 二叉搜索树

【英雄哥六月集训】第 21天: 堆(优先队列)

---

堆(优先队列)

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆是非线性数据结构，相当于一维数组，有两个直接后继。

一、 道路的最大总重要性

2285. 道路的最大总重要性

class Solution {
    class Node{
        int deg;
        int v;
        Node(){}

        Node(int v,int d){
            this.v=v;
            this.deg=d;
        }

        public boolean compareTo(Node o){
            return this.deg < o.deg;
        }

        public String toString(){
            return "Node[val="+v+",deg="+deg+"]";
        }
    }
   
    public long maximumImportance(int n, int[][] roads) {
        int[] deg = new int[50010];
        int[] val = new int[50010];
        int id = n;
        for(int i=0;i<roads.length; ++i){
            ++deg[roads[i][0]];
            ++deg[roads[i][1]];
        }
        PriorityQueue<Node> q = new PriorityQueue<Node>((na,nb)->nb.deg-na.deg);
        for(int i=0;i<n;++i){
            q.add(new Node(i,deg[i]));
        }
        System.out.println(q);
        while(!q.isEmpty()){
            Node node =q.remove();
            val[node.v]=id;
            --id;
        }
        long ans=0;
        for(int i=0;i<roads.length;++i){
            ans += val[roads[i][0]]+val[roads[i][1]];
        }
        return ans;

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

---

二、 最长快乐字符串

1405. 最长快乐字符串

class Solution {
    class Node{
        char ch;
        int cnt;
        Node(){}
        Node(char c,int cn){
            this.ch=c;
            this.cnt=cn;
        }

        public String toString(){
            return "["+this.ch+","+this.cnt+"]";
        }
    }
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<Node> q=new PriorityQueue<Node>((na,nb)->nb.cnt-na.cnt);
        if(a!=0){
            q.add(new Node('a',a));
        }
        if(b!=0){
            q.add(new Node('b',b));
        }
        if(c!=0){
            q.add(new Node('c',c));
        }
        StringBuilder ret = new StringBuilder();
        StringBuilder pre = new StringBuilder();
        while(!q.isEmpty()){
            Node n = q.remove();
            System.out.println("before q="+q);
            if(pre.toString().equals("aa") && n.ch == 'a' || pre.toString().equals("bb") && n.ch == 'b' || pre.toString().equals("cc") && n.ch == 'c'){
                System.out.println("pre="+pre+",n.ch="+n.ch);
                if(q.isEmpty()){
                    return ret.toString();
                }
                Node next = q.remove();
                ret.append(next.ch);
                if(--next.cnt!=0){
                    q.offer(next);
                }
                q.offer(n);
                pre = new StringBuilder();
                pre.append(next.ch);
            }
            else
            {
                ret.append(n.ch);
                pre.append(n.ch);
                if(pre.length()>2){
                    char pre2 = pre.charAt(pre.length()-2);
                    char pre1 = pre.charAt(pre.length()-1);

                    pre = new StringBuilder();
                    pre.append(pre2);
                    pre.append(pre1);
                }

                if(--n.cnt!=0){
                    q.offer(n);
                }

            }
            System.out.println("after q="+q);
        }
        return ret.toString();

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

三、 为高尔夫比赛砍树

675. 为高尔夫比赛砍树

class Solution {
    class Node{
        int x,y,h;
        Node(){}
        Node(int x,int y,int h){
            this.x=x;
            this.y=y;
            this.h=h;
        }
        public String toString(){
            return "["+this.x+","+this.y+","+this.h+"]";
        }
    }
    int[][] dir = new int[][]{
        {0,1},{0,-1},{1,0},{-1,0}
    };
    public int cutOffTree(List<List<Integer>> forest) {
        int m = forest.size();
        int n = forest.get(0).size();
        int i,j;
        PriorityQueue<Node> q = new PriorityQueue<Node>((na,nb)->na.h-nb.h);
        if(forest.get(0).get(0)==0){
            return -1;
        }
        for(i = 0; i<m; ++i){
            for(j=0; j<n; ++j){
                if(forest.get(i).get(j)>1){
                    q.add(new Node(i,j,forest.get(i).get(j)));
                }

            }
        }
        System.out.println(q);
        Node pre = new Node(0,0,forest.get(0).get(0));
        int ans = 0;
        while(!q.isEmpty()){
            
            Node now = q.remove();
            //System.out.println(now);
            int dis=bfs(m,n,forest,pre,now);
            //System.out.println(dis);
            if(dis == -1){
                return -1;
            }
            ans += dis;
            pre = now;
        }
        return ans;

    }
    public int bfs(int m,int n, List<List<Integer>> forest, Node start, Node end){
        int[][] hash = new int[51][51];
        for(int i=0;i<51;i++){
            for(int j=0;j<51;j++){
                hash[i][j]=-1;
            }
        }
        Queue<Node> d=new LinkedList<Node>();
        hash[start.x][start.y]=0;
        d.add(start);
        while(!d.isEmpty()){
            //System.out.println(q);
            Node now=d.poll();
            
            if(now.x == end.x && now.y == end.y){
                return hash[end.x][end.y];
            }
            System.out.println(d);
            Node next = new Node();
            
            for(int i=0;i<4;++i){
                next.x = dir[i][0] + now.x;
                next.y = dir[i][1] + now.y;
                if(next.x<0 || next.y<0 || next.x == m || next.y == n){
                    continue;
                }
                if(forest.get(next.x).get(next.y)==0){
                    continue;
                }
                if(hash[next.x][next.y]!=-1){
                    continue;
                }
                
                hash[next.x][next.y] = hash[now.x][now.y]+1;
                
                d.add(next);
                System.out.println(d);
            }
            System.out.println(d);
            

        }
        return -1;
    }
}
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

四、 分割数组为连续子序列

659. 分割数组为连续子序列

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer,PriorityQueue<Integer>> map = new HashMap<Integer,PriorityQueue<Integer>>();
        for(int x:nums){
            if(!map.containsKey(x)){
                map.put(x, new PriorityQueue<Integer>());
            }
            if(map.containsKey(x-1)){
                int prevLength = map.get(x-1).poll();
                if(map.get(x-1).isEmpty()){
                    map.remove(x-1);
                }
                map.get(x).offer(prevLength+1);
            } else {
            map.get(x).offer(1);
            }
            
        }
        Set<Map.Entry<Integer, PriorityQueue<Integer>>> entrySet = map.entrySet();
        for( Map.Entry<Integer, PriorityQueue<Integer>> entry: entrySet){
            PriorityQueue<Integer> queue = entry.getValue();
            if( queue.peek()<3){
                return false;
            }
        }
        return true;
    }

}
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

总结