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就不少。