文章目录

1600 皇位继承顺序 M1601.最多可达成的换楼请求 H 总结第208场周赛。一共两道题目。

---

1600 皇位继承顺序 M

是一道很巧妙的题目，其实变相考察了对于数据结构的理解，很多时候对于数据结构都是简单的调用。这道题仔细观察可以看出来，其实是一个树形结构。最后返回的结果其实是一颗二叉树的前序遍历。但是这里因为是多叉树，所以我们每个节点用一个List存储所有的人名。

class ThroneInheritance { String kingName; Map<String, List<String>> map = new HashMap<>(); Set<String> set = new HashSet<>(); public ThroneInheritance(String kingName) { this.kingName = kingName; map.put(kingName, new ArrayList<>()); } public void birth(String parentName, String childName) { map.get(parentName).add(childName); map.put(childName, new ArrayList<>()); } public void death(String name) { set.add(name); } public List<String> getInheritanceOrder() { List<String> ans = new ArrayList<>(); dfs(ans, kingName); return ans; } private void dfs(List ans, String kingName){ if (!set.contains(kingName))ans.add(kingName); for (String name:map.get(kingName)){ dfs(ans, name); } } }

---

1601.最多可达成的换楼请求 H

这道题好像本质上可以转换为二分图的匹配问题，但是题目给的数据范围比较小，因此其实可以通过DP的方法解决。我们可以用通过数位DP的方法解决。

因为我们只需要枚举出来所有能够出现的换房的组合，每次判断是否可以成功换房是很方便的，只要保证每个节点的出度等于入度即可。

class Solution { public int maximumRequests(int n, int[][] requests) { int m = requests.length; int N = 1<<m; int ans = 0; for (int i = 1; i<N ;i++){ int[] degree = new int[n]; int tmp = 0; // 计算每个节点在当前组合下的出度和入度。 for (int j = 0; j<m; j++){ if (((i>>j) & 1) == 1){ degree[requests[j][0]] -= 1; degree[requests[j][1]] += 1; tmp++; } } int tag = 0; for (int j = 0; j<n;j++){ if (degree[j] != 0){ tag = 1; break; } } if (tag == 0) ans = Math.max(tmp, ans); } return ans; } }