Leetcode - 140双周赛
目录
一，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();
}
}
原文地址：https://blog.csdn.net/m0_74859835/article/details/142707575
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！