Skip to main content

周赛 Weekly Contest 398

https://leetcode.cn/contest/weekly-contest-398/

100310. Special Array I​

class Solution:
    def isArraySpecial(self, nums: List[int]) -> bool:
        for i in range(len(nums)-1):
            if nums[i] % 2 == nums[i+1] %2:
                return False
        return True

100308. Special Array II​

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        res = [True] * len(queries)
        @cache
        def dfs(i, j):
            if i == j:
                return True
            if i + 1 == j:
                return nums[i] % 2 != nums[i+1] % 2
            if j - i < 3:
                for k in range(i, j, 1):
                    if nums[k] % 2 == nums[k+1] % 2:
                        return False
                return True
            mid = (i+j) // 2
            return dfs(i, mid) and dfs(mid, j)
        dfs(0, len(nums)-1)
        for i in range(len(queries)):
            q = queries[i]
            res[i] = dfs(q[0], q[1])
            # for j in range(q[0], q[1], 1):
            #     if nums[j] % 2 == nums[j+1] %2:
            #         res[i] = False
        return res

100300. Sum of Digit Differences of All Pairs​

class Solution:
    def sumDigitDifferences(self, nums):
        res = 0
        # bit = (nums // carry) % 10
        max_n = max(nums)
        max_bit = 0
        while max_n != 0:
            max_bit +=1
            max_n //= 10

        # dp = [0 for _ in range(len(nums))]
        for i in range(max_bit):
            carry = 10 ** i
            cache = [[0, -1] for _ in range(10)]
            for j in range(len(nums)):
                jbit = (nums[j] // carry) % 10
                start = 0
                curDiff = 0
                if cache[jbit][1] != -1:
                    start, diff = cache[jbit]
                    curDiff += diff
                for k in range(start, j, 1):
                    if j == k: 
                        continue
                    kbit = (nums[k] // carry) % 10
                    curDiff += 1 if jbit != kbit else 0
                cache[jbit] = [j, curDiff]
                res += curDiff
        return res

100298. Find Number of Ways to Reach the K-th Stair​

https://leetcode.cn/problems/find-number-of-ways-to-reach-the-k-th-stair/solutions/2782792/liang-chong-fang-fa-ji-yi-hua-sou-suo-zu-j227/

my approach

class Solution:
    def waysToReachStair(self, k: int) -> int:
        def dfs(num, canBack):
            if num == 0 and !canBack : return 0
            if num == 1 and !canBack: return 1
            res = 0
            if canBack:
                res += dfs(num+1, False)
            bit = 0
            while 2 ** bit < num:
                if num - 2 ** bit == 1:
                    res += 1
                    res += dfs(num - 2 ** bit, True)
                bit += 1
            return res
        return dfs(k, True)

0x3F

class Solution:
    def waysToReachStair(self, k: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, pre_down: bool) -> int:
            if i > k + 1:
                return 0
            res = 1 if i == k else 0
            res += dfs(i + (1 << j), j + 1, False)  # 操作二
            if i and not pre_down:
                res += dfs(i - 1, j, True)  # 操作一
            return res
        return dfs(1, 0, False)