6954. 统计和小于目标的下标对数目
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。
示例 1：
输入：nums = [-1,1,2,3,1], target = 2
输出：3
解释：总共有 3 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。
示例 2：
输入：nums = [-6,2,5,-2,-7,-1,3], target = -2
输出：10
解释：总共有 10 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
- (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
- (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
- (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
- (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
- (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
- (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
- (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
- (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target
提示：
1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50解答：时间复杂度(O(n^2)),直接暴力枚举
class Solution {
public int countPairs(List<Integer> nums, int target) {
int res=0;
int n=nums.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(nums.get(i)+nums.get(j)<target)res++;
}
}
return res;
}
}8014. 循环增长使字符串子序列等于另一个字符串
给你一个下标从 0 开始的字符串 str1 和 str2 。
一次操作中，你选择 str1 中的若干下标。对于选中的每一个下标 i ，你将 str1[i] 循环 递增，变成下一个字符。也就是说 'a' 变成 'b' ，'b' 变成 'c' ，以此类推，'z' 变成 'a' 。
如果执行以上操作 至多一次 ，可以让 str2 成为 str1 的子序列，请你返回 true ，否则返回 false 。
注意：一个字符串的子序列指的是从原字符串中删除一些（可以一个字符也不删）字符后，剩下字符按照原本先后顺序组成的新字符串。
示例 1：
输入：str1 = "abc", str2 = "ad"
输出：true
解释：选择 str1 中的下标 2 。
将 str1[2] 循环递增，得到 'd' 。
因此，str1 变成 "abd" 且 str2 现在是一个子序列。所以返回 true 。
示例 2：
输入：str1 = "zc", str2 = "ad"
输出：true
解释：选择 str1 中的下标 0 和 1 。
将 str1[0] 循环递增得到 'a' 。
将 str1[1] 循环递增得到 'd' 。
因此，str1 变成 "ad" 且 str2 现在是一个子序列。所以返回 true 。
示例 3：
输入：str1 = "ab", str2 = "d"
输出：false
解释：这个例子中，没法在执行一次操作的前提下，将 str2 变为 str1 的子序列。
所以返回 false 。
提示：
1 <= str1.length <= 10^5
1 <= str2.length <= 10^5
str1 和 str2 只包含小写英文字母。解答：双指针遍历
class Solution {
public boolean canMakeSubsequence(String str1, String str2) {
int m=str1.length(),n=str2.length();
for(int i=0,j=0;i<m;i++){
char c=str1.charAt(i);
char c1=str2.charAt(j);
//三种分类
if(c==c1||c+1==c1||c=='z'&&c1=='a'){
j++;
//str2遍历完返回true
if(n==j)return true;
}
}
return false;
}
}6941. 将三个组排序
给你一个下标从 0 开始长度为 n 的整数数组 nums 。
从 0 到 n - 1 的数字被分为编号从 1 到 3 的三个组，数字 i 属于组 nums[i] 。注意，有的组可能是 空的 。
你可以执行以下操作任意次：
选择数字 x 并改变它的组。更正式的，你可以将 nums[x] 改为数字 1 到 3 中的任意一个。
你将按照以下过程构建一个新的数组 res ：
将每个组中的数字分别排序。
将组 1 ，2 和 3 中的元素 依次 连接以得到 res 。
如果得到的 res 是 非递减顺序的，那么我们称数组 nums 是 美丽数组 。
请你返回将 nums 变为 美丽数组 需要的最少步数。
示例 1：
输入：nums = [2,1,3,2,1]
输出：3
解释：以下三步操作是最优方案：
1. 将 nums[0] 变为 1 。
2. 将 nums[2] 变为 1 。
3. 将 nums[3] 变为 1 。
执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3,4] ，组 2 和组 3 都为空。所以 res 等于 [0,1,2,3,4] ，它是非递减顺序的。
三步操作是最少需要的步数。
示例 2：
输入：nums = [1,3,2,1,3,3]
输出：2
解释：以下两步操作是最优方案：
1. 将 nums[1] 变为 1 。
2. 将 nums[2] 变为 1 。
执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3] ，组 2 为空，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。
两步操作是最少需要的步数。
示例 3：
输入：nums = [2,2,2,2,3,3]
输出：0
解释：不需要执行任何操作。
组 1 为空，组 2 为 [0,1,2,3] ，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 3解答：//数据范围1-100，可以采用O(n^3)
也可以使用DP，时间复杂度O(n)
//数据范围1-100，可以采用O(n^3)
class Solution {
public int minimumOperations(List<Integer> nums) {
int n=nums.size();
int res=n;
for(int i=0;i<=n;i++){
for(int j=0;j+i<=n;j++){
int count=0;
for(int k=0;k<n;k++){
int t=0;
//在第一段
if(k<=i-1)t=1;
//在第二段
else if(k<=i+j-1)t=2;
//在第三段
else t=3;
if(t!=nums.get(k))count++;
}
res=Math.min(res,count);
}
}
return res;
}
}动态规划
class Solution {
public int minimumOperations(List<Integer> nums) {
int n=nums.size();
int[][] f=new int[n][4];
//初始化f[i][j]
for(int i=1;i<=3;i++)f[0][i]=1;
f[0][nums.get(0)]=0;
for(int i=1;i<n;i++){
for(int j=1;j<=3;j++){
int t=0;
if(j!=nums.get(i))t=1;
f[i][j]=f[i-1][j]+t;
for(int k=1;k<j;k++){
f[i][j]=Math.min(f[i][j],f[i-1][k]+t);
}
}
}
return Math.min(Math.min(f[n-1][1],f[n-1][2]),f[n-1][3]);
}
}8013. 范围中美丽整数的数目
给你正整数 low ，high 和 k 。
如果一个数满足以下两个条件，那么它是 美丽的 ：
偶数数位的数目与奇数数位的数目相同。
这个整数可以被 k 整除。
请你返回范围 [low, high] 中美丽整数的数目。
示例 1：
输入：low = 10, high = 20, k = 3
输出：2
解释：给定范围中有 2 个美丽数字：[12,18]
- 12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
- 18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
以下是一些不是美丽整数的例子：
- 16 不是美丽整数，因为它不能被 k = 3 整除。
- 15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
给定范围内总共有 2 个美丽整数。
示例 2：
输入：low = 1, high = 10, k = 1
输出：1
解释：给定范围中有 1 个美丽数字：[10]
- 10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。
给定范围内总共有 1 个美丽整数。
示例 3：
输入：low = 5, high = 5, k = 2
输出：0
解释：给定范围中有 0 个美丽数字。
- 5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
提示：
0 < low <= high <= 10^9
0 < k <= 20解答：数位DP
class Solution {
public int numberOfBeautifulIntegers(int low, int high, int k) {
return calc(high, k) - calc(low - 1, k);
}
private int calc(int high, int k) {
var s = Integer.toString(high).toCharArray();
int n = s.length;
var memo = new int[n][k][n * 2 + 1];
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++)
Arrays.fill(memo[i][j], -1); // -1 表示没有计算过
return dfs(0, 0, n, true, false, k, s, memo);
}
private int dfs(int i, int val, int diff, boolean isLimit, boolean isNum, int k, char[] s, int[][][] memo) {
if (i == s.length)
return isNum && val == 0 && diff == s.length ? 1 : 0; // 找到了一个合法数字
if (!isLimit && isNum && memo[i][val][diff] != -1)
return memo[i][val][diff];
int res = 0;
if (!isNum) // 可以跳过当前数位
res = dfs(i + 1, val, diff, false, false, k, s, memo);
int up = isLimit ? s[i] - '0' : 9; // 如果前面填的数字都和 high 的一样，那么这一位至多填数字 s[i]（否则就超过 high 啦）
for (int d = isNum ? 0 : 1; d <= up; d++) // 枚举要填入的数字 d
res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, isLimit && d == up, true, k, s, memo);
if (!isLimit && isNum)
memo[i][val][diff] = res; // 记忆化搜索
return res;
}
}
