【LeetCode周赛】第 416 场

3295. 举报垃圾信息

给你一个字符串数组 message 和一个字符串数组 bannedWords。
如果数组中 至少 存在两个单词与 bannedWords 中的任一单词 完全相同，则该数组被视为 垃圾信息。
如果数组 message 是垃圾信息，则返回 true；否则返回 false。

---

思路：空间换时间，使用集合set存储bannedWords。
复杂度：O(n)

class Solution {
    public boolean reportSpam(String[] message, String[] bannedWords) {
        Set<String> set = new HashSet();
        for(String ban:bannedWords) {
            set.add(ban);
        }
        int cnt = 0;
        for(String msg:message) {
            if(set.contains(msg)) {
                cnt ++;
                if(cnt>=2) return true;
            }
        }

        return false;
    }
}

3296. 移山所需的最少秒数

给你一个整数 mountainHeight 表示山的高度。
同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :
山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + … + workerTimes[i] * x 秒。例如：
山的高度降低 1，需要 workerTimes[i] 秒。
山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。
返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。

---

思想：使用PriorityQueue。具体来说，PriorityQueue存储一个长度为3的数组nums[3]，其中nums[0]存储下一次该位需要的时间，nums[1]存储workTimes[i]，nums[2]存储下一次需要几个workTimes[i]。每次选取PriorityQueue最小的的nums[0]，ans为其中最大的，然后将nums[0]更新。
复杂度：O(n)。

class Solution {
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        Queue<Long[]> q = new PriorityQueue<>((a, b)->Long.compare(a[0], b[0]));
        // Arrays.sort(workerTimes);
        long ans = 0;
        for(int i=0; i<workerTimes.length; i++) {
            // 在下降一米所用， 速度， 用时
            q.offer(new Long[]{Long.valueOf(workerTimes[i]), Long.valueOf(workerTimes[i]), Long.valueOf(2)});
        }
        for(int i=0; i<mountainHeight; i++) {
            Long[] nd = q.poll();
            ans = Math.max(ans, nd[0]);
            nd[0] = nd[0] + nd[1]*nd[2];
            nd[2] ++;
            q.offer(nd);            
        }
        return ans;
    }
}

3297. 统计重新排列后包含另一个字符串的子字符串数目 I

给你两个字符串 word1 和 word2 。
如果一个字符串 x 重新排列后，word2 是重排字符串的
前缀 ，那么我们称字符串 x 是 合法的 。
请你返回 word1 中 合法
子字符串 的数目。

---

思路：滑动窗口，划出可以满足条件的窗口，然后窗口左端左移得到此刻最小的窗口，将left加入到答案。
复杂度：O(n).

class Solution {
    public long validSubstringCount(String word1, String word2) {
        // 滑动窗口，每一种符合条件的最小子串可以衍生出left个

        // w1和w2中每种字符数量
        int[] acnts = new int[128];
        int[] bcnts = new int[128];

        for(char c:word2.toCharArray()) {
            bcnts[c] ++;
        }

        int n = word1.length();
        long ans = 0;
        int l=0;
        // 以右端点为起点
        for(int r=0; r<n; r++) {
            acnts[word1.charAt(r)] ++;

            // w2中每个字符w1中都有时，尝试左移窗口变小，成为目前最短的子串
            while(check(acnts, bcnts)) {
                acnts[word1.charAt(l)] --;
                l ++;
            }
            ans += l;
        }
        return ans;
    }

    public boolean check(int[] acnts, int[] bcnts) {
        for(int i=0; i<128; i++) {
            if(acnts[i]<bcnts[i]) return false;
        }
        return true;
    }
}

优化：将两个统计字符的数组优化为一个。具体来说，cnts只记录word2中的字符，less记录不同字符的数量。窗口右移，对应的cnts的字符减一，注意words中没有的字符此时会减为负数，有的字符的cnts减为0时，less减一。less为0说明，是满足条件的窗口，尝试左移窗口左端，注意此时left对应的cnts为0，表明为word2中有的字符，less要加一，将left对应的字符加一。

class Solution {
    public long validSubstringCount(String word1, String word2) {
        // 滑动窗口，每一种符合条件的最小子串可以衍生出left个

        // w1和w2中每种字符数量
        int[] bcnts = new int[26];

        for(char c:word2.toCharArray()) {
            bcnts[c-'a'] ++;
        }

        int n = word1.length();
        long ans = 0;
        int l=0;
        // less表示w2中有多少个不同的字符
        int less = 0;
        for(int c:bcnts) {
            if(c>0) less ++;
        }
        // 以右端点为起点
        for(int r=0; r<n; r++) {
            // 未出现的字符的次数会变为负数
            if(--bcnts[word1.charAt(r)-'a'] == 0 ) {
                less --;
            }
            
            // w2中每个字符w1中都有时，尝试左移窗口变小，成为目前最短的子串
            while(less == 0) {
                // 当前次数为0，必是需要的
                if(bcnts[word1.charAt(l++)-'a']++ == 0) {
                    less ++;
                } 
            }
            ans += l;
        }
        return ans;
    }


}

原文地址：https://blog.csdn.net/qq_45722630/article/details/142467701

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！