Triangle – Python 3 (Week 17 – 05)

Solution 1 Divide Conquer + Memoization

class Solution:
    """
    @param triangle: a list of lists of integers
    @return: An integer, minimum path sum
    """
    def minimumTotal(self, triangle):
        # write your code here
        return self.divide_conquer(triangle, 0, 0, {})
        
    def divide_conquer(self, triangle, x, y, memo):
        if x == len(triangle):
            return 0
            
        if (x, y) in memo:
            return memo[(x, y)]
            
        left = self.divide_conquer(triangle, x + 1, y, memo)
        right = self.divide_conquer(triangle, x + 1, y + 1, memo)
        
        memo[(x, y)] = min(left, right) + triangle[x][y]
        return memo[(x, y)]

Time O(n^2). Space O(n) or O(n^2).

Sudoku Solver – Python 3 (Week 17 – 04)

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.board = board
        self.row = [[1] * 10 for i in range(9)]
        self.col = [[1] * 10 for i in range(9)]
        self.box = [[[1] * 10 for i in range(3)] for j in range(3)]
        
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    continue
                v = int(board[i][j])
                self.row[i][v] = self.col[j][v] = self.box[i//3][j//3][v] = 0
        
        
        self.dfs(0,0)
        
        
        
        
    def dfs(self, i, j):
        if i == 9:
            return True
        if self.board[i][j] != '.':
            if j < 8:
                return self.dfs(i, j + 1)
            else:
                return self.dfs(i + 1, 0)
                
        for v in range(1, 10):
            if self.row[i][v] and self.col[j][v] and self.box[i//3][j//3][v]:
                self.board[i][j] = str(v)
                self.row[i][v] = self.col[j][v] = self.box[i//3][j//3][v] = 0
                
                if j < 8:
                    if self.dfs(i, j + 1):
                        return True
                else:
                    if self.dfs(i + 1, 0):
                        return True
    
                self.row[i][v] = self.col[j][v] = self.box[i//3][j//3][v] = 1
                
        self.board[i][j] = '.'
        return False

Time O((9!)^9). Space O(81).

Word Pattern II – Python 3 (Week 17 – 03)

class Solution:
    """
    @param pattern: a string,denote pattern string
    @param str: a string, denote matching string
    @return: a boolean
    """
    def wordPatternMatch(self, pattern, str):
        # write your code here
        return self.is_match(pattern, str, {}, set())
        
        
    def is_match(self, pattern, string, mapping, used):
        if not pattern:
            return not string
        
        char = pattern[0]
        if char in mapping:
            word = mapping[char]
            if not string.startwith(word):
                return False
            return self.is_match(pattern[1:], string[len(word):], mapping, used)
            
        for i in range(len(string)):
            word = string[:i + 1]
            if word in used:
                continue
            used.add(word)
            mapping[char] = word
            
            if self.is_match(pattern[1:], string[i + 1:], mapping, used):
                return True
            
            del mapping[char]
            used.remove(word)
            
        return False

Time O(m^n). Space O(n + m).

Combination Sum II – Python 3 (Week 17 – 02)

class Solution:
    """
    @param num: Given the candidate numbers
    @param target: Given the target number
    @return: All the combinations that sum to target
    """
    def combinationSum2(self, num, target):
        # write your code here
        num.sort()
        self.ans = []
        self.dfs(num, target, 0, 0, [], [0]*len(num))
        return self.ans
        
    def dfs(self, num, target, start, now, combination, use):
    
        
        if now == target:
            self.ans.append(combination[:])
            return
        
        #if start >= len(num) or now + num[start] > target:
        #   return
    
        for i in range(start, len(num)):
            if now + num[i] <= target and (i == 0 or num[i] != num[i-1] or use[i - 1] == 1):
            #if i == 0 or num[i] != num[i-1] or use[i - 1] == 1:
                combination.append(num[i])
                use[i] = 1
                self.dfs(num, target, i + 1, now + num[i], combination, use)
                use[i] = 0
                combination.pop()

Combination Sum – Python 3 (Week 17 – 01)

class Solution:
    """
    @param candidates: A list of integers
    @param target: An integer
    @return: A list of lists of integers
    """
    
    #complexity O(s*n) s max < 2^n
    def combinationSum(self, candidates, target):
        # write your code here
        candidates = sorted(list(set(candidates)))
        results = []
        self.dfs(candidates, target, 0, [], results)
        return results
        
        
    def dfs(self, candidates, target, start, combination, results):
        if target < 0:
            return
        
        if target == 0:
            return results.append(list(combination))
            
        for i in range(start, len(candidates)):
            combination.append(candidates[i])
            self.dfs(candidates, target - candidates[i], i, combination, results)
            combination.pop()

Time O(number of solutions * n).

Subarray Sum Equals K – Python 3 (Week 16 – 04)

class Solution:
    """
    @param nums: a list of integer
    @param k: an integer
    @return: return an integer, denote the number of continuous subarrays whose sum equals to k
    """
    def subarraySumEqualsK(self, nums, k):
        # write your code here
        prefix = [nums[i] for i in range(len(nums))]
        
        for i in range(1, len(prefix)):
            prefix[i] += prefix[i - 1]
        value_to_times, ans = {0: 1}, 0
        
        for i in range(len(prefix)):
            if value_to_times.get(prefix[i] - k) != None:
                ans += value_to_times[prefix[i] - k]
            if value_to_times.get(prefix[i]) == None:
                value_to_times[prefix[i]] = 1
            else:
                value_to_times[prefix[i]] += 1
        
        return ans

Time O(n). Space O(n)>

Merge K Sorted Arrays – Python 3 (Week 16 – 03)

import heapq

class Solution:
    """
    @param arrays: k sorted integer arrays
    @return: a sorted array
    """
    def mergekSortedArrays(self, arrays):
        # write your code here
        result = []
        heap = []
        for index, array in enumerate(arrays):
            if len(array) == 0:
                continue
            #(value, index_of_array, index_of_element)
            heapq.heappush(heap, (array[0], index, 0))
            
        while len(heap):
            val, x, y = heapq.heappop(heap)
            result.append(val)
            if y == len(arrays[x]) - 1:
                continue
            heapq.heappush(heap, (arrays[x][y + 1], x, y + 1 ))
            
        return result

Time O(N log k). Space O(logk).

Merge K Sorted Lists – Python 3 (Week 16 – 02)

import heapq
"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
#override compare function
ListNode.__lt__ = lambda x,y: (x.val < y.val)
    
class Solution:
    """
    @param lists: a list of ListNode
    @return: The head of one sorted list.
    """
    
    def mergeKLists(self, lists):
        # write your code here
        if not lists:
            return None
        dummy = ListNode(0)
        tail = dummy
        heap = []
        for head in lists:
            if head:
                heapq.heappush(heap, head)
        
        while heap:
            head = heapq.heappop(heap)
            tail.next = head
            tail = head
            if head.next:
                heapq.heappush(heap, head.next)
            
        return dummy.next

Heapify – Python 3 (Week 16 – 01)

class Solution:
    """
    @param: A: Given an integer array
    @return: nothing
    """
    
    def siftup(self, A, now):
        while now:
            father = (now - 1) // 2
            #if right son: ((i*2+2) - 1) // 2 = i
            #if left son:((i*2+1) - 1) // 2 = i
            # 
            if A[now] > A[father]:
                break
            A[now], A[father] = A[father], A[now]
            
            now = father
            
            
    def heapify(self, A):
        # write your code here
        for i in range(len(A)):
            self.siftup(A, i)

Partition Array – Python 3 (Week 14 – 18)

class Solution:
“””
@param nums: The integer array you should partition
@param k: An integer
@return: The index after partition
“””
def partitionArray(self, nums, k):
# write your code here
start, end = 0, len(nums) – 1
while start <= end: while start <= end and nums[start] < k: start += 1 while start <= end and nums[end] >= k:
end -= 1
if start <= end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
return start

Design a site like this with WordPress.com
Get started