Passes Problem

152 Maximum product subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest

• Need 2 variables to record positive and negative numbers

• Swap if num < -1

• Math.max & Math.min are used to handle corner case if num==0

def maxProduct(self, nums: List[int]) -> int:
    ans = pProduct = nProduct = nums[0]
    
    for n in nums[1:]:
        if n < 0:
            pProduct, nProduct = nProduct, pProduct
        
        # nProduct is max either current num * previous product or number itself
        pProduct = max(n, pProduct*n)
        nProduct = min(n, nProduct*n)
        
        ans = max(ans, pProduct)       
    return ans

238. Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [1] * n
    
    p = nums[0]
    for i in range(1, n):
        ans[i] = p
        p *= nums[i]
        
    p = nums[n-1]
    for i in range(n-2, -1, -1):
        ans[i] *= p
        p *= nums[i]
        
    return ans

698. Partition to K Equal Sum Subset

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Explain

1. 可以處理負數

2. corner case: sum=0, 用 count > 0 紀錄加總個數

"""
nums = {-1,1,0,0}, k = 4
nums = {-1,1}, k = 1
nums = {-1,1}, k = 2
nums = {-1,1,0}, k = 2
"""
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
    if sum(nums)%k != 0: return False
    s = sum(nums)/k
    
    # decrease 能較快收斂
    nums.sort(reverse=True)
    if nums[0] > s: return False
    
    while nums and nums[0] == s:
        nums.pop(0)
        k-=1
        
    visit = [0] * len(nums)
    return self.dfs(nums, 0, 0, 0, visit, k, s)


def dfs(self, nums, idx, cur_sum, count, visit, k, s):
    # 必定valid
    if k == 1: return True
    if cur_sum > s: return False
    if cur_sum == s and count >= 1:
        return self.dfs(nums, 0, 0, 0, visit, k-1, s)
    for i in range(idx, len(nums)):
        if visit[i]: continue
        visit[i] = 1      # 前面i皆visit過了
        if self.dfs(nums, i+1, cur_sum+nums[i], count+1, visit, k, s):
            return True
        visit[i] = 0
        
    return False

472. Concatenated Words

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]

def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
    ans = []
    self.s = set(words)
    
    for w in words:
        self.s.remove(w)
        if self.isValid(w):
            ans.append(w)
        self.s.add(w)
    return ans


def isValid(self, word):
    if word in self.s: return True
    
    for i in range(1, len(word)):
        if word[:i] in self.s and self.isValid(word[i:]):
            return True
        
    return False