面试题 08.08. 有重复字符串的排列组合

面试题 08.08. 有重复字符串的排列组合
回溯法

class Solution:
    def permutation(self, S: str) -> List[str]:
        res = set()
        self.recursion(S, '', res)
        return list(res)

    def recursion(self, candidate_char: str, s: str, res: set):
        if not candidate_char:
            res.add(s)
        used = set()
        for i in range(len(candidate_char)):
            if candidate_char[i] not in used:
                self.recursion(candidate_char[:i] + candidate_char[i + 1:], s + candidate_char[i], res)
                used.add(candidate_char[i])

40. 组合总和 II

40. 组合总和 II
回溯法

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        self.recursion(candidates, [], 0, target, ans)
        return ans

    def recursion(self, candidates, path, now_value, target, ans):
        if now_value > target:
            return
        if now_value == target:
            ans.append(path[:])
        used = set()
        for i in range(len(candidates)):
            if candidates[i] not in used:
                now_value += candidates[i]
                path.append(candidates[i])
                self.recursion(candidates[i + 1:], path, now_value, target, ans)
                path.pop()
                now_value -= candidates[i]
                used.add(candidates[i])

LCR 039. 柱状图中最大的矩形

LCR 039. 柱状图中最大的矩形

【花落&月缺】我真的真的努力想说明白这个题的解法了(╬◣д◢)

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [(-1, -1)]
        result = 0
        index = 0
        for index, height in enumerate(heights):
            while height < stack[-1][0]:
                result = max(result, (index - stack[-2][1] - 1) * (stack[-1][0]))
                stack.pop()
            stack.append((height, index))
        while stack[-1][0] != -1:
            result = max(result, (index + 1 - stack[-2][1] - 1) * (stack[-1][0]))
            stack.pop()
        return result

2772. 使数组中的所有元素都等于零

2772. 使数组中的所有元素都等于零

差分数组+贪心算法

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        d = [0] * (len(nums) + 1)
        sum_d = 0
        for i in range(len(nums)):
            sum_d += d[i]
            x = nums[i] + sum_d
            if x == 0:
                continue
            if x < 0 or i + k > len(nums):
                return False
            sum_d -= x
            d[i + k] += x
        return True

2849. 判断能否在给定时间到达单元格

2849. 判断能否在给定时间到达单元格

class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
        diagonal = min(abs(sy - fy), abs(sx - fx))
        line = max(abs(sy - fy), abs(sx - fx)) - diagonal
        if diagonal + line > t:
            return False
        if sx == fx and sy == fy and t == 1:
            return False
        return True

LCR 022. 环形链表 II

LCR 022. 环形链表 II

快慢指针

class Solution:
    def detectCycle(self, head: ListNode):
        if not head:
            return None
        fast = head
        slow = head
        while True:
            if fast.next is None or fast.next.next is None:
                return None
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast