15.设计哈希映射
题目链接：706. 设计哈希映射
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
实现 MyHashMap 类：
MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。
示例：
输入：
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”,
“get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出：
[null, null, null, 1, -1, null, 1, null, -1]
解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]
提示：
0 <= key, value <= 106
最多调用 104 次 put、get 和 remove 方法
题解：
方法：链表
class MyHashMap { private class Pair { private int key; private int value; public Pair(int key, int value) { this.key = key; this.value = value; } public int getKey() { return key; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } } private static final int BASE = 769; private LinkedList[] data; /** Initialize your data structure here. */ public MyHashMap() { data = new LinkedList[BASE]; for (int i = 0; i < BASE; ++i) { data[i] = new LinkedList<Pair>(); } } /** value will always be non-negative. */ public void put(int key, int value) { int h = hash(key); Iterator<Pair> iterator = data[h].iterator(); while (iterator.hasNext()) { Pair pair = iterator.next(); if (pair.getKey() == key) { pair.setValue(value); return; } } data[h].offerLast(new Pair(key, value)); } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { int h = hash(key); Iterator<Pair> iterator = data[h].iterator(); while (iterator.hasNext()) { Pair pair = iterator.next(); if (pair.getKey() == key) { return pair.value; } } return -1; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { int h = hash(key); Iterator<Pair> iterator = data[h].iterator(); while (iterator.hasNext()) { Pair pair = iterator.next(); if (pair.key == key) { data[h].remove(pair); return; } } } private static int hash(int key) { return key % BASE; } }
16.尽量减少恶意软件的传播
题目链接：924. 尽量减少恶意软件的传播
给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。
示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0
示例 2：
输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出：0
示例 3：
输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：1
提示：
n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] == 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length <= n
0 <= initial[i] <= n - 1
initial 中所有整数均不重复
题解：
方法：深度优先搜索 图 递归
class Solution { public int minMalwareSpread(int[][] graph, int[] initial) { int n = graph.length; boolean[] vis = new boolean[n]; boolean[] isInitial = new boolean[n]; int mn = Integer.MAX_VALUE; for (int x : initial) { isInitial[x] = true; mn = Math.min(mn, x); } int ans = -1; int maxSize = 0; for (int x : initial) { if (vis[x]) { continue; } nodeId = -1; size = 0; dfs(x, graph, vis, isInitial); if (nodeId >= 0 && (size > maxSize || size == maxSize && nodeId < ans)) { ans = nodeId; maxSize = size; } } return ans < 0 ? mn : ans; } private int nodeId, size; private void dfs(int x, int[][] graph, boolean[] vis, boolean[] isInitial) { vis[x] = true; size++; // 按照状态机更新 nodeId if (nodeId != -2 && isInitial[x]) { nodeId = nodeId == -1 ? x : -2; } for (int y = 0; y < graph[x].length; y++) { if (graph[x][y] == 1 && !vis[y]) { dfs(y, graph, vis, isInitial); } } } }
17.尽量减少恶意软件的传播 II
题目链接：928. 尽量减少恶意软件的传播 II
给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。
请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。
示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0
示例 2：
输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
输出：1
示例 3：
输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：1
提示：
n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] 是 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length < n
0 <= initial[i] <= n - 1
initial 中每个整数都不同
题解：
方法：并查集 图 哈希表
class UnionFind { private final int[] p; private final int[] size; public UnionFind(int n) { p = new int[n]; size = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; size[i] = 1; } } public int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } public boolean union(int a, int b) { int pa = find(a), pb = find(b); if (pa == pb) { return false; } if (size[pa] > size[pb]) { p[pb] = pa; size[pa] += size[pb]; } else { p[pa] = pb; size[pb] += size[pa]; } return true; } public int size(int root) { return size[root]; } } class Solution { public int minMalwareSpread(int[][] graph, int[] initial) { int n = graph.length; boolean[] s = new boolean[n]; for (int i : initial) { s[i] = true; } UnionFind uf = new UnionFind(n); for (int i = 0; i < n; ++i) { if (!s[i]) { for (int j = i + 1; j < n; ++j) { if (graph[i][j] == 1 && !s[j]) { uf.union(i, j); } } } } Set<Integer>[] g = new Set[n]; Arrays.setAll(g, k -> new HashSet<>()); int[] cnt = new int[n]; for (int i : initial) { for (int j = 0; j < n; ++j) { if (!s[j] && graph[i][j] == 1) { g[i].add(uf.find(j)); } } for (int root : g[i]) { ++cnt[root]; } } int ans = 0, mx = -1; for (int i : initial) { int t = 0; for (int root : g[i]) { if (cnt[root] == 1) { t += uf.size(root); } } if (t > mx || (t == mx && i < ans)) { ans = i; mx = t; } } return ans; } }
18.从双倍数组中还原原数组
题目链接：2007. 从双倍数组中还原原数组
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。
给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。
示例 1：
输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。
示例 2：
输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。
示例 3：
输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。
提示：
1 <= changed.length <= 105
0 <= changed[i] <= 105
题解：
方法：排序
class Solution { public int[] findOriginalArray(int[] changed) { int n = changed.length; Arrays.sort(changed); int[] cnt = new int[changed[n - 1] + 1]; for (int x : changed) { ++cnt[x]; } int[] ans = new int[n >> 1]; int i = 0; for (int x : changed) { if (cnt[x] == 0) { continue; } --cnt[x]; int y = x << 1; if (y >= cnt.length || cnt[y] <= 0) { return new int[0]; } --cnt[y]; ans[i++] = x; } return ans; } }
19.准时抵达会议现场的最小跳过休息次数
给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。
当你通过第 i 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。
例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。
然而，为了能准时到达，你可以选择 跳过 一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。
例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。
返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。
示例 1：
输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。
示例 2：
输入：dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5
小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) =
10 小时抵达会议现场。
示例 3：
输入：dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时参加会议。
提示：
n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 105
1 <= speed <= 106
1 <= hoursBefore <= 107
题解：
方法：动态规划
class Solution { public int minSkips(int[] dist, int speed, int hoursBefore) { int sumDist = 0; for (int d : dist) { sumDist += d; } if (sumDist > (long) speed * hoursBefore) { return -1; } int n = dist.length; int[][] memo = new int[n][n]; for (int[] row : memo) { Arrays.fill(row, -1); // -1 表示没有计算过 } for (int i = 0; ; i++) { if (dfs(i, n - 2, memo, dist, speed) + dist[n - 1] <= (long) speed * hoursBefore) { return i; } } } private int dfs(int i, int j, int[][] memo, int[] dist, int speed) { if (j < 0) { // 递归边界 return 0; } if (memo[i][j] != -1) { // 之前计算过 return memo[i][j]; } int res = (dfs(i, j - 1, memo, dist, speed) + dist[j] + speed - 1) / speed * speed; if (i > 0) { res = Math.min(res, dfs(i - 1, j - 1, memo, dist, speed) + dist[j]); } return memo[i][j] = res; // 记忆化 } }
20.组合总和
题目链接：39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
题解：
方法：枚举
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); dfs(0, target, candidates, ans, path); return ans; } private void dfs(int i, int left, int[] candidates, List<List<Integer>> ans, List<Integer> path) { if (left == 0) { // 找到一个合法组合 ans.add(new ArrayList<>(path)); return; } if (left < candidates[i]) { return; } // 枚举选哪个 for (int j = i; j < candidates.length; j++) { path.add(candidates[j]); dfs(j, left - candidates[j], candidates, ans, path); path.remove(path.size() - 1); // 恢复现场 } } }
方法：完全背包
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); int n = candidates.length; // 完全背包 boolean[][] f = new boolean[n + 1][target + 1]; f[0][0] = true; for (int i = 0; i < n; i++) { for (int j = 0; j <= target; j++) { f[i + 1][j] = f[i][j] || j >= candidates[i] && f[i + 1][j - candidates[i]]; } } List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); // 倒着递归，这样参数符合 f 数组的定义 dfs(n - 1, target, candidates, f, ans, path); return ans; } private void dfs(int i, int left, int[] candidates, boolean[][] f, List<List<Integer>> ans, List<Integer> path) { if (left == 0) { // 找到一个合法组合 ans.add(new ArrayList<>(path)); return; } // 无法用下标在 [0, i] 中的数字组合出 left if (left < 0 || !f[i + 1][left]) { return; } // 不选 dfs(i - 1, left, candidates, f, ans, path); // 选 path.add(candidates[i]); dfs(i, left - candidates[i], candidates, f, ans, path); path.remove(path.size() - 1); } }
21.组合总和 III
题目链接：216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 9
1 <= n <= 60
题解：
方法：枚举
class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(k); dfs(9, n, k, ans, path); return ans; } private void dfs(int i, int t, int k, List<List<Integer>> ans, List<Integer> path) { int d = k - path.size(); // 还要选 d 个数 if (t < 0 || t > (i * 2 - d + 1) * d / 2) { // 剪枝 return; } if (d == 0) { // 找到一个合法组合 ans.add(new ArrayList<>(path)); return; } for (int j = i; j >= d; j--) { path.add(j); dfs(j - 1, t - j, k, ans, path); path.remove(path.size() - 1); } } }
