997.找到小镇的法官

✒解题思路：

  1. 判断出度和入度表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	public int findJudge(int N, int[][] trust) {
		int[] inDegree = new int[N + 1];
		int[] outDegree = new int[N + 1];
		for (int[] temp : trust) {
			inDegree[temp[1]]++;
			outDegree[temp[0]]++;
		}
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == N - 1 && outDegree[i] == 0) {
				return i;
			}
		}
		return -1;
	}
}

1387.将整数按权重排序

✒解题思路：

  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
class Solution {
	private Map<Integer, Integer> map = new HashMap<>();

	public int getKth(int lo, int hi, int k) {
		if (lo > hi) {
			return 0;
		}
		int[][] dp = new int[hi - lo + 1][2];
		for (int i = lo; i <= hi; i++) {
			dp[i - lo][0] = i;
			dp[i - lo][1] = getWeight(i);
		}
		Arrays.sort(dp, (a, b) -> {
			if (a[1] == b[1]) {
				return a[0] - b[0];
			} else {
				return a[1] - b[1];
			}
		});
		return dp[k - 1][0];
	}

	private int getWeight(int num) {
		if (num == 1) {
			return 0;
		}
		if (map.containsKey(num)) {
			return map.get(num);
		}
		int res = 0;
		if ((num & 1) == 1) {
			res = getWeight(num * 3 + 1) + 1;
		} else {
			res = getWeight(num / 2) + 1;
		}
		map.put(num, res);
		return res;
	}
}

207.课程表

✒解题思路：

  1. 找到邻接表找到度入度为0的点
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
class Solution {
	public boolean canFinish(int numCourses, int[][] prerequisites) {
		//邻接表
		List<List<Integer>> adjacency = new ArrayList<>();
		int[] inDegree = new int[numCourses];
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < numCourses; i++) {
			adjacency.add(new ArrayList<>());
		}
		for (int[] temp : prerequisites) {
			inDegree[temp[0]]++;
			adjacency.get(temp[1]).add(temp[0]);
		}
		for (int i = 0; i < numCourses; i++) {
			if (inDegree[i] == 0) {
				queue.add(i);
			}
		}
		while (!queue.isEmpty()) {
			int pre = queue.poll();
			numCourses--;
			for (int cur : adjacency.get(pre)) {
				if (--inDegree[cur] == 0) {
					queue.add(cur);
				}
			}
		}
		return numCourses == 0;
	}
}