1653. 使字符串平衡的最少删除次数

1653. 使字符串平衡的最少删除次数

class Solution:
    def minimumDeletions(self, s: str) -> int:
        dp = [0 for i in range(len(s))]
        cnt_b = 0
        for i in range(len(s)):
            if s[i] == 'a':
                dp[i] = min(dp[i - 1] + 1, cnt_b)
            elif s[i] == 'b':
                dp[i] = dp[i - 1]
                cnt_b += 1
        return dp[-1]

2541. 使数组中所有元素相等的最小操作数 II

2541. 使数组中所有元素相等的最小操作数 II

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
        if sum(nums1) != sum(nums2):
            return -1
        if k == 0:
            if nums2 != nums1:
                return -1
            else:
                return 0
        rest = 0
        cnt = 0
        for i in range(len(nums1)):
            if (nums1[i] - nums2[i]) % k != 0:
                return -1
            need = (nums2[i] - nums1[i]) // k  # + 给 - 收
            if need == 0:
                continue
            if rest > 0 and need > 0:
                rest = rest - need
                cnt += abs(rest) if rest < 0 else 0
            elif rest < 0 and need < 0:
                rest = rest - need
                cnt += abs(rest) if rest > 0 else 0
            else:
                cnt += abs(need)
                rest = rest - need
        return cnt

1466. 重新规划路线

1466. 重新规划路线

class Solution:
    def __init__(self):
        self.cnt = 0

    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        tree = [[] for i in range(n)]
        for i in range(n - 1):
            tree[connections[i][0]].append((connections[i][1], 1))
            tree[connections[i][1]].append((connections[i][0], -1))
        self.dfs(tree, 0, set())
        return self.cnt

    def dfs(self, tree: List[List[Tuple[int, int]]], node_index, used: set):
        node = tree[node_index]
        used.add(node_index)
        for i in range(len(node)):
            if node[i][0] in used:
                continue
            if node[i][1] == 1:
                self.cnt += 1
            self.dfs(tree, node[i][0], used)

884. 两句话中的不常见单词

884. 两句话中的不常见单词

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        s = s1 + ' ' + s2
        s = s.split(' ')
        s_set = set()
        discard = set()
        for i in range(len(s)):
            if s[i] in discard:
                continue
            if s[i] in s_set:
                discard.add(s[i])
                s_set.discard(s[i])
            else:
                s_set.add(s[i])
        return list(s_set)