第 359 场力扣周赛

判别首字母缩略词

Java

class Solution {
    public boolean isAcronym(List<String> words, String s) {
        int n = words.size(), m = s.length();
        if (n != m) return false;
        for (int i = 0; i < n; i++) {
            if (words.get(i).charAt(0) != s.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    bool isAcronym(vector<string>& words, string s) {
        int m = words.size(), n = s.size();
        if (m != n) return false;
        for (int i = 0; i < n; i++) {
            if (words[i][0] != s[i]) {
                return false;
            }
        }
        return true;
    }
};

k-avoiding 数组的最小总和

贪心。

Java

class Solution {
    public int minimumSum(int n, int k) {
        int m = Math.min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
}

C++

class Solution {
public:
    int minimumSum(int n, int k) {
        int m = min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
};

销售利润最大化

不从动态规划的角度思考，我首先用的是对左端点排序。如果用动态规划，那么根据转移方程就会对右端点排序，处理方式也比对左端点排序简单一些。还可以不排序做，使用桶存储相同 \(end\) 的 \(offer\)，分别处理每个桶。

Java

class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        Collections.sort(offers, (a, b) -> a.get(1) - b.get(1));
        offers.add(List.of(n - 1, n - 1, 0));
        int m = offers.size(), i = 0;
        int[] leftMax = new int[n + 1];
        for (var offer : offers) {
            int s = offer.get(0), e = offer.get(1), g = offer.get(2);
            for (; i <= e; i++) leftMax[i + 1] = leftMax[i];
            leftMax[e + 1] = Math.max(leftMax[e + 1], leftMax[s] + g);
        }
        return leftMax[n];
    }
}

C++

class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        vector<vector<pair<int, int>>> groups(n);
        for (auto &offer : offers) {
            groups[offer[1]].emplace_back(offer[0], offer[2]);
        }
        vector<int> f(n + 1);
        for (int end = 0; end < n; end++) {
            f[end + 1] = f[end];
            for (auto &[start, gold] : groups[end]) {
                f[end + 1] = max(f[end + 1], f[start] + gold);
            }
        }
        return f[n];
    }
};

找出最长等值子数组

Java

滑动窗口：

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size();
        Map<Integer, Integer> map = new HashMap<>();
        int lo = 0, hi = 0, ans = 0;
        while (hi < n) {
            map.merge(nums.get(hi++), 1, Integer::sum);
            if (hi - lo - map.get(nums.get(lo)) > k) {
                map.merge(nums.get(lo++), -1, Integer::sum);
            }
            ans = Math.max(ans, map.get(nums.get(lo)));
        }
        while (lo + 1 < n) {
            map.merge(nums.get(lo++), -1, Integer::sum);
            ans = Math.max(ans, map.get(nums.get(lo)));
        }
        return ans;
    }
}

滑动窗口（优化）：

• 优化一：观察到 \(1\leq nums[i]\leq nums.lenth\)，所以可以用数组模拟哈希表。
• 优化二：滑动窗口直接枚举右端点，这样可以枚举到所有情况。但是如何保证删除的元素数量小于等于 \(k\) 呢？当左端点的值 \(nums[i]\) 不能构成等值数组，则将左端点右移。为什么这样可以保证？当 \(nums[i]\neq nums[j]\) 时，移动左端点不影响答案；当 \(nums[i]=nums[j]\) 时，移动左端点可以保证删除的元素数量小于等于 \(k\)。

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size(), ans = 0;
        int[] map = new int[n + 1];
        for (int i = 0, j = 0; j < n; j++) {
            map[nums.get(j)]++;
            if (j - i + 1 - map[nums.get(i)] > k) {
                map[nums.get(i++)]--;
            }
            ans = Math.max(ans, map[nums.get(j)]);
        }
        return ans;
    }
}

C++

分组 + 双指针：

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        vector<vector<int>> pos(n + 1);
        for (int i = 0; i < n; i++) {
            pos[nums[i]].push_back(i);
        }
        for (auto &ps : pos) {
            int left = 0;
            for (int right = 0; right < ps.size(); right++) {
                while (ps[right] - ps[left] - right + left > k) {
                    left++;
                }
                ans = max(ans, right - left + 1);
            }
        }
        return ans;
    }
};