目录

一，3300. 替换为数位和以后的最小元素

二，3301. 高度互不相同的最大塔高和

三，3302. 字典序最小的合法序列

四，3303. 第一个几乎相等子字符串的下标

---

一，3300. 替换为数位和以后的最小元素

本题直接暴力求解，代码如下：

class Solution {public int minElement(int[] nums) {int mn = Integer.MAX_VALUE;for(int x : nums){int res = 0;while(x > 0){res += x%10;x /= 10;}mn = Math.min(mn, res);}return mn;}
}

二，3301. 高度互不相同的最大塔高和

本题求最大总高度，从贪心的角度想，那必然是每个塔的高度越大越好，所以可以将maximumHeight 数组从大到小排序，使用一个变量 p 记录当前所能取到的最大值，对于下一个数x来说：

• 如果 x < p，就说明当前塔可以选取的高度为[1，x]，一定选 x，这时将 p = x；
• 如果 x >= p，由于数组从大到小排序的，所以当 x >= p 时，就说明 x 已经在之前取过了，此时塔可以选取的高度为[1，p-1]（注：p是上一次取过的值，不能再取），一定选 p-1，此时将 p = p-1。
• 注：题目要求所有塔的高度不能 <= 0，所以要加一个额外判断，如果 p <= 0，返回 -1

代码如下：

class Solution {public long maximumTotalSum(int[] h) {int n = h.length;long res = 0;Arrays.sort(h);int p = Integer.MAX_VALUE;for(int i=n-1; i>=0; i--){p = h[i] < p ? h[i] : p - 1; if(p <= 0) return -1;res += p;}return res;}
}

三，3302. 字典序最小的合法序列

本题可以使用前后缀分解的方式来解决，可以预处理 suf[i]：对于 w1[i:] 的子序列来说，他能匹配w2的最长后缀为 w2[j:]（j=suf[i]），然后直接枚举修改的下标：

• 如果 w1[i] == w2[j]，直接把 i 加入答案。因为题目要求字典序最小
• 如果 w1[i] != w2[j]，那么需要判断 suf[i+1] 是否小于等于 j+1，如果是，说明修改 w2[i] 后w2[j+1:] 是 w1[i+1:] 的子序列，此时一定要修改（只能修改一次），因为题目要求字典序最小，将 i 加入答案。

代码如下：

class Solution {public int[] validSequence(String word1, String word2) {char[] w1 = word1.toCharArray();char[] w2 = word2.toCharArray();int m = w1.length, n = w2.length;int[] suf = new int[m+1];//suf[i]:w2[j:]是w1[i:]的子序列（j=suf[i]）suf[m] = n;for(int i=m-1, j=n-1; i>=0; i--){if(j>=0 && w1[i] == w2[j]){j--;}suf[i] = j + 1;}int[] ans = new int[n];int j = 0;boolean changed = false;for(int i=0; i<m; i++){if(w1[i] == w2[j] || !changed && suf[i+1]<=j+1){if(w1[i] != w2[j]){changed = true;}ans[j++] = i;if(j == n) return ans;}}return new int[0];}
}

四，3303. 第一个几乎相等子字符串的下标

本题和T3类似，还是使用前后缀分解，只不过这里匹配的不是子序列而是子串，所以这里使用z函数来预处理前后缀，然后枚举修改的下标，判断它的前后缀加起来是否能组成 pattern。

代码如下：

class Solution {public int minStartingIndex(String s, String pattern) {int[] pre = zBox(pattern + s);int[] suf = zBox(rev(pattern) + rev(s));int m = s.length(), n = pattern.length();for(int i=n; i<=m; i++){if(pre[i] + suf[n+m-i] >= n-1)return i - n;}return -1;}int[] zBox(String s){char[] ch = s.toCharArray();int n = ch.length;int[] z = new int[n];z[0] = n;int l = 0, r = 0;for(int i=1; i<n; i++){z[i] = i < r ? Math.min(z[i-l], r-i) : 0;while(i + z[i] < n && ch[z[i]] == ch[i+z[i]]){l = i;r = i + z[i];z[i]++;}}return z;}String rev(String s){return new StringBuilder(s).reverse().toString();}
}