23.03.20 Today’s Leetcode

605. Can Place Flowers (easy)

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        m = len(flowerbed)
        count = 0
        for i in range(m):
            a = b = c = False
            if i - 1 < 0 or flowerbed[i - 1] == 0: a = True
            if i + 1 >= m or flowerbed[i + 1] == 0: b = True
            if flowerbed[i] == 0: c = True
            if a and b and c:
                flowerbed[i] = 1
                count += 1

        # print(flowerbed, count)
        return n <= count

326. Power of Three (easy)

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0: return False
        if n == 1: return True
        if n % 3 != 0: return False
        return self.isPowerOfThree(n // 3)

331. Verify Preorder Serialization of a Binary Tree (medium)

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        split = preorder.split(',')
        def dfs(arr):
            # print(arr)
            if arr[0] == '#':
                return 1
            if len(arr) < 3:
                return 0
            if arr[1] == '#' and arr[2] == '#':
                # leaf node, next node is behind 3 index
                return 3
            left = dfs(arr[1:])
            right = dfs(arr[1 + left:])
            return 1 + left + right
        
        return dfs(split) == len(split)

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        preorder = preorder.split(',')
        index = 0
        def dfs():
            nonlocal preorder, index
            if index >= len(preorder):
                return False
            if preorder[index] == '#':
                index += 1
                return True
            index += 1
            if dfs() and dfs():
                return True
            return False
        return dfs() and index == len(preorder) 

347. Top K Frequent Elements (medium)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = Counter(nums)
        d = defaultdict(set)
        for p in counter.keys():
            d[counter[p]].add(p)

        res = []
        order = sorted(list(d.keys()), reverse=True)
        # print(order)
        for key in order:
            res += list(d[key])
        
        return res[:k]

343. Integer Break (medium)

class Solution:
    def integerBreak(self, n: int) -> int:
        # Initialize dp array with 0's
        dp = [0]*(n+1)
        
        # Base case
        dp[2] = 1
        
        # Iterate from 3 to n
        for i in range(3, n+1):
            # Iterate from 1 to i//2
            for j in range(1, i//2+1):
                # Calculate the product of j and i-j
                prod = j*(i-j)
                
                # Update the maximum product in dp[i]
                dp[i] = max(dp[i], max(prod, j*dp[i-j]))
        
        # Return dp[n]
        return dp[n]