第314场周赛

一、使数组中所有元素都等于0

把数组存储到list里面，每次list其余位置的值 - list.get(0),直到list长度为0

class Solution {
    public int minimumOperations(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for(int num : nums) {
            if(num != 0) {
                list.add(num);
            }
        }
        Collections.sort(list);
        int res = 0;
        
        while(list.size() != 0) {
            int min = list.get(0);
            res++;
            for(int i = 1; i < list.size(); i++) {
                if(list.get(i) - min == 0) {
                    list.remove(i);
                    i--;
                }else{
                    list.set(i, list.get(i) - min);
                }
            }
            list.remove(0);
        }
        
        return res;
    }
}
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

二、分组的最大数量

可以按照大小排序，后一组长度 = 前一组长度 + 1，如果符合条件res++
这里可以不排序，直接根据长度计算

class Solution {
    public int maximumGroups(int[] grades) {
        int res = 0;
        int len = grades.length;
        int pre = 0;
        
        while(len >= pre + 1) {
            res++;
            len -= (pre + 1);
            pre = pre + 1;
        }
        
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三、找到离给定两个节点最近的节点

class Solution {
	/**
         * 如果两个map中有相同的key，说明node1和node2有可以到达的相同的点，取出node1和node2到这个节点的较大值
         * result存储符合条件的较大值中的最小值
         * index存储结果的节点
         */
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int len = edges.length;
        Map<Integer, Integer> map1 = getMap(edges, new boolean[len], node1);
        Map<Integer, Integer> map2 = getMap(edges, new boolean[len], node2);
        int result = Integer.MAX_VALUE;
        int index = -1;

        for(Map.Entry<Integer, Integer> entry : map1.entrySet()) {
            int key = entry.getKey();
            if(map2.containsKey(key)) {
                int curr = Math.max(map2.get(key), entry.getValue());
                if(result > curr) {
                    result = curr;
                    index = key;
                }
            }
        }

        return index;
    }

    public Map<Integer, Integer> getMap(int[] edges, boolean[] visited, int node) {
        Map<Integer, Integer> map = new HashMap<>();
        int len = 0;
        while(!map.containsKey(node) && !visited[node]) {
            map.put(node, len);
            visited[node] = true;
            if(edges[node] == -1) {
                break;
            }else{
                node = edges[node];
                len++;
            }
        }
        return 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43

四、图中最长环

class Solution {
    boolean[] visited;
    public int longestCycle(int[] edges) {
        int result = -1;
        int len = edges.length;
        visited = new boolean[len];
        for(int i = 0; i < edges.length; i++) {
            if(!visited[i] && edges[i] != -1) {
                int curr = getMap(edges, i);
                if(curr != -1) {
                    result = Math.max(result, curr);
                }
            }

        }
        return result;
    }
    
	/**
     * 当从node节点开始遍历的时候，无论终点是否等于起始点node，当满足条件当前node节点在map中存在的时候，可以根据当前node节点第一次
     * 访问的时候在map中添加的顺序得到当前路径中环的长度
     *
     * visited数组保证每一个元素只被访问一次，因为一个点只有一个出边，所以就算当前节点不是环的起始点和终点，那么当前节点已经被遍历过，
     * 说明当前node节点的路径中的环已经被找出来了，就不需要再次访问
     * @param edges
     * @param node
     */
    public int getMap(int[] edges, int node) {
        Map<Integer, Integer> map = new HashMap<>();
        int len = 0;
        while(!map.containsKey(node)) {
            if(visited[node] || edges[node] == -1) return -1;
            map.put(node, len);
            len++;
            visited[node] = true;
            node = edges[node];
        }
        int pre = map.get(node);
        return map.size() - pre;
    }
}
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