NO.1 Find the largest common divisor of an array

Their thinking

To find the greatest common divisor by division.

The code shown

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); }}Copy the code

No.2 Find different binary strings

Their thinking

Violent enumeration is enough. To facilitate enumeration, you can parse binary strings into integers.

The code shown

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 "";
  }
} 
Copy the code

NO.3 Minimize the difference between the target value and the selected element

Their thinking

In dynamic programming, the state dp[I][j] is defined to indicate whether the sum can be j when the number in the ith row is taken

The code shown

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; }}Copy the code

 

No.4 Restoring an array from the sum of subsets

Their thinking

Make num the absolute value of the difference between the minimum and sublarge values (or the maximum and the sublarge) in sums, then either num or -nums must be in the original array. Sums can be divided into two groups by num: those with and without num.

For example: [-3,-2,-1,0,0,1,2,3] num = 1, then 1 or -1 must exist in the original array.

Num = 1 can divide sums into [-3, -1, 0, 2] and [-2, 0, 1, 3]. When we assume that 1 exists in the original array, the first half should be used to continue recursion, and vice versa.

The code shown

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)); List<Integer> next = new ArrayList<>(); // Sums must be equal to sums. 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; }}Copy the code