LeetCode Weekly Contest 255解题报告

【 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<Integer> 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<Integer> sums2 = new ArrayList<>();
       for (int i : sums) {
           sums2.add(i);
      }
       List<Integer> result = new ArrayList<>();
       Collections.sort(sums2);
       dfs(n, result, sums2);
       return result.stream().mapToInt(i -> i).toArray();
  }

   private boolean dfs(int n, List<Integer> result, List<Integer> sums) {
       if (n == 0) {
           return true;
      }
       int num = Math.abs(sums.get(0) - sums.get(1));
       // num 或 -num 必然存在于 result 中
       // 以 num 可以将 sums 分成两部分
       List<Integer> next = new ArrayList<>();
       LinkedList<Integer> 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;
  }
}
复制代码