lcpBi104

老人的数目

方法一：模拟

class Solution {
    public int countSeniors(String[] details) {
        int res = 0;
        for (String detail : details) {
            int age = Integer.parseInt(detail.substring(11, 13));
            if (age > 60)
                ++res;
        }
        return  res;
    }
}

矩阵中的和

方法一：错

TreeSet中不能存放重复的元素，使用大根堆！

public int matrixSum(int[][] nums) {
    int m = nums.length, n = 0;
    TreeSet<Integer>[] treeSets = new TreeSet[m];
    for (int i = 0; i < m; ++i) {
        treeSets[i] = new TreeSet<>();
        for (int j = 0; j < nums[i].length; ++j) {
            n = Math.max(n, nums[i].length);
            treeSets[i].add(nums[i][j]);
        }
    }
    int res = 0;
    for (int j = 0; j < n; ++j) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < m; ++i) {
            if (!treeSets[i].isEmpty()) {
                int cur = treeSets[i].last();
                treeSets[i].remove(cur);
                max = Math.max(max, cur);
            }
        }
        res += max;
    }
    return res;
}

方法二：排序

class Solution {
    public int matrixSum(int[][] nums) {
        for (int[] row : nums)
            Arrays.sort(row);
        int res = 0;
        for (int j = 0; j < nums[0].length; ++j) {
            int max = 0;
            for (int i = 0; i < nums.length; ++i) {
                if (nums[i][j] > max)
                    max = nums[i][j];
            }
            res += max;
        }
        return res;
    }
}

方法三：大根堆

用的小根堆，和大根堆一样，先把每行最小的弹出

class Solution {
    public int matrixSum(int[][] nums) {
        int m = nums.length, n = nums[0].length;
        PriorityQueue<Integer>[] queues = new PriorityQueue[m];
        for (int i = 0; i < m; ++i) {
            queues[i] = new PriorityQueue<>();
            for (int j = 0; j < nums[i].length; ++j) {
                queues[i].add(nums[i][j]);
            }
        }
        int res = 0;
        for (int j = 0; j < n; ++j) {
            int max = 0;
            for (int i = 0; i < m; ++i) {
                max = Math.max(max, queues[i].poll());
            }
            res += max;
        }
        return res;
    }
}

最大或值

方法一：前后缀+ 记忆化搜索

一定要用数组！不要用哈希表

class Solution {
    public long maximumOr(int[] nums, int k) {
        this.nums = nums;
        n = nums.length;
        dp = new long[n + 1][16];
        for (long[] arr : dp)
            Arrays.fill(arr, -1);
        preOr = new long[n + 1];
        for (int i = 1; i <= n; ++i)
            preOr[i] = nums[i - 1] | preOr[i - 1];
        postOr = new long[n + 1];
        for (int i = n - 1; i >= 0; --i)
            postOr[i] = nums[i] | postOr[i + 1];
        return dfs(0, k);
    }
    private long dfs(int index, int k) {
        if (dp[index][k] != -1)
            return dp[index][k];
        if (index == n) // 走到这说明k的次数没用完
            return preOr[n];
        if (k == 0) {
            int pre = -1;
            long temp1 = 0, temp2;
            for (int i : change.keySet()) {
                temp2 = preOr[i] | preOr[pre + 1];
                temp2 = temp2 | ((long) nums[i] << change.get(i));
                temp1 |= temp2;
                pre = i;
            }
            temp2 = postOr[pre + 1];
            temp1 |= temp2;
            return temp1;
        }
        long res, changeNext = 0;
        long pass = dfs(index + 1, k);
        if (k > 0) {
            change.put(index, change.getOrDefault(index, 0) + 1);
            changeNext = dfs(index, k - 1);
            change.put(index, change.get(index) - 1);
            if (change.get(index) == 0)
                change.remove(index);
        }
        res = Math.max(pass, changeNext);
        return dp[index][k] = res;
    }

    int[] nums;
    long[] preOr, postOr;
    int n;
    TreeMap<Integer, Integer> change = new TreeMap<>();
    long[][] dp;
}

方法二：贪心

把「乘 2」分配给多个数，不如只分配给一个数，这样更有可能得到更大的答案。

class Solution {

    public long maximumOr(int[] nums, int k) {

        int n = nums.length;

        var suf = new int[n + 1];

        for (int i = n - 1; i > 0; i--)

            suf[i] = suf[i + 1] | nums[i];

        long ans = 0;

        for (int i = 0, pre = 0; i < n; i++) {

            ans = Math.max(ans, pre | ((long) nums[i] << k) | suf[i + 1]);

            pre |= nums[i];

        }

        return ans;

    }

}

英雄的力量

方法一：贡献法

class Solution {
    public int sumOfPower(int[] nums) {
        Arrays.sort(nums);
        long MOD = (int) 1e9 + 7, res = 0, s = 0;
        for (long x : nums) {
            res = (res + x * x % MOD * (x + s)) % MOD;
            s = (s * 2 + x) % MOD;
        }
        return (int) res;
    }
}