14-周赛348总结
T3还是想不到想不到，技巧性好强
T4数位dp花了点时间做出来了
最小化字符串长度【LC2716】
给你一个下标从 0 开始的字符串 s ，重复执行下述操作 任意 次：
- 在字符串中选出一个下标
i，并使c为字符串下标i处的字符。并在i左侧（如果有）和 右侧（如果有）各 删除 一个距离i最近 的字符c。
- （如果有）各 删除 一个距离
i最近 的字符c。请你通过执行上述操作任意次，使
s的长度 最小化 。返回一个表示 最小化 字符串的长度的整数。
哈希表
- 思路
每次操作选择一个字符，可以删除其左右的相同字符，执行任意次后，最终每种字符只剩下一个，因此最终结果即为字符串中的字符种类数目 - 实现
class Solution { public int minimizedStringLength(String s) { int n = s.length(); Set<Character> set = new HashSet<>(); for (char c : s.toCharArray()){ set.add(c); } return set.size(); } }
class Solution { public int minimizedStringLength(String s) { int mask = 0; for (var c : s.toCharArray()) mask |= 1 << (c - 'a'); return Integer.bitCount(mask); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/minimize-string-length/solutions/2296066/o1-kong-jian-wei-yun-suan-xie-fa-pythonj-7t4p/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
半有序排列【LC2717】
给你一个下标从 0 开始、长度为
n的整数排列nums。如果排列的第一个数字等于
1且最后一个数字等于n，则称其为 半有序排列 。你可以执行多次下述操作，直到将nums变成一个 半有序排列 ：
- 选择
nums中相邻的两个元素，然后交换它们。
返回使 nums 变成 半有序排列 所需的最小操作次数。
排列 是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。
思路：分类讨论
class Solution { public int semiOrderedPermutation(int[] nums) { int n = nums.length; if (nums[0] == 1 && nums[n - 1] == n){ return 0; } int index1 = -1, indexN = -1; // 先找到1和n的下标 for (int i = 0; i < n; i++){ if (nums[i] == 1){ index1 = i; }else if(nums[i] == n){ indexN = i; } } int res = index1 + (n - 1 - indexN); if (index1 > indexN){// indexN后移一格 return res - 1; } return res; } }
查询后矩阵的和【LC2718】
给你一个整数
n和一个下标从 0 开始的 二维数组queries，其中queries[i] = [typei, indexi, vali]。
一开始，给你一个下标从 0 开始的 n x n 矩阵，所有元素均为 0 。每一个查询，你需要执行以下操作之一：
- 如果
typei == 0，将第indexi 行的元素全部修改为 vali ，覆盖任何之前的值。
- 如果
typei == 1，将第indexi列的元素全部修改为vali，覆盖任何之前的值。请你执行完所有查询以后，返回矩阵中所有整数的和。
- 思路：逆序操作
- 如果对每个位置进行反复操作，那么只有最后一次的操作会计入答案，那么可以倒序操作
queries
class Solution { public long matrixSumQueries(int n, int[][] queries) { long res = 0L; Set<Integer> visRow = new HashSet<>(); Set<Integer> visCol = new HashSet<>(); for (int i = queries.length - 1; i >= 0; i--){ if (queries[i][0] == 0 && !visRow.contains(queries[i][1])){// 对行操作 res += queries[i][2] * (n - visCol.size()); visRow.add(queries[i][1]); }else if(queries[i][0] == 1 && !visCol.contains(queries[i][1])){ res += queries[i][2] * (n - visRow.size()); visCol.add(queries[i][1]); } } return res; } }
统计整数数目【LC2719】
给你两个数字字符串
num1和num2，以及两个整数max_sum和min_sum。如果一个整数x满足以下条件，我们称它是一个好整数：
num1 <= x <= num2min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7取余后的结果。
注意，digit_sum(x) 表示 x 各位数字之和。
import java.math.*; class Solution { int MOD = (int)(1e9 + 7); int min_sum; int max_sum; public int count(String num1, String num2, int min_sum, int max_sum) { // 数位dp this.min_sum = min_sum; this.max_sum = max_sum; BigInteger a1 = new BigInteger(num1); BigInteger a2 = new BigInteger("1"); a1 = a1.subtract(a2); // Long down = Long.valueOf(num1) - 1; char[] s1 = a1.toString().toCharArray(); char[] s2 = num2.toCharArray(); int[][] dp1 = new int[s1.length][max_sum + 1]; int[][] dp2 = new int[s2.length][max_sum + 1]; for (int i = 0; i < s1.length; i++){ Arrays.fill(dp1[i], -1); } for (int i = 0; i < s2.length; i++){ Arrays.fill(dp2[i], -1); } // 统计[num1, num2]中数位之和小于等于max_sum大于等于min_sum的个数 return (f(s2, dp2, 0, 0, true) - f(s1,dp1, 0, 0, true) + MOD) % MOD;// 防止出现负数 } // 统计[0, num]中数位之和小于等于max_sum大于等于min_sum的个数 public int f(char[] s, int[][] dp, int i, int sum, boolean isLimit){ if (i == s.length) return sum >= min_sum ? 1 : 0;// 数位之和大于下限，数量+1 if (!isLimit && dp[i][sum] != -1) return dp[i][sum]; int res = 0; int up = isLimit ? s[i] - '0' : 9; for (int a = 0; a <= up; a++){ if (sum + a > maxSum) break;// 数位之和超上限，不可以继续构造 res = (f(s, dp, i + 1, sum + a, isLimit && a == s[i] - '0') + res) % MOD; } if (!isLimit){ dp[i][sum] = res; } return res; } }
