23.02.12 Today’s Leetcode

2477. Minimum Fuel Cost to Report to the Capital (medium)

사람 수를 이용하여 계산.

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        tree = defaultdict(list)
        for u, v in roads:
            tree[u].append(v)
            tree[v].append(u)
        
        n = len(roads) + 1
        visited = [False] * n
        people = [-1] * n
        fuel = 0

        def dfs(cur, prev):
            res = 1
            nonlocal fuel
            if people[cur] != -1:
                return people[cur]
            for node in tree[cur]:
                if node != prev: 
                    temp = dfs(node, cur)
                    res += temp
                    fuel += math.ceil(temp / seats)
            people[cur] = res
            return res

        dfs(0, -1)
        print(people)
        return fuel

387. First Unique Character in a String (easy)

class Solution:
    def firstUniqChar(self, s: str) -> int:
        temp = defaultdict(list)
        for i in range(len(s)):
            t = s[i]
            temp[t].append(i)
        
        for arr in temp.values():
            if len(arr) == 1:
                return arr[0]
        return -1

383. Ransom Note (easy)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        a, b = Counter(ransomNote), Counter(magazine)
        return a | b == b

242. Valid Anagram (easy)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        a, b = Counter(s), Counter(t)
        return a == b

75. Sort Colors (medium)

class Solution:

    def sortColors(self, nums: List[int]) -> None:
        i, j, k = 0, 0, len(nums) - 1
        while j <= k:
            if nums[j] == 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j += 1
            elif nums[j] == 1:
                j += 1
            else:
                nums[j], nums[k] = nums[k], nums[j]
                k -= 1