leetcode 2225. Find Players With Zero or One Losses（找出全赢或只输一次的玩家）

You are given an integer array matches where matches[i] = [winneri, loseri] indicates that the player winneri defeated player loseri in a match.

Return a list answer of size 2 where:

answer[0] is a list of all players that have not lost any matches.
answer[1] is a list of all players that have lost exactly one match.
The values in the two lists should be returned in increasing order.

Note:

You should only consider the players that have played at least one match.
The testcases will be generated such that no two matches will have the same outcome.

Example 1:

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

matches数组中的每个子数组代表 [ 赢家，输家 ],
找出只赢过的玩家 和 只输过一次的玩家 保存在结果list中的[0], [1] list内，
玩家要升序排列。

思路：

首先声明一下几个点，
全赢的玩家不用管它赢几次，只要没输过就行。
只输过一次的玩家是真的只输过一次，输两次赢一次也算输两次，输一次赢一次也算输一次，
是不可抵消的（亲自验证过…）。
所以不需要考虑记录赢的次数，只需要记录赢的玩家有没有输过。

方法一：
用hashSet记录赢家，如果赢家出现在输的名单上，就移除它。
注意要把所有玩家保存之后再看有没有出现在输家名单上，不能边加边check.
因为玩家并不是按顺序出现的，假如前面删过一次，它不存在了，后面又出现了，这时是加还是不加呢。
注意还要给玩家排序。

public List<List<Integer>> findWinners(int[][] matches) {
    HashSet<Integer> set_winner = new HashSet<>();
    HashMap<Integer, Integer> map_loser = new HashMap<>();
    List<Integer> arr_winner = new ArrayList<>();
    List<Integer> arr_loser = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    
    for(int[] match : matches) {
        set_winner.add(match[0]);            
        map_loser.put(match[1], map_loser.getOrDefault(match[1], 0)+1);
    }
    
    for(Integer winner : set_winner) {       
        if(!map_loser.containsKey(winner)) arr_winner.add(winner);
    }
    
    for (Map.Entry<Integer, Integer> entry : map_loser.entrySet()) {
        if(entry.getValue() == 1) arr_loser.add(entry.getKey());
    }
    Collections.sort(arr_winner);
    Collections.sort(arr_loser);
    
    res.add(arr_winner);
    res.add(arr_loser);
    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

方法二：
可以发现玩家只处于4种状态，第1种：空白还没处理(0)，第2种：只赢过(1)，
第3种：只输过一次(2)，第4种：输过多次(3)。
也不需要赢家输家单独保存，而是在数组上直接覆盖。
看下状态转移：
空白(0)：赢 -> 赢(1), 输 -> 输一次(2)
赢(1)： 赢 -> 不变(1), 输 -> 输一次(2)
输(2,3)：赢 -> 不变(2), 输 -> 输多次(3)

因为玩家是作为数组下标出现的，肯定是升序，所以最后不需要排序。

public List<List<Integer>> findWinners(int[][] matches) {
    int[] result = new int[100001];
    List<Integer> arr_winner = new ArrayList<>();
    List<Integer> arr_loser = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    int max_res = 0;
    final int WIN_NO_LOSE = 1;
    final int LOSE_ONCE = 2;
    final int LOSE_MORE = 3;
    
    for(int[] match : matches) {
        if(result[match[0]] == 0) result[match[0]] = WIN_NO_LOSE;
        result[match[1]] = result[match[1]] <= WIN_NO_LOSE ? LOSE_ONCE : LOSE_MORE;
        max_res = Math.max(max_res, Math.max(match[0], match[1]));
    }
    
    for(int i = 0; i <= max_res; i++) {
        if(result[i] == WIN_NO_LOSE) arr_winner.add(i);
        if(result[i] == LOSE_ONCE) arr_loser.add(i);
    }
    
    res.add(arr_winner);
    res.add(arr_loser);
    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