100221. Maximum Number of Operations With the Same Score I
给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作：
- 选择 nums 中的前两个元素并将它们删除。
一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
测试样例：
输入：nums = [3,2,1,4,5]
输出：2
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,4,5] 。
- 删除前两个元素，分数为 1 + 4 = 5 ，nums = [5] 。
由于只剩下 1 个元素，我们无法继续进行任何操作。
解答：按照题意，按照顺序删除前缀并判断元素和是否一致。
class Solution {
public int maxOperations(int[] nums) {
int target = nums[0] + nums[1];
int res = 0;
for (int i = 0; i + 1 < nums.length; i = i + 2) {
if (nums[i] + nums[i + 1] == target) {
++res;
} else {
break;
}
}
return res;
}
}100211. Apply Operations to Make String Empty
给你一个字符串 s 。
请你进行以下操作直到 s 为 空 ：
- 每次操作 依次 遍历 'a' 到 'z'，如果当前字符出现在 s 中，那么删除出现位置 最早 的该字符。
请你返回进行 最后 一次操作 之前 的字符串 s 。
测试样例：
输入：s = "aabcbbca"
输出："ba"
解释：我们进行以下操作：
- 删除 s = "aabcbbca" 中加粗加斜字符，得到字符串 s = "abbca" 。
- 删除 s = "abbca" 中加粗加斜字符，得到字符串 s = "ba" 。
- 删除 s = "ba" 中加粗加斜字符，得到字符串 s = "" 。
进行最后一次操作之前的字符串为 "ba" 。
解答：每次都会把'a'到'z'，最早的字符去掉，然后题目有要求我们保留最后一次操作前的字符串。那么比较简单的算法就是计算每个字符出现的次数，最后一次删除的必然是出现频率最大的一批。然后按照最后一个字符出现位置排序就是答案。
class Solution {
public String lastNonEmptyString(String s) {
int[] count = new int[26], last = new int[26];
for (int i = 0; i < s.length(); ++i) {
int o = s.charAt(i) - 'a';
count[o] += 1;
last[o] = i;
}
int max = 0;
for (int n : count) {
max = Math.max(n, max);
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 26; ++i) {
if (count[i] == max) {
list.add(i);
}
}
Collections.sort(list, (a, b) -> (last[a] - last[b]));
StringBuilder sb = new StringBuilder();
for (int n : list) {
sb.append((char)(n + 'a'));
}
return sb.toString();
}
}100220. Maximum Number of Operations With the Same Score II
给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：
- 选择 nums 中最前面两个元素并且删除它们。
- 选择 nums 中最后两个元素并且删除它们。
- 选择 nums 中第一个和最后一个元素并且删除它们。
一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
测试样例：
输入：nums = [3,2,1,2,3,4]
输出：3
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
- 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
- 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
由于 nums 为空，我们无法继续进行任何操作。
解答：第一题的加强版，存在三种不同删除的可能。我们利用动态规划记录中间状态，并计算每种开局最大的操作数。
class Solution {
public int maxOperations(int[] nums) {
int len = nums.length - 1;
return Math.max(helper(nums, nums[0] + nums[1]),
Math.max(helper(nums, nums[0] + nums[len]), helper(nums, nums[len] + nums[len - 1])));
}
private int helper(int[] nums, int target) {
int st = 0, ed = nums.length - 1;
Integer[][] mem = new Integer[nums.length][nums.length];
return helper(nums, target, mem, st, ed);
}
private int helper(int[] nums, int target, Integer[][] mem, int st, int ed) {
if (ed - st <= 0) {
return 0;
}
int key = st * nums.length + ed;
if (mem[st][ed] == null) {
int max = 0;
if (nums[st] + nums[ed] == target) {
max = helper(nums, target, mem, st + 1, ed - 1) + 1;
}
if (nums[st] + nums[st + 1] == target) {
max = Math.max(max, helper(nums, target, mem, st + 2, ed) + 1);
}
if (nums[ed] + nums[ed - 1] == target) {
max = Math.max(max, helper(nums, target, mem, st, ed - 2) + 1);
}
mem[st][ed] = max;
}
return mem[st][ed];
}
}100205. Maximize Consecutive Elements in an Array After Modification
给你一个下标从 0 开始只包含 正 整数的数组 nums 。
一开始，你可以将数组中 任意数量 元素增加 至多 1 。
修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说，[3, 4, 5] 是连续的，但是 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。
请你返回 最多 可以选出的元素数目。
测试样例：
输入：nums = [2,1,5,1,1]
输出：3
解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。最多可以得到 3 个连续元素。
解答：这题还是挺简单的，主要是细心一点。首先对数组排序，然后我们遍历数组。当前数有2种可能，+1或者不操作。利用动态规划分别记录这两种情况能到达的最大数组长度。
class Solution {
public int maxSelectedElements(int[] nums) {
Arrays.sort(nums);
HashMap<Integer, Integer> mem = new HashMap<>();
int res = 0;
for (int n : nums) {
{
int tmp = Math.max(mem.getOrDefault(n + 1, 0),
mem.containsKey(n) ? (mem.get(n) + 1) : 1);
mem.put(n + 1, tmp);
res = Math.max(res, tmp);
}
{
int tmp = Math.max(mem.getOrDefault(n, 0),
mem.containsKey(n - 1) ? (mem.get(n - 1) + 1) : 1);
mem.put(n, tmp);
res = Math.max(res, tmp);
}
}
return res;
}
}