lcp344

找出不同元素数目差数组

方法一：模拟

class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            Set<Integer> preSet = new HashSet<>(), postSet = new HashSet<>();
            for (int j = i; j >= 0; --j)
                preSet.add(nums[j]);
            for (int j = i + 1; j < n; ++j)
                    postSet.add(nums[j]);
            res[i] = preSet.size() - postSet.size();
        }
        return res;
    }
}

频率跟踪器

方法一：HashMap

class FrequencyTracker {

    int[] nums;
    Map<Integer, Set<Integer>> map;

    public FrequencyTracker() {
        nums = new int[100001];
        map = new HashMap<>();
    }
    
    public void add(int number) {
        ++nums[number];
        int freq = nums[number];
        if (!map.containsKey(freq))
            map.put(freq, new HashSet<>());
        map.get(freq).add(number);
        if (map.containsKey(freq - 1))
            map.get(freq - 1).remove(number);
    }
    
    public void deleteOne(int number) {
        int freq = nums[number];
        if (nums[number] == 0)
            return;
        else {
            --nums[number];
            map.get(freq).remove(number);
            if (!map.containsKey(freq - 1))
                map.put(freq - 1, new HashSet<>());
            map.get(freq - 1).add(number);
        }
    }
    
    public boolean hasFrequency(int frequency) {
        if (map.containsKey(frequency) && map.get(frequency).size() > 0)
            return true;
        else
            return false;
    }
}

/**
 * Your FrequencyTracker object will be instantiated and called as such:
 * FrequencyTracker obj = new FrequencyTracker();
 * obj.add(number);
 * obj.deleteOne(number);
 * boolean param_3 = obj.hasFrequency(frequency);
 */

方法二：前后缀分解

class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] res = new int[n],  suffix = new int[n + 1];
        Set<Integer> set = new HashSet<>();
        for (int i = n - 1; i >= 0; --i) {
            set.add(nums[i]);
            suffix[i] = set.size();
        }
        set.clear();
        for (int i = 0; i < n; ++i) {
            set.add(nums[i]);
            res[i] = set.size() - suffix[i + 1];
        }
        return res;
    }
}

有相同颜色的相邻元素数目

方法一：模拟

class Solution {
    public int[] colorTheArray(int n, int[][] queries) {
        int[] res = new int[queries.length], nums = new int[n + 1];
        int count = 0, idx = 0;
        for (int[] query : queries) {
            int index = query[0], color = query[1];
            if (nums[index] > 0) {
                if (index > 0 && nums[index] == nums[index - 1])
                    --count;
                if (index < n && nums[index] == nums[index + 1])
                    --count;
            }
            nums[index] = color;
            if (index > 0 && nums[index] == nums[index - 1])
                ++count;
            if (index < n && nums[index] == nums[index + 1])
                ++count;
            res[idx++] = count;
        }
        return res;
    }
}

使二叉树所有路径值相等的最小代价

方法一：树上贪心

class Solution {
    public int minIncrements(int n, int[] cost) {
        int res = 0;
        for (int i = n / 2; i > 0; --i) {
            res += Math.abs(cost[2 * i - 1] - cost[2 * i]);
            cost[i - 1] += Math.max(cost[2 * i - 1], cost[2 * i]);
        }
        return res;
    }
}