找出合规工序
题目描述
工厂中有不同的工序，请按升序输出所有的合规工序。
合规工序：工序的所有的路径工序都会到达终点工序。终点工序不会指向任何工序。
所有终点工序都为合规工序。
输入
先输入 n，代表的工序的个数
接下来会有 n 行，第 i 行所代表的是第 i 个工序的下个工序
终点工序指向-1
示例
输入：
输出：
解释：
工序 5 和 6 为终点工序，即为合规工序
工序 2 和 4 开始的所有下游工序最终都指向终点工序，按照升序排列最终结果为 2，4，5，6
解析
看到这题，最初的想法是 dfs，但是发现吃力不讨好，也想过用并查集，但也不好做。最后用贪心解决了。
由题意得，合规工序的所有路径都会指向终点工序，且终点工序不会指向其他任何工序。那么可以从图的角度理解，图中只要有环，那么环中的所有节点（工序）都不是合规工序，因为这些工序的某些路经无法到达终点工序。
从终点工序倒推，所有终点工序都是合规工序。
如果有工序只指向了合规工序，且没有指向其他工序，那么这个节点的所有路径都可以到达终点工序，这个节点为终点工序。接下来重复以上步骤，直到无法推导为止。
其中图上环中的所有工序无法被进入这个流程，因为他们相互指向，始终存在不是合规工序的子节点。
参考
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
| public class Solution {
static int n;
static List<Integer>[] adj;
static Set<Integer> set;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
adj = new List[n];
set = new HashSet<>();
in.nextLine();
int end = -1;
for (int i = 0; i < n; i++) {
String[] temp = in.nextLine().split(" ");
adj[i] = new ArrayList<>(temp.length);
for (String s : temp) {
Integer val = Integer.parseInt(s);
if (val == -1) {
end = val;
set.add(i);
}
adj[i].add(val);
}
}
boolean p = true;
while(p) {
p = false;
for (int i = 0; i < n; i++) {
if(set.contains(i)) continue;
if (check(i)) {
set.add(i);
p = true;
}
}
}
List<Integer> ans = new ArrayList<>(set);
ans.sort(null);
for (Integer a : ans) {
System.out.print(a + " ");
}
}
private static boolean check(int i){
for (Integer j : adj[i]) {
if(!set.contains(j)) return false;
}
return true;
}
}
|
检查数字是否超过上限
题目描述
数字可以被分成 n 份（n ≥ 2），存在一个上限 x，检查分成的子数的乘积是否超过上限。
返回数字子数的乘积超过上限，返回 true，反之返回 false。
输入
输入 x 与 n 分别代表上限和数字
示例
输入： 161 14
输出： true
解释：
14 = 3 + 3 + 3 + 3 + 2
3 * 3 * 3 * 3 * 2 = 162 > 161
解析
由题意得，找出 num 的子数的最大乘积，从而判断是否超过上限。对于不同的数，不存在一个绝对最大分法，因此需要去搜索找到最大值。
递归搜索 + 保存计算结果 = 记忆化搜索
使用动态规划解决本题，因为题中存在明显的子结构问题，因而可以使用动态来推导。
dfs(i, j)表示的是求数字 i 的最大乘积，并返回 i * j。
转移公式： dfs(num, mul) = max{dfs(num - i, mul * i)}，其中 1 ≤ i ≤ num
当 i = num 时，即为 num * mul
存储其中的最大值，下次碰到时直接返回。
参考
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 {
static Map<Long, Long> memo = new HashMap<>();
public static void main(String[] args) throws ClassNotFoundException, InstantiationException, IllegalAccessException {
Scanner in = new Scanner(System.in);
long upLimit = in.nextInt();
long sum = in.nextInt();
long ans = dfs(sum, 1);
System.out.println(ans > upLimit);
}
private static long dfs(long num, long mul){
if(num == 0 || num == 1) return mul;
if(memo.containsKey(num)) return memo.get(num) * mul;
long max = num * mul;
for(int i = 1; i < num; i++){
max = Math.max(max, dfs(num - i, mul * i));
}
memo.put(num, max / mul);
return max;
}
}
|
