Leetcode - 140双周赛

目录

一，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();
    }
}