【 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;

  }

}