893. 特殊等价字符串组

893. 特殊等价字符串组

class Solution:
    def numSpecialEquivGroups(self, words: List[str]) -> int:
        for i in range(len(words)):
            words[i] = [
                sorted([words[i][j] for j in range(0, len(words[i]), 2)]),
                sorted([words[i][j] for j in range(1, len(words[i]), 2)]),
            ]
            words[i][0] = ''.join(words[i][0])
            words[i][1] = ''.join(words[i][1])
            words[i] = ''.join(words[i])
        return len(set(words))

面试题 17.11. 单词距离

面试题 17.11. 单词距离

class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        p0 = -1
        ans = float('inf')
        last_find = None  # 1: word1 2: word2
        for p1 in range(len(words)):
            if words[p1] == word1:
                if p0 < 0 or last_find == 1:
                    pass
                elif p1 - p0 < ans:
                    ans = p1 - p0
                last_find = 1
                p0 = p1
            elif words[p1] == word2:
                if p0 < 0 or last_find == 2:
                    pass
                elif p1 - p0 < ans:
                    ans = p1 - p0
                last_find = 2
                p0 = p1
        return ans

337. 打家劫舍 III

337. 打家劫舍 III
动态规划

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from typing import Optional


class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        return max(
            self.max(root, include=True),
            self.max(root, include=False)
        )

    def max(self, node, include):
        if node is None:
            return 0
        if hasattr(node, "include_self_max") and include:
            return node.include_self_max
        if hasattr(node, "not_include_self_max") and not include:
            return node.not_include_self_max
        node.include_self_max = node.val + self.max(node.left, include=False) + self.max(node.right, include=False)
        node.not_include_self_max = max(
            self.max(node.left, include=True),
            self.max(node.left, include=False)
        ) + max(
            self.max(node.right, include=True),
            self.max(node.right, include=False),
        )
        if include:
            return node.include_self_max
        else:
            return node.not_include_self_max