LeetCode冲刺：Day30

发布于 2022-12-07 1069 次阅读

今天摸了，忏悔。

1. 字符串中最大的 3 位相同数字

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

简单模拟。

代码

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        n = len(num)
        ans = ""
        for i in range(2, n):
            if num[i] == num[i - 1] and num[i] == num[i - 2]:
                if num[i - 2:i + 1] > ans: ans = num[i - 2:i + 1]
        return ans

2. 统计值等于子树平均值的节点数

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

看到树相关题应该先想用什么顺序遍历。判断当前结点是否满足条件时，需要用到孩子的值和计数，显然应当用后序遍历。没太弄明白python中怎么把整数传引用给函数，所以用数组代替下。

另外要注意python中除法的出的是浮点数，要手动转成int。

代码

class Solution:
    def postOrder(self, root: TreeNode, ans: List[int]) -> List:
        if (root == None): return [0, 0]
        left = self.postOrder(root.left, ans)
        right = self.postOrder(root.right, ans)
        totalVal = root.val + left[0] + right[0]
        totalCnt = 1 + left[1] + right[1]
        if int(totalVal / totalCnt) == root.val: ans[0] += 1
        return [totalVal, totalCnt]

    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
        ans = [0]
        self.postOrder(root, ans)
        return ans[0]

3. 统计打字方案数

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

空间和时间都还有能优化的地方，但能独立做出来已经很不错了！

首先很明显的一点是，每段连续相同数字所构成的种数的累乘，就是整段数字串能组成的字符串种数。

那么从最简单的情况开始，即数字串中只有一种数字。观察对于当前数字串，每多一个相同数字，无非几种选择，一是单独按一次，那么能构成的种数是前一位的种数；与前一位一起按，那么能构成的种数是前前一位的种数……以此类推，但要注意的是，能够一起按的数量跟当前数字对应的字母数有关，比如2最多可以跟前两个按键一起按。所以很明显可以用DP做。

另外，为了方便计算，DP数组应该在起始位置多出一位，值为1。这也是说得通的，因为第一个数字只能单独按，它可以构成一种。

有了以上思路，我们只要把整个数字串分为多个相同连续数字组成的子串，然后分别求得其种数，再累乘即可。

应该是有直接连续遍历，而不用分割字符串的算法，但我暂时想不出来。

另一个优化思路是，因为连续相同数字子串能构成的种数只与其长度和数字对应的字母种数有关，而长度和对应字母种数都是有上限的，我们可以针对字母种数3和4分别构造一个长度为10的5次方加1的DP数组，表示可以构成的种数。然后遍历一遍数字串，在一段连续相同数字子串结束时直接累乘对应种数即可。

代码

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        nums = [0, 0, 3, 3, 3, 3, 3, 4, 3, 4]
        n = len(pressedKeys)
        ans = 1
        MOD = 1000000007
        start = 0
        keys = []
        for i in range(n + 1):
            if i == n or pressedKeys[i] != pressedKeys[start]:
                keys.append(pressedKeys[start:i])
                start = i
        for key in keys:
            m = len(key)
            dp = [0] * (m + 1)
            dp[0] = dp[1] = 1
            for i in range(2, m + 1):
                j = i - 1
                while j >= 0 and i - j <= nums[int(key[0])]:
                    dp[i] = (dp[i] + dp[j]) % MOD
                    j -= 1
            ans = (ans * dp[m]) % MOD
        return ans