100262. Find the Sum of Encrypted Integers
给你一个整数数组 nums ，数组中的元素都是 正 整数。定义一个加密函数 encrypt ，encrypt(x) 将一个整数 x 中 每一个 数位都用 x 中的 最大 数位替换。比方说 encrypt(523) = 555 且 encrypt(213) = 333 。
请你返回数组中所有元素加密后的 和 。
测试样例：
输入：nums = [1,2,3]
输出：6
解释：加密后的元素位 [1,2,3] 。加密元素的和为 1 + 2 + 3 == 6 。
解答：按照题意，变化每个数字并累加。
class Solution {
public int sumOfEncryptedInt(int[] nums) {
int res = 0;
for (int n : nums) {
res += max(n);
}
return res;
}
private int max(int num) {
String tmp = String.valueOf(num);
int max = 0;
for (int i = 0; i < tmp.length(); ++i) {
max = Math.max(max, tmp.charAt(i) - '0');
}
StringBuilder res = new StringBuilder();
for (int i = 0; i < tmp.length(); ++i) {
res.append(max);
}
return Integer.parseInt(res.toString());
}
}100209. Mark Elements on Array by Performing Queries
给你一个长度为 n 下标从 0 开始的正整数数组 nums 。
同时给你一个长度为 m 的二维操作数组 queries ，其中 queries[i] = [indexi, ki] 。
一开始，数组中的所有元素都 未标记 。
你需要依次对数组执行 m 次操作，第 i 次操作中，你需要执行：
- 如果下标 indexi 对应的元素还没标记，那么标记这个元素。
- 然后标记 ki 个数组中还没有标记的 最小 元素。如果有元素的值相等，那么优先标记它们中下标较小的。如果少于 ki 个未标记元素存在，那么将它们全部标记。
请你返回一个长度为 m 的数组 answer ，其中 answer[i]是第 i 次操作后数组中还没标记元素的 和 。
测试样例：
输入：nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]
输出：[8,3,0]
解释：我们依次对数组做以下操作：
- 标记下标为 1 的元素，同时标记 2 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 2 + 2 + 3 + 1 = 8 。
- 标记下标为 3 的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的 3 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 3 。
- 标记下标为 4 的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的 2 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 0 。
解答：利用优先队列将当前数组进行排序，然后引入一个标记数组，最后完成当前数组累和。遍历所有query元素，按照题意完成第index位标记，并寻找最小的k个未标记的数，所有未标记数从累和中扣除。
class Solution {
public long[] unmarkedSumArray(int[] nums, int[][] queries) {
long sum = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (Integer.compare(nums[a], nums[b]) == 0
? Integer.compare(a, b) : Integer.compare(nums[a], nums[b])));
for (int i = 0; i < nums.length; ++i) {
queue.add(i);
sum += nums[i];
}
long[] res = new long[queries.length];
boolean[] isMark = new boolean[nums.length];
for (int i = 0; i < res.length; ++i) {
if (!isMark[queries[i][0]]) {
sum -= nums[queries[i][0]];
isMark[queries[i][0]] = true;
}
int remain = queries[i][1];
while (!queue.isEmpty() && remain > 0) {
int tmp = queue.poll();
if (!isMark[tmp]) {
isMark[tmp] = true;
sum -= nums[tmp];
--remain;
}
}
res[i] = sum;
}
return res;
}
}100249. Replace Question Marks in String to Minimize Its Value
给你一个字符串 s 。s[i] 要么是小写英文字母，要么是问号 '?' 。
对于长度为 m 且 只 含有小写英文字母的字符串 t ，我们定义函数 cost(i) 为下标 i 之前（也就是范围 [0, i - 1] 中）出现过与 t[i] 相同 字符出现的次数。
字符串 t 的 分数 为所有下标 i 的 cost(i) 之 和 。
比方说，字符串 t = "aab" ：
- cost(0) = 0
- cost(1) = 1
- cost(2) = 0
- 所以，字符串 "aab" 的分数为 0 + 1 + 0 = 1 。
你的任务是用小写英文字母 替换 s 中 所有 问号，使 s 的 分数最小 。
请你返回替换所有问号 '?' 之后且分数最小的字符串。如果有多个字符串的 分数最小 ，那么返回字典序最小的一个。
测试样例：
输入：s = "???"
输出："abc"
解释：这个例子中，我们将 s 中的问号 '?' 替换得到 "abc" 。对于字符串 "abc" ，cost(0) = 0 ，cost(1) = 0 和 cost(2) = 0 。"abc" 的分数为 0 。其他修改 s 得到分数 0 的字符串为 "cba" ，"abz" 和 "hey" 。这些字符串中，我们返回字典序最小的。
解答：这周个人认为最难的一题，是一道脑筋急转弯题。对于每个?字符，可以认为它是对当前所有已经确认的某个字符的累和。那么每个?都是寻找当前哪个字符出现最少的过程。?的替换顺序其实不重要，获取字符串之后，排序插入即可。
class Solution {
public String minimizeStringValue(String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) != '?') {
count[s.charAt(i) - 'a'] += 1;
}
}
List<Character> list = new ArrayList<>();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '?') {
int min = Integer.MAX_VALUE, pos = 0;
for (int j = 0; j < 26; ++j) {
if (min > count[j]) {
min = count[j];
pos = j;
}
}
list.add((char)(pos + 'a'));
count[pos] += 1;
}
}
Collections.sort(list);
StringBuilder res = new StringBuilder();
int pos = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) != '?') {
res.append(s.charAt(i));
} else {
res.append(list.get(pos++));
}
}
return res.toString();
}
}100216. Maximum Strength of K Disjoint Subarrays
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。
一个整数数组的 能量 定义为和 等于 k 的子序列的数目。
请你返回 nums 中所有子序列的 能量和 。
由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。
测试样例：
输入：nums = [1,2,3], k = 3
输出：6
解释：总共有 5 个能量不为 0 的子序列：
- 子序列 [1,2,3] 有 2 个和为 3 的子序列：[1,2,3] 和 [1,2,3] 。
- 子序列 [1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。
- 子序列 [1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。
- 子序列 [1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。
- 子序列 [1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。
所以答案为 2 + 1 + 1 + 1 + 1 = 6 。
解答：k的范围不大，其实可以遍历并搜索所有小于等于k的数字，属于的子序列数。逻辑比较简单，遍历数字。如果当前数字选择不加入，那么当前累和子序列次数*2（加入，不加入两种情况）。选择加入，那么对当前累和+n进行更新。
class Solution {
private static final int mod = 1_000_000_007;
public int sumOfPower(int[] nums, int k) {
int[] mem = new int[k + 1];
mem[0] = 1;
for (int n : nums) {
int[] nextMem = new int[k + 1];
for (int j = k; j >= 0; --j) {
nextMem[j] = (2 * mem[j]) % mod;
if (j - n >= 0) {
nextMem[j] = (nextMem[j] + mem[j - n]) % mod;
}
}
mem = nextMem;
}
return mem[k];
}
}