1

import java.util.Arrays;

class Solution {
    public int solution(int[] X, int[] Y, int W) {
        // write your code in Java 8 (Java SE 8)
        Arrays.sort(X);
        int i = 0;
        int res = 0;
        while (i < X.length) {
            res ++;
            int end = X[i] + W;
            while (i < X.length && X[i] <= end) {
                i ++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[]{2, 4, 2, 6, 7, 1}, new int[]{0, 5, 3, 2, 1, 5}, 2));
    }
}

2

import java.util.OptionalInt;
import java.util.stream.IntStream;

class Solution {
    public String solution(String S) {
        // write your code in Java 8 (Java SE 8)

        // 统计每个字母出现的次数
        int[] count = new int[26];
        for (char c : S.toCharArray()) {
            count[c - '0'] ++;
        }
        OptionalInt mid = IntStream.range(0, 10).filter(i -> count[i] % 2 == 1).max();
        StringBuilder builder = new StringBuilder();
        for (int i = 9; i >= 0; i--) {
            if (i == 0 && builder.length() == 0) {
                continue;
            }
            for (int j = 0; j < count[i] / 2; j++) {
                builder.append(i);
            }
        }
        String res = "";
        if (mid.isPresent()) {
            res += mid.getAsInt();
        }
        res = builder + res + builder.reverse();
        if (res.length() == 0) {
            return "0";
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().solution("0000"));
    }
}

3

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

class Solution {

    public int solution(int[] A, int[] B) {
        int edgesCount = A.length;
        int nodesCount = edgesCount + 1;
        Map<Integer, List<Integer>> connectedNodesMap = getConnectedNodesMap(A, B);
        // 获取每个节点到0的距离
        int[] distances = getDistancesToZero(connectedNodesMap, nodesCount);
        // 获取每个距离对应的节点
        Map<Integer, List<Integer>> distanceToNodesMap = getDistanceToNodesMap(distances, nodesCount);
        // 每个节点上的人数
        int[] peopleCount = new int[nodesCount];
        // 从每个节点尝试向离0更近的节点移动
        int consumedEnergy = 0;
        List<Integer> distanceList = new ArrayList<>(distanceToNodesMap.keySet());
        distanceList.sort(Collections.reverseOrder());
        for (int distance : distanceList.subList(0, distanceList.size() - 1)) {
            List<Integer> nodesList = distanceToNodesMap.get(distance);
            // 每个节点找到他可以直达的，并且距离0更近的节点
            for (int node : nodesList) {
                int destination = connectedNodesMap.get(node).stream().filter(v -> distances[v] == distance - 1).findFirst().orElseThrow(() -> new RuntimeException("not found"));
                // 移到目的地
                peopleCount[destination] += (peopleCount[node] + 1);
                consumedEnergy += (peopleCount[node] + 1 + (4 - 1)) / 4;
            }
        }
        return consumedEnergy;
    }

    private Map<Integer, List<Integer>> getDistanceToNodesMap(int[] distances, int nodesCount) {
        Map<Integer, List<Integer>> distanceToNodesMap = new HashMap<>();
        for (int i = 0; i < nodesCount; i++) {
            int distance = distances[i];
            distanceToNodesMap.computeIfAbsent(distance, k -> new ArrayList<>()).add(i);
        }
        return distanceToNodesMap;
    }

    private int[] getDistancesToZero(Map<Integer, List<Integer>> connectedNodesMap, int nodesCount) {
        int[] distancesToZero = new int[nodesCount];
        boolean[] visited = new boolean[nodesCount];
        for (int i = 0; i < nodesCount; i++) {
            distancesToZero[i] = -1;
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        int distance = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                distancesToZero[node] = distance;
                connectedNodesMap.getOrDefault(node, Collections.emptyList()).forEach(neighbor -> {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.add(neighbor);
                    }
                });
            }
            distance++;
        }
        return distancesToZero;
    }

    /**
     * 获取每个节点直接联通的节点
     */
    private Map<Integer, List<Integer>> getConnectedNodesMap(int[] A, int[] B) {
        int edgesCount = A.length;
        int nodesCount = edgesCount + 1;
        int[][] edges = new int[edgesCount][2];
        for (int i = 0; i < edgesCount; i++) {
            edges[i][0] = A[i];
            edges[i][1] = B[i];
        }
        // 与每个节点直接联通的节点
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < edgesCount; i++) {
            if (!map.containsKey(edges[i][0])) {
                map.put(edges[i][0], new ArrayList<>());
            }
            map.get(edges[i][0]).add(edges[i][1]);
            if (!map.containsKey(edges[i][1])) {
                map.put(edges[i][1], new ArrayList<>());
            }
            map.get(edges[i][1]).add(edges[i][0]);
        }
        return map;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[]{0, 1, 1}, new int[]{1, 2, 3}));
    }

}