链接: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
- Leetcode Contest Weekly 359leetcode contest weekly 359 leetcode contest weekly 361 leetcode contest weekly 355 leetcode contest weekly 365 leetcode contest weekly 367 leetcode contest weekly 368 leetcode contest weekly 350 leetcode contest weekly 351 leetcode contest weekly 339 leetcode contest weekly 364