No.1 Check binary string fields

Their thinking

A string that meets the requirements is a string whose prefix is all 1’s and suffix is all 0’s.

The code shown

    public boolean checkOnesSegment(String s) {
        if (!s.contains("0")) {
            return true;
        }
        if (s.substring(s.indexOf("0")).contains("1")) {
            return false;
        }
        return true;
    }
}
Copy the code

No.2 constitutes the minimum element that is specific and needs to be added

Their thinking

Be greedy and add as large an absolute value as possible each time. Note that the sum may overflow int, so use long for the intermediate operation.

The code shown

    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        sum = Math.abs(goal - sum);
        int count = (int) (sum / limit);
        if (sum % limit != 0) {
            count++;
        }
        return count;
    }
}
Copy the code

No.3 Number of restricted paths from the first node to the last node

Their thinking

Dijkstra + DP

The code shown

static class Edge { int next; int len; Edge(int next, int len) { this.next = next; this.len = len; }} public int countRestrictedPaths(int n, int[][] edges) {Map<Integer, List<Edge>> graph = new HashMap<>(); for (int[] edge : edges) { for (int i = 0; i < 2; i++) { if (! graph.containsKey(edge[i])) { graph.put(edge[i], new ArrayList<>()); } graph.get(edge[i]).add(new Edge(edge[1 - i], edge[2])); Var distanceToLastNode = dijkstra(n, graph); // DP int[] mem = new int[n + 1]; Arrays.fill(mem, -1); mem[n] = 1; return dp(1, mem, distanceToLastNode, graph); } private int dp(int cur, int[] mem, Map<Integer, Integer> distanceToLastNode, Map<Integer, List<Edge>> graph) { if (mem[cur] >= 0) { return mem[cur]; } mem[cur] = 0; for (var next : graph.get(cur)) { if (distanceToLastNode.get(cur) > distanceToLastNode.get(next.next)) { mem[cur] = (mem[cur] + dp(next.next, mem, distanceToLastNode, graph)) % 1000000007; } } return mem[cur]; } static class Node { int to; int len; Node(int to, int len) { Look @t This To... = to; this.len = len; } } private Map<Integer, Integer> dijkstra(int start, Map<Integer, List<Edge>> graph) { Set<Integer> visited = new HashSet<>(); Map<Integer, Integer> res = new HashMap<>(); PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (o1.len - o2.len)); res.put(start, 0); heap.add(new Node(start, 0)); while (! heap.isEmpty()) { Node node = heap.poll(); if (visited.contains(node.to)) { continue; } visited.add(node.to); for (Edge e : graph.get(node.to)) { if (res.getOrDefault(e.next, Integer.MAX_VALUE) > node.len + e.len) { res.put(e.next, node.len + e.len); heap.add(new Node(e.next, node.len + e.len)); } } } return res; }}Copy the code

No.4 sets xOR results to zero for all intervals

Their thinking

DP

The code shown

Public int minChanges(int[] nums, int k) {public int minChanges(int[] nums, int k) { Int [][] count = new int[k][1 << 10]; for (int i = 0; i < nums.length; i++) { count[i % k][nums[i]]++; Int [][] dp = new int[k + 1][1 << 10]; int[] dp = new int[k + 1][1 << 10]; for (int i = 0; i <= k; i++) { Arrays.fill(dp[i], nums.length); } dp[0][0] = 0; int min = nums.length, sum = 0; for (int i = 1; i <= k; i++) { int[] cur = count[i - 1]; int tot = 0, max = 0; for (int j : cur) { tot += j; max = Math.max(max, j); } sum += tot - max; min = Math.min(min, max); for (int j = 0; j < (1 << 10); j++) if (cur[j] > 0) { int now = tot - cur[j]; for (int K = 0; K < (1 << 10); K++) dp[i][j ^ K] = Math.min(dp[i][j ^ K], dp[i - 1][K] + now); } } return Math.min(dp[k][0], min + sum); }}Copy the code