lcp359

判别首字母缩略词

方法一：暴力

class Solution {
    public boolean isAcronym(List<String> words, String s) {
        StringBuilder sb = new StringBuilder();
        for (String word : words)
            sb.append(word.charAt(0));
        return s.equals(sb.toString());
    }
}

k-avoiding 数组的最小总和

方法一：HashSet

class Solution {
    public int minimumSum(int n, int k) {
        Set<Integer> set = new HashSet<>();
        int i = 1, sum = 0;
        while (n > 0) {
            if (!set.contains(k - i)) {
                set.add(i);
                sum += i;
                --n;
            }
            ++i;
        }
        return sum;
    }
}

销售利润最大化

方法一：线性DP

相似题目

• 2008. 出租车的最大盈利（和本题几乎一样）

• 1235. 规划兼职工作（数据范围更大的情况，我的题解）

• 1751. 最多可以参加的会议数目 II（区间个数限制）

• 2054. 两个最好的不重叠活动

class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        List<int[]>[] list = new List[n];
        Arrays.setAll(list, e -> new ArrayList<>());
        for (List<Integer> offer : offers) {
            int start = offer.get(0), end = offer.get(1), val = offer.get(2);
            list[end].add(new int[]{start, val});
        }
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            for (int[] arr : list[i - 1]) {
                int start = arr[0], val = arr[1];
                dp[i] = Math.max(dp[i], dp[start] + val);
            }
        }
        return dp[n];
    }
}

方法二：二分 + DP

class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        Collections.sort(offers, (o1, o2) -> o1.get(1) - o2.get(1));
        // 处理标号为0~i的房子能获得的最大利润
        int[] dp = new int[offers.size() + 1];
        for (int i = 0; i < offers.size(); ++i) {
            dp[i + 1] = dp[i];
            int j = bisearch(offers, i, offers.get(i).get(0));
            dp[i + 1] = Math.max(dp[i + 1], (j >= -1 ? dp[j + 1] : 0) + offers.get(i).get(2));
        }
        return dp[offers.size()];
    }

    private int bisearch(List<List<Integer>> offers, int r, int start) {
        int l = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (offers.get(mid).get(1) < start)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }
}

找出最长等值子数组

方法一：滑动窗口 同向双指针

1. 将每个值的下标存到List中，例如对于nums = [1,3,2,3,1,3], k = 3

   list[1]: [0, 4]

   list[2] : [4]

   list[3]: [1, 3, 5]

2. 枚举每个list，即把元素替换成1或2或3，例如枚举list[3]: [1, 3, 5]，l = 0, r = 1时，nums数组有list.get(r) - list.get(0) + 1 = 3 - 1 + 1 = 3个数：[3，2，3]，这个子数组中有r - l + 1 = 1 - 0 + 1 = 2个3，所以需要删除3 - 2 = 1个数

3. 当需要删除的数大于k时，将左端点右移，直到满足需要删除的元素小于等于k

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size();
        List<Integer>[] pos = new List[n + 1];
        Arrays.setAll(pos, e -> new ArrayList<>());
        for (int i = 0; i < n; ++i)
            pos[nums.get(i)].add(i);
        int res = 0;
        for (List<Integer> list : pos) {
            int l = 0;
            for (int r = 0; r < list.size(); ++r) {
                while (list.get(r) - list.get(l) + 1 - (r - l + 1) > k)
                    ++l;
                res = Math.max(res, r - l + 1);
            }
        }
        return res;
    }
}