Find K Closest Elements – Python 3 (Week 17 – 15)

class Solution:
    """
    @param A: an integer array
    @param target: An integer
    @param k: An integer
    @return: an integer array
    """
    def kClosestNumbers(self, nums, target, k):
        # write your code here
        if not nums or not target or not k:
            return []
            
        if k > len(nums):
            return nums
            
        start = 0
        end = len(nums) - 1
        
        while start + 1 < end:
            mid = start + (end - start) // 2
            if nums[mid] < target:
                start = mid
            else:
                end = mid
                
        result = []
        
        left, right = start, end
        
        for _ in range(k):
            if left < 0:
                result.append(nums[right])
                right += 1
            elif right >= len(nums):
                result.append(nums[left])
                left -= 1
            elif target - nums[left] <= nums[right] - target:
                result.append(nums[left])
                left -= 1
            else:
                result.append(nums[right])
                right += 1
        
        return result

Time O(logn +k). Space O(1).

Maximum Number in Mountain Sequence – Python 3 (Week 17 – 14)

class Solution:
    """
    @param nums: a mountain sequence which increase firstly and then decrease
    @return: then mountain top
    """
    def mountainSequence(self, nums):
        # write your code here
        if not nums:
            return None
        
        length = len(nums)
        
        if length == 1:
            return nums[0]
            
        start = 0
        end = length - 1
        
        while start + 1 < end:
            mid = start + (end - start) // 2
            if nums[mid - 1] < nums[mid]:
                start = mid
            else:
                end = mid
            
        if nums[start] > nums[end]:
            return nums[start]
        else:
            return nums[end]

Last Position of Target – Python 3 ( Week 17 – 13)

class Solution:
    """
    @param nums: An integer array sorted in ascending order
    @param target: An integer
    @return: An integer
    """
    def lastPosition(self, nums, target):
        # write your code here
        if not nums or not target:
            return -1
        
        start = 0
        end = len(nums) - 1
        
        while start + 1 < end:
            mid = start + (end - start) // 2
            if nums[mid] <= target:
                start = mid
            else:
                end = mid
                
        if nums[end] == target:
            return end
        elif nums[start] == target:
            return start
            
        return -1

Paint House – Python 3 (Week 17 – 12)

class Solution:
    """
    @param costs: n x 3 cost matrix
    @return: An integer, the minimum cost to paint all houses
    """
    def minCost(self, cost):
        # write your code here
        if len(cost) == 0:
            return 0
            
        for i in range(1, len(cost)):
            for j in range(3):
                cost[i][j] = cost[i][j] + min(cost[i - 1][(j + 1) % 3], cost[i - 1][(j + 2) % 3])
        
        return min(cost[-1][0], cost[-1][1], cost[-1][2])

Time O(n). Space O(1).

Longest Palindromic Subsequence – Python 3 (Week 17 – 11)

class Solution:
    """
    @param s: the maximum length of s is 1000
    @return: the longest palindromic subsequence's length
    """
    def longestPalindromeSubseq(self, s):
        # write your code here
        length = len(s)
        if length == 0:
            return 0

        dp = [[0 for i in range(length)] for j in range(length)]
        
        for i in range(length - 1, - 1, - 1):
            dp[i][i] = 1
            for j in range(i + 1, length):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1] [j], dp[i][j - 1])
       
        return dp[0][length - 1]

Space, Time O(n^2).

Largest Divisible Subset – Python 3 (Week 17 – 10)

class Solution:
    """
    @param: nums: a set of distinct positive integers
    @return: the largest subset 
    """
    def largestDivisibleSubset(self, nums):
        # write your code here
        n = len(nums)
        dp = [1] * n
        father = [-1] * n
        
        nums.sort()
        m, index = 0, -1
 
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j] + 1 > dp [i]:
                        dp[i] = dp[j] + 1
                        father[i] = j
                        
            if dp[i] >= m:
                m = dp[i]
                index = i
        
        result = []
        
        for i in range(m):
            result.append(nums[index])
            index = father[index]
            
        return result

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

Longest Increasing Subsequence – Python 3 (Week 17 – 09)

class Solution:
    """
    @param nums: An integer array
    @return: The length of LIS (longest increasing subsequence)
    """
    def longestIncreasingSubsequence(self, nums):
        # write your code here
        if nums is None or not nums:
            return 0
        
        dp = [1] * len(nums)
        for curr, val in enumerate(nums):
            for prev in range(curr):
                if nums[prev] < val:
                    dp[curr] = max(dp[curr], dp[prev] + 1)
                    
        return max(dp)

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

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

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.startswith(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

Regular Expression Matching – Python 3 (Week 17 – 07)

class Solution:
    """
    @param s: A string 
    @param p: A string includes "." and "*"
    @return: A boolean
    """
    def isMatch(self, s, p):
        # write your code here
        return self.is_match_helper(s, 0, p, 0, {})
        
    def is_match_helper(self, s, i, p, j, memo):
        if (i, j) in memo:
            return memo[(i, j)]
            
        if len(s) == i:
            return self.is_empty(p[j:])
        if len(p) == j:
            return False
        
        if j + 1 < len(p) and p[j + 1] == '*':
            matched = self.is_match_char(s[i], p[j]) and self.is_match_helper(s, i + 1, p, j, memo) or self.is_match_helper(s, i, p, j + 2, memo)
        else:
            matched = self.is_match_char(s[i], p[j]) and self.is_match_helper(s, i + 1, p, j + 1, memo)
        
        memo[(i, j)] = matched
        
        return memo[(i, j)]
        
    
    def is_match_char(self, s, p):
        return s == p or p == '.'
        
        
    def is_empty(self, p):
        if len(p) % 2 == 1:
            return False
        for i in range(len(p) // 2):
            if p[i * 2 + 1] != '*':
                return False
        return True

Time, Space O(mn).

Wildcard Matching – Python 3 (Week 17 – 06)

class Solution:
    """
    @param s: A string 
    @param p: A string includes "?" and "*"
    @return: is Match?
    """
    def isMatch(self, source, pattern):
        # write your code here
        return self.is_match_helper(source, 0, pattern, 0, {})
        
    def is_match_helper(self, source, i, pattern, j, memo):
        if (i, j) in memo:
            return memo[(i, j)]
        
        if len(source) == i:
            for index in range(j, len(pattern)):
                if pattern[index] != '*':
                    return False
            return True
        
        if len(pattern) == j:
            return False

        
        if pattern[j] != '*':
            matched = self.is_match_char(source[i], pattern[j]) and self.is_match_helper(source, i + 1, pattern, j + 1, memo)
        else:
            matched = self.is_match_helper(source, i + 1, pattern, j, memo) or self.is_match_helper(source, i, pattern, j + 1, memo)
            
        memo[(i, j)] = matched
        return matched
        
    def is_match_char(self, s, p):
        return s == p or p == '?'

Time, Space O(len(s)*len(p)).

Design a site like this with WordPress.com
Get started