周赛351

2748. 美丽下标对的数目

暴力枚举：

外层循环枚举下标 $i$ 遍历 $nums$，内层循环从 $i+1$ 遍历到数组末尾，满足条件结果 $+1$ 即可。

func countBeautifulPairs(nums []int) int {
    var res int
    for i, x := range nums {
        for x >= 10 {
            x /= 10
        }
        for j := i + 1; j < len(nums); j++ {
            y := nums[j] % 10
            if gcd(x, y) == 1 {
                res++
            }
        }
    }
    return res
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

非暴力枚举：

根据题意对于数字的最高位取值范围在 $[1,9]$ 中，所以可以改造下上述暴力解法，再内部循环时，只遍历 $[1,9]$ 即可。

设 $x = nums[i]$，遍历 $nums$，同时维护 $x$ 的最高位的出现次数 $cnt$。

枚举 $[1,9]$ 内的数字 $y$，如果最高位 $y$ 出现过且与 $x \% 10$ 互质则答案加上 $cnt[y]$

func countBeautifulPairs(nums []int) int {
    cnt := [10]int{}
    res := 0
    for _, x := range nums {
        for y := 1; y < 10; y++ {
            if cnt[y] > 0 && gcd(x%10, y) == 1 { // 这里y 表示最高位,出现过最高位,且与最低位互质
                res += cnt[y]
            }
        }
        for x >= 10 {
            x /= 10
        }
        cnt[x] ++ // 统计最高位的出现次数
    }
    return res
}

2749. 得到整数零需要执行的最少操作数

枚举：

假设操作了 $k$ 次，那么操作后 $num_1$ 变成 $num_1 - num_2 \times k - k \times 2^i = 0$

此时问题变成：$num_1 - num_2 \times k$ 能否拆分成 $k$ 个 $2^i$ 之和？

设 $x = num_1 - num_2 \times k$，可以看出至少需要 bits.OnesCount(x) 个 $2^i$ 磁能凑成 $x$ （bits.OnesCount 表示 $x$ 二进制中 $1$ 的个数）；同时，最多只能用 $x$ 个 $2^0 =1$ 凑出 $x$，也就是说，只要 $k$ 满足 $bits.OnesCount(x) \leq k \leq x$ 就是一个合法的 $k$。

因为每个 $2^i$ 都可以拆分为两个 $2^{i-1}$，所以 bits.OnesCount(x) 到 $x$ 之间的所有值都是符合要求的。

从小到大遍历，获取到第一个合法的 $k$ 即可返回答案。

func makeTheIntegerZero(num1 int, num2 int) int {
    for k := 1; k <= num1-num2*k; k++ {
        if k >= bits.OnesCount(uint(num1-num2*k)) {
            return k
        }
    }
    return -1
}

2750. 将数组划分成若干好子数组的方式

乘法：

根据题意，需要在每两个 $1$ 之前画分割线，两个 $1$ 之间有 $x$ 个 $0$ 就可以画 $x+1$ 条分割线。根据乘法原理，答案为所有分割线的方案数的乘积。

假设原数组为 $nums = [1,0,0,1,0,1]$，按照 $1$ 分为两个部分，$nums_1 = [1,0,0,1]$ 和 $nums_2 = [1,0,1]$。其中 $nums_1$ 可以画 $3$ 条分割线，$nums_2$ 可以画 $2$ 条分割线，所以答案为 $2 \times 3 = 6$。

特别地，如果数组中没有 $1$，那么答案为 $0$，如果数组中只有一个 $1$，那么答案为 $1$。

func numberOfGoodSubarraySplits(nums []int) int {
    const mod = 1e9 + 7
    res, pre := 1, -1
    for i, num := range nums {
        if num > 0 {
            if pre >= 0 {
                res = res * (i - pre) % mod
            }
            pre = i
        }
    }
    if pre < 0 {
        return 0
    }
    return res
}

2751. 机器人碰撞

栈：

用数组 $toLeft$ 维护向左的机器人，用栈 $st$ 维护向右的机器人。

按照 $positions[i]$ 从小到大排序。遍历机器人，如果遇到向右的机器人，直接加入栈 $st$，如果遇到一个向左的机器人 $p$，分类讨论：

• 如果 $p$ 的健康度小于栈顶，那么栈顶机器人健康度减一。
• 如果 $p$ 的健康度等于栈顶，那么移除栈顶。
• 如果 $p$ 的健康度大于栈顶，那么移除栈顶，将 $p$ 的健康度减一，再去与下一个栈顶比较
• 如果栈为空，$p$ 加入$toLeft$

最后剩余的 $toLeft$ 与 $st$ 合并，按照编号排序后，返回健康度列表。

func survivedRobotsHealths(positions []int, healths []int, directions string) []int {
    type data struct {
        i, p, h int
        d       byte
    }
    
    arr := make([]data, len(positions))
    for i, position := range positions {
        arr[i] = data{i, position, healths[i], directions[i]}
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i].p < arr[j].p
    })
    
    var toLeft, st []data
    for _, p := range arr {
        if p.d == 'R' {
            st = append(st, p)
            continue
        }
        
        for len(st) > 0 {
            top := &st[len(st)-1]
            if top.h > p.h { // 栈顶的健康度更大
                top.h--
                break
            }
            if top.h == p.h { // 健康度一样大
                st = st[:len(st)-1]
                p.h = -1 // 防止加入 toLeft
                break
            }
            p.h-- // p的健康度更大
            st = st[:len(st)-1]
        }
        if len(st) == 0 && p.h != -1{
            toLeft = append(toLeft, p) // p把栈中全部撞掉
        }
    }
    
    toLeft = append(toLeft, st...)
    sort.Slice(toLeft, func(i, j int) bool {
        return toLeft[i].i < toLeft[j].i
    })
    res := make([]int, len(toLeft))
    for i, d := range toLeft {
        res[i] = d.h
    }
    return res
}