7004. Check if a String Is an Acronym of Words
给你一个字符串数组 words 和一个字符串 s ，请你判断 s 是不是 words 的 首字母缩略词 。
如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ，则认为 s 是 words 的首字母缩略词。例如，"ab" 可以由 ["apple", "banana"] 形成，但是无法从 ["bear", "aardvark"] 形成。
如果 s 是 words 的首字母缩略词，返回 true ；否则，返回 false 。
测试样例：
输入：words = ["alice","bob","charlie"], s = "abc"
输出：true
解释：
words 中 "alice"、"bob" 和 "charlie" 的第一个字符分别是 'a'、'b' 和 'c'。因此，s = "abc" 是首字母缩略词。
解答：暴力遍历一下words，然后生成首字母字符串，最后和s比较一下。
class Solution {
public boolean isAcronym(List<String> words, String s) {
StringBuilder sb = new StringBuilder();
for (String w : words) {
sb.append(w.charAt(0));
}
return sb.toString().equals(s);
}
}6450. Determine the Minimum Sum of a k-avoiding Array
给你两个整数 n 和 k 。
对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。
返回长度为 n 的 k-avoiding 数组的可能的最小总和。
测试样例：
输入：n = 5, k = 4
输出：18
解释：
设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。可以证明不存在总和小于 18 的 k-avoiding 数组。
解答：这道题目需要用到贪婪算法。一个简单的思路，假设我们期望加入1，那么 k - 1 就不再符合要求。但是1和k - 1之间，我们肯定选择1，因为很直观的1更小。因为提示给的范围很小1 <= n, k <= 50。暴力计数，只要n能满足。
class Solution {
public int minimumSum(int n, int k) {
int res = 0, pos = 1;
Set<Integer> invalid = new HashSet<>();
while (n > 0) {
if (!invalid.contains(pos)) {
res += pos;
invalid.add(k - pos);
--n;
}
++pos;
}
return res;
}
}7006. Maximize the Profit as the Salesman
给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。
另给你一个二维整数数组 offers ，其中 offers[i] = [starti, endi, goldi] 表示第 i 个买家想要以 goldi 枚金币的价格购买从 starti 到 endi 的所有房屋。
作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。
返回你可以赚取的金币的最大数目。
注意 同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。
测试样例
输入：n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
输出：3
解释：
有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。将位于 [0,0] 范围内的房屋以 1 金币的价格出售给第 1 位买家，并将位于 [1,3] 范围内的房屋以 2 金币的价格出售给第 3 位买家。可以证明我们最多只能获得 3 枚金币。
解答：这道题目考到了排序和动态规划。排序可以利用结束房间位置排序，然后计算当前结束位置最好的情况（最好情况可以利用动态规划）。
class Solution {
public int maximizeTheProfit(int n, List<List<Integer>> offers) {
Collections.sort(offers, (a, b) -> (a.get(1).compareTo(b.get(1))));
TreeMap<Integer, Integer> score = new TreeMap<>();
score.put(-1, 0);
int max = 0;
for (List<Integer> arr : offers) {
int st = arr.get(0), ed = arr.get(1);
int preBest = score.floorEntry(ed).getValue();
int curScore = score.lowerEntry(st).getValue() + arr.get(2);
score.put(ed, Math.max(curScore, preBest));
max = Math.max(max, curScore);
}
return max;
}
}6467. Find the Longest Equal Subarray
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
子数组 是数组中一个连续且可能为空的元素序列。
测试样例
输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：
最优的方案是删除下标 2 和下标 4 的元素。删除后，nums 等于 [1, 3, 3, 3] 。最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。可以证明无法创建更长的等值子数组。
解答：题目主要考察的是折半搜索。利用折半搜索可以寻找最长可以符合要求的数组。每次折半搜索中，可以遍历数组，查看mid + k这个长度的数组中，是否存在同样的mid个数，如果存在就是true，否则是false。
class Solution {
public int longestEqualSubarray(List<Integer> nums, int k) {
int[] arr = new int[nums.size()];
int offset = 0;
for (int n : nums) {
arr[offset++] = n;
}
int st = 0, ed = arr.length + 1;
while (st < ed) {
int mid = (st + ed + 1) / 2;
if (isValid(arr, mid, k)) {
st = mid;
} else {
ed = mid - 1;
}
}
return st;
}
private boolean isValid(int[] nums, int len, int k) {
HashMap<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
int n = nums[i];
int c = count.getOrDefault(n, 0) + 1;
if (c >= len) {
return true;
}
count.put(n, c);
if (i >= len + k - 1) {
int r = nums[i - (len + k - 1)];
removeKey(count, r);
}
}
return false;
}
private void removeKey(Map<Integer, Integer> map, int key) {
int c = map.get(key);
if (c == 1) {
map.remove(key);
} else {
map.put(key, c - 1);
}
}
}