1323. 6 和 9 组成的最大数字

1323. 6 和 9 组成的最大数字

class Solution:
    def maximum69Number(self, num: int) -> int:
        num = list(str(num))
        for i in range(len(num)):
            if num[i] == '6':
                num[i] = '9'
                break
        return int(''.join(num))

168. Excel表列名称

168. Excel表列名称

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        if columnNumber == 0:
            return 'A'  # 'A' represents 0 in base-26
        result = ''
        while columnNumber > 0:
            columnNumber -= 1  # Adjust for 0-based indexing
            remainder = columnNumber % 26
            result = chr(ord('A') + remainder) + result
            columnNumber //= 26
        return result

1442. 形成两个异或相等数组的三元组数目

1442. 形成两个异或相等数组的三元组数目

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        cache = {}
        i_k = []
        for i in range(len(arr)):
            xor = 0
            for j in range(i, len(arr)):
                xor ^= arr[j]
                cache[(i, j)] = xor
                if xor == 0 and i != j:
                    i_k.append((i, j))
        ans = 0
        for i in range(len(i_k)):
            for j in range(i_k[i][0] + 1, i_k[i][1] + 1):
                if cache[(i_k[i][0], j - 1)] == cache[(j, i_k[i][1])]:
                    ans += 1
                    # print((i_k[i][0], j, i_k[i][1]))
        return ans

2615. 等值距离和

2615. 等值距离和

from typing import List, Dict
from collections import defaultdict


class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        d: Dict[int, list] = defaultdict(list)
        for i in range(len(nums)):
            d[nums[i]].append(i)
        for k, v in d.items():
            if len(v) == 1:
                nums[v[0]] = 0
                continue
            pre_sum = 0
            aft_sum = sum(v)
            for i in range(len(v)):
                aft_sum -= v[i]
                nums[v[i]] = abs(pre_sum - v[i] * i) + abs(aft_sum - v[i] * (len(v) - i - 1))
                pre_sum += v[i]
        return nums

2544. 交替数字和

2544. 交替数字和

class Solution:
    def alternateDigitSum(self, n: int) -> int:
        n = str(n)
        ans = 0
        for i in range(len(n)):
            ans += int(n[i]) if i % 2 == 0 else -int(n[i])
        return ans

2344. 使数组可以被整除的最少删除次数

2344. 使数组可以被整除的最少删除次数

from typing import List
import heapq


class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        heapq.heapify(nums)
        gcd_max = numsDivide[0]
        for i in range(1, len(numsDivide)):
            gcd_max = self.gcd(gcd_max, numsDivide[i])
        ans = -1
        while nums:
            ans += 1
            x = heapq.heappop(nums)
            if gcd_max % x == 0:
                break
        else:
            return -1
        return ans

    def gcd(self, a, b):
        while b != 0:
            a, b = b, a % b
        return a

面试题 17.22. 单词转换

面试题 17.22. 单词转换

from typing import List


class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[str]:
        wordList.append(beginWord)
        graph = [[] for i in range(len(wordList))]
        end_index = None
        for i in range(len(wordList)):
            if wordList[i] == endWord:
                end_index = i
            for j in range(i + 1, len(wordList)):
                if self.diff(wordList[i], wordList[j]):
                    graph[i].append(j)
                    graph[j].append(i)
        if end_index is None:
            return []
        used = set()
        path = self.dfs(graph, len(graph) - 1, end_index, [len(graph) - 1], used)
        if not path:
            return []
        return [wordList[path[i]] for i in range(len(path))]


    def dfs(self, graph, start, end, path, used):
        if start == end:
            return path
        used.add(start)
        for i in range(len(graph[start])):
            if graph[start][i] in used:
                continue
            path.append(graph[start][i])
            res = self.dfs(graph, graph[start][i], end, path, used)
            if res:
                return res
            path.pop()

    def diff(self, a, b):
        count = 0
        for i in range(len(a)):
            if a[i] != b[i]:
                count += 1
            if count >= 2:
                return False
        return True if count == 1 else False