image.png
昨晚掉的分又打回来了。。。
T3wrong一次因为哈希冲突了，后来改成了暴力，用字符串做哈希

6047. 移除指定数字得到的最大结果

给你一个表示某个正整数的字符串 number 和一个字符 digit 。
从 number 中 恰好 移除 一个 等于 digit 的字符后，找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。

示例 1：
输入：number = “123”, digit = “3” 输出：“12” 解释：“123” 中只有一个 ‘3’ ，在移除 ‘3’ 之后，结果为 “12” 。
示例 2：
输入：number = “1231”, digit = “1” 输出：“231” 解释：可以移除第一个 ‘1’ 得到 “231” 或者移除第二个 ‘1’ 得到 “123” 。 由于 231 > 123 ，返回 “231” 。
示例 3：
输入：number = “551”, digit = “5” 输出：“51” 解释：可以从 “551” 中移除第一个或者第二个 ‘5’ 。 两种方案的结果都是 “51” 。

提示：

  • 2 <= number.length <= 100
  • number 由数字 ‘1’ 到 ‘9’ 组成
  • digit 是 ‘1’ 到 ‘9’ 中的一个数字
  • digit 在 number 中出现至少一次

思路：
模拟
时间复杂度：O(n2)
空间复杂度：O(n)

  1. class Solution {
  2.     public String removeDigit(String number, char digit) {
  3.         int n = number.length();
  5.         String res = null;
  6.         for (int i = 0; i < n; i++) {
  7.             if (number.charAt(i) != digit)
  8.                 continue;
  10.             StringBuilder sb = new StringBuilder();
  11.             for (int j = 0; j < n; j++) {
  12.                 if (j == i) continue;
  13.                 sb.append(number.charAt(j));
  14.             }
  16.             if (res == null || sb.toString().compareTo(res) > 0)
  17.                 res = sb.toString();
  18.         }
  19.         return res;
  20.     }
  21. }

6048. 必须拿起的最小连续卡牌数

给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。
返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。

示例 1：
输入：cards = [3,4,2,3,4,7] 输出：4 解释：拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意，拿起 [4,2,3,4] 也是最优方案。
示例 2：
输入：cards = [1,0,5,3] 输出：-1 解释：无法找出含一对匹配卡牌的一组连续卡牌。

提示：

  • 1 <= cards.length <= 105
  • 0 <= cards[i] <= 106

思路：
贪心
时间复杂度：O(n)
空间复杂度：O(n)

  1. class Solution {
  2.     public int minimumCardPickup(int[] cards) {
  3.         Map<Integer, Integer> map = new HashMap<>();
  4.         int n = cards.length;
  6.         int min = 0x3f3f3f3f;
  7.         for (int i = 0; i < n; i++) {
  8.             int x = cards[i];
  9.             if (map.containsKey(x)) {
  10.                 min = Math.min(min, i - map.get(x) + 1);
  11.             }
  12.             map.put(x, i);
  13.         }
  14.         return min == 0x3f3f3f3f ? -1 : min;
  15.     }
  16. }

6049. 含最多 K 个可整除元素的子数组

给你一个整数数组 nums 和两个整数 k 和 p ，找出并返回满足要求的不同的子数组数，要求子数组中最多 k 个可被 p 整除的元素。
如果满足下述条件之一，则认为数组 nums1 和 nums2 是 不同 数组：

  • 两数组长度 不同 ，或者
  • 存在 至少 一个下标 i 满足 nums1[i] != nums2[i] 。

子数组 定义为：数组中的连续元素组成的一个 非空 序列。

示例 1：
输入：nums = [2,3,3,2,2], k = 2, p = 2 输出：11 解释： 位于下标 0、3 和 4 的元素都可以被 p = 2 整除。 共计 11 个不同子数组都满足最多含 k = 2 个可以被 2 整除的元素： [2]、[2,3]、[2,3,3]、[2,3,3,2]、[3]、[3,3]、[3,3,2]、[3,3,2,2]、[3,2]、[3,2,2] 和 [2,2] 。 注意，尽管子数组 [2] 和 [3] 在 nums 中出现不止一次，但统计时只计数一次。 子数组 [2,3,3,2,2] 不满足条件，因为其中有 3 个元素可以被 2 整除。
示例 2：
输入：nums = [1,2,3,4], k = 4, p = 1 输出：10 解释： nums 中的所有元素都可以被 p = 1 整除。 此外，nums 中的每个子数组都满足最多 4 个元素可以被 1 整除。 因为所有子数组互不相同，因此满足所有限制条件的子数组总数为 10 。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i], p <= 200
  • 1 <= k <= nums.length

思路：
暴力 + 哈希
时间复杂度：O(n3)
空间复杂度：O(n2)

  1. class Solution {
  2.     public int countDistinct(int[] nums, int k, int p) {
  3.         int n = nums.length;
  4.         boolean[] st = new boolean[n];
  6.         for (int i = 0; i < n; i++) {
  7.             if (nums[i] % p == 0)
  8.                 st[i] = true;
  9.         }
  11.         int sum = 0;
  12.         for (int len = 1; len <= n; len++) {
  13.             Set<String> set = new HashSet<>();
  14.             for (int l = 0; l + len - 1 < n; l++) {
  15.                 int r = l + len - 1;
  16.                 int cnt = 0;
  17.                 StringBuilder sb = new StringBuilder();
  18.                 for (int i = l; i <= r; i++) {
  19.                     if (st[i]) cnt++;
  20.                     sb.append(nums[i] + " ");
  21.                 }
  22.                 if (cnt <= k && !set.contains(sb.toString())) {
  23.                      sum++;
  24.                     set.add(sb.toString());
  25.                 }
  26.             }
  27.         }
  28.         return sum;
  29.     }
  30. }

6050. 字符串的总引力

字符串的 引力 定义为：字符串中 不同 字符的数量。

  • 例如，”abbca” 的引力为 3 ，因为其中有 3 个不同字符 ‘a’、’b’ 和 ‘c’ 。

给你一个字符串 s ，返回 其所有子字符串的总引力 。
子字符串 定义为：字符串中的一个连续字符序列。

示例 1：
输入：s = “abbca” 输出：28 解释：“abbca” 的子字符串有： - 长度为 1 的子字符串：”a”、”b”、”b”、”c”、”a” 的引力分别为 1、1、1、1、1，总和为 5 。 - 长度为 2 的子字符串：”ab”、”bb”、”bc”、”ca” 的引力分别为 2、1、2、2 ，总和为 7 。 - 长度为 3 的子字符串：”abb”、”bbc”、”bca” 的引力分别为 2、2、3 ，总和为 7 。 - 长度为 4 的子字符串：”abbc”、”bbca” 的引力分别为 3、3 ，总和为 6 。 - 长度为 5 的子字符串：”abbca” 的引力为 3 ，总和为 3 。 引力总和为 5 + 7 + 7 + 6 + 3 = 28 。
示例 2：
输入：s = “code” 输出：20 解释：“code” 的子字符串有： - 长度为 1 的子字符串：”c”、”o”、”d”、”e” 的引力分别为 1、1、1、1 ，总和为 4 。 - 长度为 2 的子字符串：”co”、”od”、”de” 的引力分别为 2、2、2 ，总和为 6 。 - 长度为 3 的子字符串：”cod”、”ode” 的引力分别为 3、3 ，总和为 6 。 - 长度为 4 的子字符串：”code” 的引力为 4 ，总和为 4 。 引力总和为 4 + 6 + 6 + 4 = 20 。

提示：

  • 1 <= s.length <= 105
  • s 由小写英文字母组成

思路：
思维题
考虑每个字符作为子串中该字符第一次出现的所有子串
从前往后遍历，当前字符在子串中首次出现意味着它在前面没有出现
统计每个字符能在哪些子串中作为该字符的首次出现字符即可

  1. class Solution {
  2.     public long appealSum(String s) {
  3.         long cnt = 0;
  4.         int n = s.length();
  6.         int[] pre = new int[26];
  7.         Arrays.fill(pre, -1);
  9.         for (int i = 0; i < n; i++) {
  10.             int idx = s.charAt(i) - 'a';
  11.             int r = n - i, l = i - pre[idx];
  12.             cnt += 1L * r * l;
  13.             pre[idx] = i;
  14.         }
  15.         return cnt;
  16.     }
  17. }