526互联

[Leetcode Weekly Contest]359

发布时间 2023-08-21 20:16:00作者: Jamest

链接：LeetCode

[Leetcode]2828. 判别首字母缩略词

给你一个字符串数组 words 和一个字符串 s ，请你判断 s 是不是 words 的 首字母缩略词 。
如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ，则认为 s 是 words 的首字母缩略词。例如，"ab" 可以由 ["apple", "banana"] 形成，但是无法从 ["bear", "aardvark"] 形成。
如果 s 是 words 的首字母缩略词，返回 true ；否则，返回 false 。

遍历即可。

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

[Leetcode]2829. k-avoiding 数组的最小总和

给你两个整数 n 和 k 。
对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。
返回长度为 n 的 k-avoiding 数组的可能的最小总和。

数学。推理公式。

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;
    }
}

[Leetcode]2830. 销售利润最大化

给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。
另给你一个二维整数数组 offers ，其中 offers[i] = [starti, endi, goldi] 表示第 i 个买家想要以 goldi 枚金币的价格购买从 starti 到 endi 的所有房屋。
作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。
返回你可以赚取的金币的最大数目。
注意 同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。

动态规划。定义 f[i+1] 表示销售编号不超过 i 的房屋的最大盈利。
考虑编号为 i 的房屋卖或不卖：

  • 不卖，有 f[i+1]=f[i]。
  • 卖，那么遍历所有 \(\textit{end}_j=i\)的购买请求，有 \(f[i+1]=max⁡(f[start_j]+gold_j)\)。为了方便遍历，可以先把所有 \(\textit{end}\) 相同的数据用哈希表归类。
    两种情况取最大值。
class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        Map<Integer, List<List<Integer>>> map = new HashMap<>();
        for(var offer: offers) {
            map.computeIfAbsent(offer.get(1), k-> new ArrayList<List<Integer>>()).add(offer);
        }

        int[] dp = new int[n+1];
        for(int i=1;i<n+1;++i) {
            dp[i] = dp[i-1];
            for(var offer: map.getOrDefault(i-1,  new ArrayList<List<Integer>>())) {
                int start = offer.get(0), end = offer.get(1), gold = offer.get(2);
                dp[i] = Math.max(dp[i], dp[start] + gold);
            }
        }
        return dp[n];
    }
}

[Leetcode]2831. 找出最长等值子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
子数组 是数组中一个连续且可能为空的元素序列。

分组+滑动窗口。用滑动窗口在相同的数字里面计算长度，每次记录左右边界差值；
窗口每加入一个相同的数，计算与上一个数对应下标的差值，并累计起来，差值表示中间删掉的数字个数，超过规定值左边界就要弹出；
窗口加入不同的数字时，左边界需要直接移动到右边界，计算新的数字的长度，并重新累计下标差值。

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        Map<Integer, List<Integer>> index = new HashMap<>();
        for(int i=0;i<nums.size();++i) {
            index.computeIfAbsent(nums.get(i), kk -> new ArrayList<>()).add(i);
        }
        int res = 1;
        for(int num: index.keySet()) {
            List<Integer> inds = index.get(num);
            int left = 0, right = 0;
            while(right < inds.size()) {
                while(inds.get(right)-inds.get(left)-(right-left) > k) left ++;
                res = Math.max(res, right-left+1);
                ++right;
            }
        }
        return res;
    }
}

参考：LeetCode