腾讯音乐20220926

第一题 01数列 AC

和之前百度的题目很像

给定一个01字符串s，你可以把相邻的两个字符变成“00”或“11”

求最少需要多少次变化可以使所有字符相等

s.length < 1000

solution

数据范围小，暴力求解

class Solution:
    def minOperations(self, s: str) -> int:
        def f(s, ch):
            cnt = 0
            for i in range(len(s) - 1):
                if s[i] != ch:
                    cnt += 1
                    s[i + 1] = ch
                    s[i] = ch
            return cnt if s[-1] == ch else cnt + 1

        return min(f(list(s), "0"), f(list(s), "1"))
print(Solution().minOperations("1001101"))

第二题 子数组 AC

给定一个正整数数组a，以及一个正整数x

要求满足 子数组乘积尾随0个数大于等于x 的子数组个数

结果可能很大，对1e9+7取模

a.length ≤ 100000

0 < x < a.length

solution

首先你要知道尾随0的个数只和 2和5有关

其实就是一个动态规划

class Solution:
    def getSubarrayNum(self, a: List[int], k: int) -> int:
        # 定义dp[i] 为以i结尾的满足题意的子数组数量
        # [5,2,3,50,4],2
        mod = 10 ** 9 + 7

        def get(x, base):
            res = 0
            while x % base == 0:
                res += 1
                x //= base
            return res

        n = len(a)
        dp = [0] * (n + 1)
        pre = [(0, 0)]
        left = 0
        for x in a:
            t1, t2 = pre[-1]
            pre.append((get(x, 2) + t1, get(x, 5) + t2))
        for i in range(1, n + 1):
            dp[i] += dp[i - 1]
            while min(pre[i][1] - pre[left][1], pre[i][0] - pre[left][0]) >= k:
                dp[i] += 1
                left += 1
        # print(dp)
        return sum(dp) % mod

print(Solution().getSubarrayNum([5, 2, 3, 50, 4], 2))

第三题 矩阵 15%

给定一个n x m 的二维矩阵，给定一个x，保证x为偶数

求矩阵中所有的数都在[1,x]之间且所有2 x 2子矩阵的和为偶数的矩阵构造方式

结果可能很大，对1e9+7取模

2 ≤ n, m, x ≤ 1e9

样例 n=m=x=2

有8种方法

全为1，1种放法

全为2，1种放法

两个1两个2，从4个位置选2个位置放1，有6种放法，剩余放2

1 + 1 + 6

solution

这个数据范围属实吓人

我推了很久还是不知道怎么做，等大佬吧

还有一个构造题，秒杀系统，不懂这方面直接跳过了

总结

寄