lcpBi114

8038. 收集元素的最少操作次数

方法一：HashSet

class Solution {
    public int minOperations(List<Integer> nums, int k) {
        Set<Integer> set = new HashSet<>();
        int n = nums.size();
        int res = 0;
        for (int i = n - 1; i >= 0; --i) {
            int x = nums.get(i);
            set.add(x);
            ++res;
            if (check(set, k))
                return res;
        }
        return 0;
    }

    private boolean check(Set<Integer> set, int k) {
        for (int i = 1; i <= k; ++i) {
            if (!set.contains(i))
                return false;
        }
        return true;
    }
}

100032. 使数组为空的最少操作次数

方法一：HashMap

class Solution {
    public int minOperations(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int res = 0;
        for (int x : nums)
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        for (int x : cnt.values()) {
            if (x == 1)
                return -1;
            int a = x / 3;
            if (x % 3 == 0)
                res += a;
            else {
                res += a + 1;
            }

        }
        return res;
    }

}

100019. 将数组分割成最多数目的子数组

方法一：二分查找 + 贪心

class Solution {
    public int maxSubarrays(int[] nums) {
        //二分
        int n = nums.length;

        int cnt0 = 0, cur = nums[0];
        boolean flag = false;
        for (int x : nums) {
            if (flag) {
                cur = x;
                flag = false;
            }
            else
                cur &= x;
            if (cur == 0) {
                ++cnt0;
                flag = true;
            }
        }
        int l = cnt0, r = n;
        int target = nums[0];
        for (int x : nums)
            target &= x;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(nums, mid, target))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }

    private boolean check(int[] nums, int k, int target) {
        int sum = 0, cur = nums[0], cnt = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            cur &= x;
            if (cur <= target && sum + cur <= target) {
                ++cnt;
                sum += cur;
                if (i == n - 1)
                    break;
                cur = nums[i + 1];
            }
        }
        return cnt >= k && sum == target;
    }
}

2872. 可以被 K 整除连通块的最大数目

方法一：树形DP

class Solution {
    public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        this.k = k;
        this.values = values;
        g = new List[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        return dfs(0, -1)[0];
    }
    List<Integer>[] g;
    int k;
    int[] values;
    private int[] dfs(int x, int p) {
        int[] arr = new int[2];
        arr[1] = values[x];
        for (int next : g[x]) {
            if (next != p) {
                int[] temp = dfs(next, x);
                arr[0] += temp[0];
                arr[1] += temp[1];
            }
        }
        if (arr[1] % k == 0) {
            arr[1] = 0;
            arr[0]++;
        }
        return arr;
    }
}