周赛 Weekly Contest 412

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

3264. Final Array State After K Multiplication Operations I

pass

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        for i in range(k):
            cm = min(nums)
            for j in range(len(nums)):
                if nums[j] == cm:
                    nums[j] = nums[j] * multiplier
                    break
        return nums

3265. Count Almost Equal Pairs I

pass

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        @cache
        def getAllCases(n):
            ns = list(str(n))
            res = {}
            res[int("".join(ns))] = True
            for i in range(len(ns)-1):
                for j in range(1, len(ns), 1):
                    ns[i], ns[j] = ns[j], ns[i]
                    curN = int("".join(ns))
                    if curN not in res:
                        res[curN] = True
                    # print(i, ns, res)
                    ns[i], ns[j] = ns[j], ns[i]
            return res

        allCases = []
        for i in range(0, len(nums), 1):
            allCases.append(getAllCases(nums[i]))
        # print(allCases)

        def checkSame(i, j):
            nonlocal allCases
            if nums[i] in allCases[j]:
                return True
            elif nums[j] in allCases[i]:
                return True
            return False

        # print(allCases)
        ans = 0
        for i in range(len(allCases)-1):
            for j in range(i+1, len(allCases), 1):
                # print(allCases[i], allCases[j])
                if checkSame(i, j):
                    ans += 1
        return ans
        

3266. Final Array State After K Multiplication Operations II

WA

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        mod = 10**9 + 7
        h = [(val, idx) for idx, val in enumerate(nums)]
        heapq.heapify(h)
        for i in range(k):
            mv, idx = heapq.heappop(h)
            nums[idx] = mv * multiplier
            heapq.heappush(h, (nums[idx], idx))
        nums = [num % mod for num in nums]
        return nums

3267. Count Almost Equal Pairs II

Pass

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        @cache
        def getAllCases(n):
            ns = list(str(n))
            res = {}
            res[int("".join(ns))] = True
            for i in range(len(ns)-1):
                for j in range(1, len(ns), 1):
                    ns[i], ns[j] = ns[j], ns[i]
                    curN = int("".join(ns))
                    if curN not in res:
                        res[curN] = True
                    ns[i], ns[j] = ns[j], ns[i]
            return res

        times = {}
        allCases = {}
        for i in range(0, len(nums), 1):
            cN = nums[i]
            if cN not in allCases:
                cAll = {}
                fAll = getAllCases(cN)
                for fk in fAll:
                    cAll[fk] = True
                    sAll = getAllCases(fk)
                    for sk in sAll:
                        if sk not in fAll:
                            cAll[sk] = True
                allCases[cN] = cAll
            if cN not in times:
                times[cN] = 1
            else:
                times[cN] += 1
        # print(allCases)

        # @cache
        # def checkSame(x, y):
        #     nonlocal allCases
        #     if x in allCases[y]:
        #         return True
        #     elif y in allCases[x]:
        #         return True
        #     return False

        ans = 0
        listAllNums = sorted(list(allCases))
        for i in range(len(listAllNums)):
            k1 = listAllNums[i]
            n = times[k1]
            ans += int(n*(n-1)/2)
            for j in range(i+1, len(listAllNums), 1):
                k2 = listAllNums[j]
                isSame = False
                if k1 in allCases[k2]:
                    isSame = True
                elif k2 in allCases[k1]:
                    isSame = True
                if isSame:
                    ans += times[k1] * times[k2]
        # for k1 in allCases:
        #     n = times[k1]
        #     ans += int(n*(n-1)/2)
        #     for k2 in allCases:
        #         if k1 == k2:
        #             continue
        #         else:
        #             isSame = False
        #             if k1 in allCases[k2]:
        #                 isSame = True
        #             elif k2 in allCases[k1]:
        #                 isSame = True
        #             if isSame:
        #                 ans += times[k1] * times[k2]
        #         print(k1, k2, ans)
                
        # for i in range(len(nums)-1):
        #     for j in range(i+1, len(nums), 1):
        #         # print(ans, i, j, nums[i], nums[j])
        #         x, y = nums[i], nums[j]
        #         if x in allCases[y]:
        #             ans += 1
        #         elif y in allCases[x]:
        #             ans += 1
        #         # if checkSame(nums[i], nums[j]):
        #             # ans += 1
        return ans