2022.8.31 途虎养车笔试

public class Main1 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    Set<Integer> set = new HashSet<>();
    public int numColor(TreeNode root) {
        // write code here
        dfs(root);
        return set.size();
    }

    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        set.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}

public class Main2 {
    
    public int change (int[] oils, int box) {
        // write code here
        int[] dp = new int[box+1];
        Arrays.fill(dp,box+1);
        dp[0]=0;
        for (int i = 1; i <= box; i++) {
            for (int j = 0; j < oils.length; j++) {
                if(oils[j]<=i){
                    dp[i]=Math.min(dp[i],dp[i-oils[j]]+1);
                }
            }
        }
        return dp[box]>box?-1:dp[box];
    }
}

public class Main3 {
    Set<Integer>[] sets ;
    int[][] arr;
    int res = Integer.MAX_VALUE;
    public int minimumIncompatibility(int[] nums, int k) {
        // write code here
        int len = nums.length;
        Arrays.sort(nums);
        int t = len / k;
        int[] tong = new int[nums.length + 1];
        for (int num : nums) {
            tong[num]++;
        }
        for (int num : tong) {
            if (num > k) {
                return -1;
            }
        }
        sets = new HashSet[k];
        for (int i = 0; i < k; i++) {
            sets[i] = new HashSet<>();
        }
        arr = new int[k][2];
        for (int i = 0; i < k; i++) {
            arr[i][0] = Integer.MAX_VALUE;
            arr[i][1] = Integer.MIN_VALUE;
        }
        dfs(nums,0,k,t);
        return res;
    }

    private void dfs(int[] nums, int cur,int k,int t) {
        if(cur>=nums.length){
            int sum=0;
            for (int i = 0; i < k; i++) {
                sum+=arr[i][1]-arr[i][0];
            }
            res=Math.min(res,sum);
            return;
        }
        for (int i = 0; i < k; i++) {
            Set<Integer> set2 = sets[i];
            if (t==set2.size() || set2.contains(nums[cur])){
                continue;
            }
            set2.add(nums[cur]);
            int min = arr[i][0];
            int max = arr[i][1];
            arr[i][0]=Math.min(min,nums[cur]);
            arr[i][1]=Math.max(max,nums[cur]);
            dfs(nums,cur+1,k,t);
            set2.remove(nums[cur]);
            arr[i][0]=min;
            arr[i][1]=max;
            if(set2.size()==0){
               break;
            }
        }
    }
}