周赛356 | 顾澜的技术小站

2798. 满足目标工作时长的员工数目

啊？怎么会有这么简单的题

func numberOfEmployeesWhoMetTarget(hours []int, target int) (res int) {
    for _, hour := range hours {
        if hour >= target {
            res++
        }
    }
    return
}

2799. 统计完全子数组的数目

暴力：

两次循环，判断每个子数组是否满足要求

func countCompleteSubarrays(nums []int) (res int) {
    set := make(map[int]struct{})
    for _, num := range nums {
        set[num] = struct{}{}
    }
    l := len(set)
    
    for i := 0; i < len(nums); i++ {
        cnt := make(map[int]int)
        for _, x := range nums[i:] {
            cnt[x]++
            if len(cnt) == l {
                res++
            }
        }
    }
    return res
}

滑动窗口：

找到符合条件的滑动窗口 $[left,right]$ ，此时 $right$ 右侧有 $k$ 个元素，那就有 $k+1(滑动窗口本身)$ 个滑动窗口满足条件

因为 $k=len(nums)-right-1$ ，此时就有 $len(nums)-right$ 个满足条件的滑动窗口

移动 $left$ 累加满足条件的滑动窗口个数，直到 $[left,right]$ 不满足条件

继续移动 $right$ ，找到下一个满足条件的 $[left,right]$

func countCompleteSubarrays(nums []int) int {
    set := make(map[int]struct{})
    for _, num := range nums {
        set[num] = struct{}{}
    }
    l := len(set)
    
    cnt := make(map[int]int)
    left := 0
    res := 0
    for _, num := range nums {
        cnt[num]++
        for len(cnt) == l { // 满足条件,左端点向右移动
            x := nums[left]
            cnt[x]--
            if cnt[x] == 0 {
                delete(cnt, x)
            }
            left++
        }
        res += left
    }
    return res
}

2800. 包含三个字符串的最短字符串

枚举：

枚举 $a,b,c$ 的全排列 $a',b',c'$ ，合并 $a',b'$ 得到最短字符串 $x$ ，再合并 $x,c'$ 得到最短字符 s。

合并 $a',b'$ 时，在没有完全包含的情况下，相当于在 $b'$ 的左右两边分别添加一些字母，得到最短字符串 $s$ 。

取最短且字典序最小的 $s$ 作为答案。


func merge(s, t string) string {
    // 先特判完全包含的情况
    if strings.Contains(s, t) {
        return s
    }
    if strings.Contains(t, s) {
        return t
    }
    for i := min(len(s), len(t)); ; i-- {
        // 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的
        x := s[len(s)-i:]
        y := t[:i]
        if x == y {
            return s + t[i:]
        }
    }
}

func minimumString(a string, b string, c string) (res string) {
    strList := []string{a, b, c}
    
    arr := [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}}
    for _, a := range arr {
        s := merge(merge(strList[a[0]], strList[a[1]]), strList[a[2]])
        if res == "" || len(s) < len(res) || len(s) == len(res) && s < res {
            res = s
        }
    }
    return
}

KMP:

合并字段是使用KMP的思路进行合并：

设 $p = t+"\#"+ s$ ，求出 $p$ 的公共子串
$s$ 加上 $t$ 去掉公共子串就是最短字符串

func mearge2(s, t string) string {
    if strings.Contains(s, t) {
        return s
    }
    if strings.Contains(t, s) {
        return t
    }
    
    p := t + "#" + s
    n := len(p)
    next := make([]int, n) // 通过next计算子串
    for i := 1; i < n; i++ {
        j := next[i-1]
        for j > 0 && p[i] != p[j] {
            j = next[j-1]
        }
        if p[i] == p[j] {
            j++
        }
        next[i] = j
    }
    
    // s+t去掉公共子串
    return s + t[next[n-1]:]
}

2801. 统计范围内的步进数字数目

解题思路:

抄一下灵神的思路：原文见数位 DP 通用模板

定义 $calc(n)$ 表示不超过 $n$ 的步进数字数目。那么答案就是

$cacl(hight)-cacl(low-1)$

$=calc(hight)-cacl(low)+valid(low)$

由于 $low$ 是个很大的数字，不方便减一，所以用 $valid(low)$ 表示：如果 $low$ 是步进数字，那么多减了 $1$ ，再加 $1$ 补回来。

如何计算 $calc(n)$ 呢？（下文用 $s$ 表示 $n$ 的字符串形式）

一种通用套路是，定义 $f(i, pre, isLimit, isNum)$ 表示构造第 $i$ 位及其以后数位的合法方案数，其中参数的含义为：

$pre$ 表示上一个数位的值，如果 $isNum$ 为 false，就可以忽略 $pre$ 。
$isLimit$ 表示当前是否收到了 $n$ 的约束（注意要构造的数字不能超过 $n$ ）。若为真，则第 $i$ 位填入的数字最大为 $s[i]$ ，否则可是 $9$ 。如果收到约束的情况下填了 $s[i]$ ，那么后续填入的数字仍会受到约束。例如 $n=123$ ，那么 $i=0$ 填入的是 $1$ 的话， $i=1$ 的这一位最大填 $2$ 。
$isNum$ 表示 $i$ 前面的数位是否填入了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 $1$ ；若为真，则要填入的数字可以从 $0$ 开始。例如 $n=123$ ，在 $i=0$ 时跳过的话，相当于后面要构造的数字是一个 $99$ 以内的数字了，如果 $i=1$ 不跳过，那么相当于构造了一个 $10~99$ 的两位数，如果 $i=1$ 也跳过，相当于构造的事一个 $9$ 以内的数字。

实现细节：

递归入口：f(0, 0, true, false)，表示：

从 $s[0]$ 开始枚举
$pre$ 初始成什么都可以，因为填入第一个数的时候是忽略 $pre$ 的
一开始要收到 $n$ 的约束（否则就可以随便填了，比如 $n=2$ ，但你填个 $9$ ）
一开始没有填数字

递归中：

如果 $isNum$ 为假，说明前面没有填数字，那么当前可以不填数字。一旦从这里递归下去， $isLimit$ 就可以置为 false 了，这是因为 $s[0]$ 必然是大于 $0$ 的，后面就不受到 $n$ 的约束了。或者说，最高位不填数字，后面无论怎么填都比 $n$ 小。
如果 $isNum$ 为真，那么那么当前必须填一个数字。枚举填入的数字，根据 $isNum$ 和 $isLimit$ 来决定填入数字的范围。

递归终点：当 $i == len(s)$ 时，如果 $isNum$ 为真，则表示得到了一个合法数字（因为不合法的不会继续递归下去），返回 $1$ ，否则返回 $0$ 。

const mod int = 1e9 + 7
func countSteppingNumbers(low string, high string) int {
    res := (calc(high) - calc(low) + mod) % mod
    if valid(low) {
        res = (res + 1) % mod
    }
    return res
}

func calc(s string) int {
    memo := make([][10]int, len(s))
    for i := range memo {
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    
    // pre 表示上一个数位的值, isNumber为false,可以忽略
    // isLimit 表示当前是否收到了前n位的约束
    // isNumber 表示i前面的数值是否填充了数字
    var dfs func(i, pre int, isLimit, isNumber bool) int
    dfs = func(i, pre int, isLimit, isNumber bool) (res int) {
        if i == len(s) { // 递归结束
            if isNumber {
                return 1
            }
            return 0 // 前面最后一位没填充数字,非法
        }
        
        // var res int
        if !isLimit && isNumber {
            p := &memo[i][pre]
            if *p >= 0 {
                return *p
            }
            defer func() { *p = res }()
        }
        
        if !isNumber { // 可以跳过当前数位
            res += dfs(i+1, pre, false, false)
        }
        
        d := 0
        if !isNumber {
            d = 1 // 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
        }
        up := 9
        if isLimit {
            up = int(s[i] - '0') // 如果前面填的数字都和 s 的一样，那么这一位至多填数字 s[i]（否则就超过 s 啦）
        }
        for ; d <= up; d++ {
            if !isNumber || abs(d, pre) == 1 { // 第一位数字随便填，其余必须相差 1
                res += dfs(i+1, d, isLimit && d == up, true)
            }
        }
        return res % mod
    }
    return dfs(0, 0, true, false)
}

// 如果 low 是步进数字,那么多减了1,再加一不回来
func valid(s string) bool {
    for i := 1; i < len(s); i++ {
        if abs(int(s[i-1]), int(s[i])) != 1 {
            return false
        }
    }
    return true
}

func abs(a, b int) int {
    if a > b {
        return a - b
    }
    return b - a
}