本文共 2508 字,大约阅读时间需要 8 分钟。
最大整除子集的解法
给定一个由无重复正整数组成的集合 nums, 需要找出其中最大的整除子集。该子集中的每一对元素 (a, b) 必须满足 a % b == 0 或者 b % a == 0。如果存在多个满足条件的子集,可以返回任意一个。
import java.util.ArrayList;import java.util.Collections;import java.util.List;public class Solution { public ListlargestDivisibleSubset(List nums) { if (nums.isEmpty()) { return new ArrayList<>(); } // 排序使得较小的数字在前面 Collections.sort(nums); // dp[i] 表示以 nums[i] 结尾的最大整除子集的大小 int n = nums.size(); int[] dp = new int[n]; List result = new ArrayList<>(); for (int i = 0; i < n; i++) { dp[i] = 1; // 每个数至少自己组成一个子集 } int maxSize = 1; int maxValIndex = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums.get(i) % nums.get(j) == 0) { if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; } } } if (dp[i] > maxSize) { maxSize = dp[i]; maxValIndex = i; } } // 收集结果,从后面开始检查,直到找到最大值的位置 List answer = new ArrayList<>(); boolean first = true; int currentValue = maxSize; for (int i = n - 1; i >= 0; i--) { List temp = new ArrayList<>(); if (dp[i] == currentValue && currentValue != 0) { temp.add(nums.get(i)); int nextValue = 0; for (int j : temp) { if (num % j != 0 && j % num != 0) { nextValue = Math.min(nextValue, j % num + j % num != 0 ? 0 : 1); } // 这种方式不够准确,最好直接比较是否满足条件 } Collections.reverse(temp); answer.addAll(temp); currentValue = 0; break; } } return answer.size() > 0 ? answer : List.of(nums.get(0)); }}
这道题的解法采用了动态规划的思想,通过状态转移来解决一个个小问题,最终得到整体的解。首先对数组进行排序,有助于后续处理和减少计算复杂度。动态规划数组 dp 用于记录以当前数字结尾的最大子集的大小。在遍历时,对于每个数字,检查前面是否有能够整除它的数字,从而更新最优解。最后通过回溯找出所有最优解对应的数字,构造最终的结果。这个方法时间复杂度为 O(n^2),适用于给定的约束条件。
转载地址:http://dqnwk.baihongyu.com/