【周赛总结】周赛356

简介: 【周赛总结】周赛356

周赛356

T2T3少写条件各WA一次,T4忘记取余WA一次,时间不够没有通过,可惜

满足目标工作时长的员工数目【LC2798】

公司里共有 n 名员工,按从 0n - 1 编号。每个员工 i 已经在公司工作了 hours[i] 小时。

公司要求每位员工工作 至少target 小时。

给你一个下标从 0 开始、长度为 n 的非负整数数组 hours 和一个非负整数 target

请你用整数表示并返回工作至少 target 小时的员工数。

  • 实现:模拟+计数
class Solution {
    public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {
        int res = 0;
        for (int h : hours){
            if (h >= target){
                res++;
            }
        }
        return res;
    }
}

image.png


统计完全子数组的数目【LC2799】

给你一个由 整数组成的数组 nums

如果数组中的某个子数组满足下述条件,则称之为 完全子数组

  • 子数组中 不同 元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

image.png

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int count = map.size();
        int res = 0, n = nums.length;
        // 对于每个l,找到其最左边合法的r,以l为左端点的完全子数组个数为n - r
        // 对于nums[0, r],r右边的一定合法
        int r = n - 1;
         while (r > 0 && map.get(nums[r]) > 1){
            map.put(nums[r], map.get(nums[r]) - 1);
            r--;
        }
        for (int l = 0; l < n; l++){
            while (r + 1 < n && map.size() < count){
                r++;
                map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);
            }
            if (map.size() == count){
                res += n - r;
            }     
            // 移除nums[l]
            map.put(nums[l], map.get(nums[l]) - 1);
            if (map.get(nums[l]) == 0){
                map.remove(nums[l]);
            }
        }
        return res;
    }
}

image.png

包含三个字符串的最短字符串【LC2800】

给你三个字符串 abc , 你的任务是找到长度 最短 的字符串,且这三个字符串都是它的 子字符串

如果有多个这样的字符串,请你返回 字典序最小 的一个。

请你返回满足题目要求的字符串。

注意:

  • 两个长度相同的字符串 ab ,如果在第一个不相同的字符处,a 的字母在字母表中比 b 的字母 靠前 ,那么字符串 a 比字符串 b字典序小
  • 子字符串 是一个字符串中一段连续的字符序列。

思路

  • 先考虑包含两个字符串的最短字符串,此时有两种可能结果,在a的末尾添加最少字符使其包含b的字符串或者在b的末尾添加最少字符使其包含a的字符串;

扩展至包含两个字符串的最短字符串时,有6种情况,取长度 最短 的字符串返回,长度相同时,取字典序最小的字符串

  • abc:先找到在a的末尾添加最少字符使其包含b的最短字符串,再在得到的字符串末尾添加最少字符使其包含c
  • acb
  • bac
  • bca
  • cab
  • cba
  • 如何找到在a的末尾添加最少字符使其包含b的字符串
  • 如果a包含b那么即为a

image.png

class Solution {
    public String minimumString(String a, String b, String c) {
        String res = null;
        StringBuilder sb = new StringBuilder();
        // 6种情况
        String s1 = minimumString(minimumString(a, b), c);
        String s2 = minimumString(minimumString(a, c), b);        
        String s3 = minimumString(minimumString(b, a), c);
        String s4 = minimumString(minimumString(b, c), a);
        String s5 = minimumString(minimumString(c, a), b);
        String s6 = minimumString(minimumString(c, b), a);
        return compare(compare(compare(s1, s2), compare(s3, s4)), compare(s5, s6));
    }
    public String minimumString(String a, String b){
        // a中包含b,return a
        if (a.indexOf(b) != -1){
            return a;
        }
        // 否则找到最长公共前后缀:a后缀 b前缀
        int n1 = a.length(), n2 = b.length();
        int maxIndex = 0, maxLen = 0; 
        for (int i = 0; i < n1; i++){
            if (n1 - i > n2) continue;
            if (a.substring(i, n1).equals(b.substring(0, n1 - i))){
                maxLen = n1 - i;
                break;
            }
        }
        return a + b.substring(maxLen, n2);
    }
    public String compare(String s1, String s2){
        if (s1.length() == s2.length()){
            if (s1.compareTo(s2) <= 0){
                return s1;
            }else{
                return s2;
            }
        }else if (s1.length() < s2.length()){
            return s1;
        }
        return s2;
    }
}

image.png

统计范围内的步进数字数目【LC2801】

给你两个正整数 lowhigh ,都用字符串表示,请你统计闭区间 [low, high] 内的 步进数字 数目。

如果一个整数相邻数位之间差的绝对值都 恰好1 ,那么这个数字被称为 步进数字

请你返回一个整数,表示闭区间 [low, high] 之间步进数字的数目。

由于答案可能很大,请你将它对 109 + 7取余 后返回。

**注意:**步进数字不能有前导 0 。

image.png

class Solution {
    public static final int MOD = (int)(1e9 + 7);
    public int countSteppingNumbers(String low, String high) {
        int[][] dp1 = new int[low.length()][10];
        int[][] dp2 = new int[high.length()][10];
        int flag = 1;
        for (int i = 0; i < low.length() - 1; i++){
            if (Math.abs(low.charAt(i) - low.charAt(i + 1)) != 1){
                flag = 0;
                break;
            }
        }
        for (int i = 0; i < low.length(); i++){
            Arrays.fill(dp1[i], -1);
        }
        for (int i = 0; i < high.length(); i++){
            Arrays.fill(dp2[i], -1);
        }
        return (f(high, dp2, 0, -1, false, true) - f(low, dp1, 0, -1, false, true) + flag + MOD) % MOD;
    }
    // 小于等于s的数目
    public int f(String s, int[][] dp, int i, int pre, boolean isNum, boolean isLimit){
        if (i == s.length()) return 1;
        if (isNum && !isLimit && dp[i][pre] >= 0) return dp[i][pre];
        int res = 0;
        int up = isLimit ? s.charAt(i) - '0' : 9;
        int down = isNum ? 0 : 1;
        if (!isNum){
            res = (res + f(s, dp, i + 1, -1, false, false)) % MOD;
            for (int d = down; d <= up; d++){
                res = (res + f(s,dp, i + 1, d, true, isLimit && d == s.charAt(i) - '0')) % MOD;
            }
        }else{
            if (pre - 1 >= down && pre - 1 <= up){
                res = (res + f(s,dp, i + 1, pre - 1, true, isLimit && pre - 1 == s.charAt(i) - '0')) % MOD;
            }
            if (pre + 1 >= down && pre + 1 <= up){
                res = (res + f(s,dp, i + 1, pre + 1, true, isLimit && pre + 1 == s.charAt(i) - '0')) % MOD;
            }
        }
        if (isNum && !isLimit){
            dp[i][pre] = res;
        }
        return res;
    }
}

image.png

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    public int countSteppingNumbers(String low, String high) {
        return (calc(high) - calc(low) + MOD + (valid(low) ? 1 : 0)) % MOD; // +MOD 防止算出负数
    }
    private char s[];
    private int memo[][];
    private int calc(String s) {
        this.s = s.toCharArray();
        int m = s.length();
        memo = new int[m][10];
        for (int i = 0; i < m; i++)
            Arrays.fill(memo[i], -1); // -1 表示没有计算过
        return f(0, 0, true, false);
    }
    private int f(int i, int pre, boolean isLimit, boolean isNum) {
        if (i == s.length)
            return isNum ? 1 : 0; // isNum 为 true 表示得到了一个合法数字
        if (!isLimit && isNum && memo[i][pre] != -1)
            return memo[i][pre];
        int res = 0;
        if (!isNum) // 可以跳过当前数位
            res = f(i + 1, pre, false, false);
        int up = isLimit ? s[i] - '0' : 9; // 如果前面填的数字都和 s 的一样,那么这一位至多填数字 s[i](否则就超过 s 啦)
        for (int d = isNum ? 0 : 1; d <= up; d++) // 枚举要填入的数字 d
            if (!isNum || Math.abs(d - pre) == 1) // 第一位数字随便填,其余必须相差 1
                res = (res + f(i + 1, d, isLimit && d == up, true)) % MOD;
        if (!isLimit && isNum)
            memo[i][pre] = res;
        return res;
    }
    private boolean valid(String s) {
        for (int i = 1; i < s.length(); i++)
            if (Math.abs((int) s.charAt(i) - (int) s.charAt(i - 1)) != 1)
                return false;
        return true;
    }
}
作者:灵茶山艾府
链接:https://leetcode.cn/problems/count-stepping-numbers-in-range/solutions/2364624/shu-wei-dp-tong-yong-mo-ban-by-endlessch-h8fj/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


目录
相关文章
|
7月前
【周赛总结】周赛354
【周赛总结】周赛354
49 0
|
7月前
9-周赛335总结
9-周赛335总结
53 0
|
7月前
14-周赛348总结
14-周赛348总结
54 0
|
7月前
|
存储
10-周赛336总结
10-周赛336总结
61 0
|
7月前
13-周赛347总结
13-周赛347总结
55 0
|
7月前
|
人工智能 BI
12-周赛338总结
12-周赛338总结
52 0
|
7月前
|
算法 Windows
【周赛总结】周赛360
【周赛总结】周赛360
51 0
|
7月前
【周赛总结】18-周赛353
【周赛总结】18-周赛353
61 0
|
7月前
|
算法
8-周赛334总结
8-周赛334总结
51 0
|
7月前
|
机器学习/深度学习 索引
11-周赛337总结
11-周赛337总结
57 0