【 NO.1 找出数组的最大公约数】
解题思路
辗转相除法求最大公约数。
代码展示
class Solution {
public int findGCD(int[] nums) {
Arrays.sort(nums);
return gcd(nums[nums.length - 1], nums[0]);
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
【 NO.2 找出不同的二进制字符串】
解题思路
暴力枚举即可，为了方便枚举，可以将二进制字符串解析成整数。
代码展示
class Solution {
public String findDifferentBinaryString(String[] nums) {
Set set = new HashSet<>();
for (var num : nums) {
set.add(Integer.parseInt(num, 2));
}
int n = nums.length;
for (int i = 0; i < (1 << n); i++) {
if (!set.contains(i)) {
String str = Integer.toBinaryString(i);
while (str.length() < n) {
str = “0” + str;
}
return str;
}
}
return “”;
}
}
【 NO.3 最小化目标值与所选元素的差】
解题思路
动态规划，定义状态 dp[i][j] 表示取到第 i 行的数字时，能否使得和为 j
代码展示
class Solution {
public int minimizeTheDifference(int[][] mat, int target) {
int n = mat.length;
int m = mat[0].length;
int M = 5000;
boolean[][] dp = new boolean[n][M];
for (int i = 0; i < m; i++) {
dp[0][mat[0][i]] = true;
}
for (int i = 1; i < n; i++) {
for (int k = 0; k < M; k++) {
for (int j = 0; j < m; j++) {
if (k >= mat[i][j] && dp[i - 1][k - mat[i][j]]) {
dp[i][k] = true;
break;
}
}
}
}
int result = M;
for (int i = 0; i < M; i++) {
if (dp[n - 1][i]) {
result = Math.min(result, Math.abs(i - target));
}
}
return result;
}
}
【 NO.4 从子集的和还原数组】
解题思路
令 num 表示 sums 中最小值和次小值（或者最大值与次大值）的差的绝对值，那么 num 或 -nums 一定存在于原数组中，枚举这两种情况即可。sums 可以被 num 分成两组：包含 num 的和不包含 num 的。
以样例举例解释：[-3,-2,-1,0,0,1,2,3] num = 1, 那么 1 或 -1 一定存在于原数组中。
num = 1 可以将 sums 分成 [-3, -1, 0, 2] 和 [-2, 0, 1, 3] 这两部分，当我们假定 1 存在于原数组时，应当用前半部分继续递归，反之，用后半部分继续递归。
代码展示
class Solution {
public int[] recoverArray(int n, int[] sums) {
List sums2 = new ArrayList<>();
for (int i : sums) {
sums2.add(i);
}
List result = new ArrayList<>();
Collections.sort(sums2);
dfs(n, result, sums2);
return result.stream().mapToInt(i → i).toArray();
}
private boolean dfs(int n, List result, List sums) {
if (n == 0) {
return true;
}
int num = Math.abs(sums.get(0) - sums.get(1));
// num 或 -num 必然存在于 result 中
// 以 num 可以将 sums 分成两部分
List next = new ArrayList<>();
LinkedList toRemove = new LinkedList<>();
for (int i : sums) {
if (toRemove.isEmpty() || toRemove.getFirst() != i) {
next.add(i);
toRemove.addLast(i + num);
} else {
toRemove.pollFirst();
}
}
if (sums.contains(num) && dfs(n - 1, result, next)) {
result.add(num);
return true;
}
for (int i = 0; i < next.size(); i++) {
next.set(i, next.get(i) + num);
}
if (sums.contains(-num) && dfs(n - 1, result, next)) {
result.add(-num);
return true;
}
return false;
}
}