6462. Minimize String Length
给你一个下标从 0 开始的字符串 s ，重复执行下述操作 任意 次：
- 在字符串中选出一个下标 i ，并使 c 为字符串下标 i 处的字符。并在 i 左侧（如果有）和 右侧（如果有）各 删除 一个距离 i 最近 的字符 c 。
请你通过执行上述操作任意次，使 s 的长度 最小化 。
返回一个表示 最小化 字符串的长度的整数。
测试样例：
输入：s = "aaabc"
输出：3
解释：
整数 在这个示例中，s 等于 "aaabc" 。我们可以选择位于下标 1 处的字符 'a' 开始。接着删除下标 1 左侧最近的那个 'a'（位于下标 0）以及下标 1 右侧最近的那个 'a'（位于下标 2）。执行操作后，字符串变为 "abc" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 3 。
解答：每个操作，其实就是删除相同的字符。那么直到每个字符都只出现1次的时候，就无法继续操作了。所以寻找所有distinct的字符数量。
class Solution {
public int minimizedStringLength(String s) {
boolean[] count = new boolean[26];
int res = 0;
for (int i = 0; i < s.length(); ++i) {
int o = s.charAt(i) - 'a';
if (!count[o]) {
++res;
count[o] = true;
}
}
return res;
}
}6424. Semi-Ordered Permutation
给你一个下标从 0 开始、长度为 n 的整数排列 nums 。
如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：
- 选择 nums 中相邻的两个元素，然后交换它们。
返回使 nums 变成 半有序排列 所需的最小操作次数。
排列 是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。
测试样例：
输入：nums = [2,1,4,3]
输出：2
解释：
可以依次执行下述操作得到半有序排列：1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。可以证明，要让 nums 成为半有序排列，不存在执行操作少于 2 次的方案。
解答：这道题目重要查看1和nums.length出现的位置就可以了。但是要注意一个特殊情况：如果nums.length出现在1的左边，那么移动1的时候可以少移动一次。
class Solution {
public int semiOrderedPermutation(int[] nums) {
int res = 0;
boolean isMet = false;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == 1) {
res += i;
if (isMet) {
res -= 1;
}
} else if (nums[i] == nums.length) {
res += (nums.length - i - 1);
isMet = true;
}
}
return res;
}
}6472. Sum of Matrix After Queries
给你一个整数 n 和一个下标从 0 开始的 二维数组 queries ，其中 queries[i] = [typei, indexi, vali] 。
一开始，给你一个下标从 0 开始的 n x n 矩阵，所有元素均为 0 。每一个查询，你需要执行以下操作之一：
- 如果 typei == 0 ，将第 indexi 行的元素全部修改为 vali ，覆盖任何之前的值。
- 如果 typei == 1 ，将第 indexi 列的元素全部修改为 vali ，覆盖任何之前的值。
请你执行完所有查询以后，返回矩阵中所有整数的和。
测试样例
输入：n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出：23
解释：
上图展示了每个查询以后矩阵的值。所有操作执行完以后，矩阵元素之和为 23 。
解答：这道题目需要脑筋急转弯一下。我们可以从右向左遍历query。因为最后出现的query必然可以覆盖之前的操作，但是没办法覆盖之后的操作。所以从右开始遍历的话，如果row/col被占用了，那么之前的操作可覆盖的col/row就会减少1。如果row/col已经被占用，那么当前操作可以跳过。
class Solution {
public long matrixSumQueries(int n, int[][] queries) {
long row = n, col = n;
long res = 0;
boolean[] isRowUsed = new boolean[n], isColUsed = new boolean[n];
for (int i = queries.length - 1; i >= 0; --i) {
int[] q = queries[i];
if (q[0] == 0) {
if (!isColUsed[q[1]]) {
res += col * q[2];
row -= 1;
isColUsed[q[1]] = true;
}
} else {
if (!isRowUsed[q[1]]) {
res += row * q[2];
col -= 1;
isRowUsed[q[1]] = true;
}
}
}
return res;
}
}6396. Count of Integers
给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：
- num1 <= x <= num2
- min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大，请返回答案对 10^9 + 7 取余后的结果。
注意，digit_sum(x) 表示 x 各位数字之和。
测试样例
输入：num1 = "1", num2 = "12", min_num = 1, max_num = 8
输出：11
解释：总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。
解答：这道题目，我倒是觉得从编程角度还蛮难的。转换一下角度，num1 <= x <= num2可以理解为：(x <= num2的数目) - (x < num1的数目)。
那么接下来的难点就是寻找x < num的个数。这个时候其实就已经简单很多。我们直接遍历数字长度。如果位数小于当前位数，直接利用动态规划记录在范围内的数字数就行了。如果等于当前的位数，那么就要一位位比较。
如果当前位数字小于num的数字，那边还是可以利用之前动态规划的结果，计算总数目。否则进入下一位遍历。
class Solution {
private static final int mod = 1_000_000_007;
public int count(String num1, String num2, int min_sum, int max_sum) {
return delete(getCount(num2, min_sum, max_sum),
delete(getCount(num1, min_sum, max_sum), isValid(num1, min_sum, max_sum) ? 1 : 0));
}
private int getCount(String num, int minSum, int maxSum) {
int len = num.length();
int res = 0;
int[][] dp = new int[num.length()][maxSum + 1];
dp[0][0] = 1;
for (int i = 1; i <= len; ++i) {
if (i < len) {
int st = i == 1 ? 1 : 0;
for (int k = st; k <= 9; ++k) {
for (int m = maxSum; m >= k; --m) {
dp[i][m] = add(dp[i][m], dp[i - 1][m - k]);
}
}
res = add(res, addUp(dp[i], minSum, maxSum, 0));
} else {
int preSum = 0;
for (int p = 0; p < num.length(); ++p) {
int n = num.charAt(p) - '0';
int st = p == 0 ? 1 : 0;
for (int k = st; k < n; ++k) {
for (int remain = 0; remain <= num.length() - p - 1; ++remain) {
res = add(res, addUp(dp[remain], minSum, maxSum, preSum + k));
}
}
preSum += n;
}
}
}
return isValid(num, minSum, maxSum) ? add(res, 1) : res;
}
private int add(int x, int y) {
return (x + y) % mod;
}
private int delete(int x, int y) {
return (x - y + mod) % mod;
}
private int addUp(int[] arr, int min, int max, int offset) {
int sum = 0;
int st = Math.max(0, min - offset), ed = max - offset;
for (int i = st; i <= ed; ++i) {
sum = add(sum, arr[i]);
}
return sum;
}
private boolean isValid(String n, int min, int max) {
int add = 0;
for (int i = 0; i < n.length(); ++i) {
add += n.charAt(i) - '0';
}
return add >= min && add <= max;
}
}这周题目，还是有点难度的。最后一题如果之前没做过类似的题目，就算能想到解题方法，题目的corner case就不少。