Blog Feed – Page 31 – 步步发财

Minimum Subarray – Python 3 (Week 13 – 09)

class Solution:
    """
    @param: nums: a list of integers
    @return: A integer indicate the sum of minimum subarray
    """
    def minSubArray(self, nums):
        # write your code here
        if not nums:
            return None
        newsum, maxsum = 0, 0
        minsum = nums[0]
        
        for i in range(len(nums)):
            newsum += nums[i]
            if newsum - maxsum < minsum:
                minsum = newsum - maxsum
            if newsum > maxsum:
                maxsum = newsum
            
        return minsum

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

Count 1 in Binary – Python 3 (Week 13 -08)

class Solution:
    """
    @param: num: An integer
    @return: An integer
    """
    def countOnes(self, num):
        # write your code here
        if num < 0:
            num &= 1 << 32 - 1
        count = 0
        while num != 0:
            num &= num - 1
            count += 1
            
        return count

Python的整数是无限长的, -1在Java/C++的32位整数中为: 11...11111 (32个1)
但是在Python中为: ...1111111111111 (无限个1)
因此在遇到负数时要先截断为32位
num &= (1 << 32)-1

strStr II – Python 3 (Week 13 – 07)

Solution 1 Rabin Karp

class Solution:
    """
    @param: source: A source string
    @param: target: A target string
    @return: An integer as index
    """
    def strStr2(self, source, target):
        # write your code here
        if source == None or target == None:
            return -1
            
        m, n = len(source), len(target)
        if n == 0:
            return 0
        if m < n:
            return -1
        
        power = 1
        base = 10000000
        hashtarget = 0
        for i in range(n):
            power = (power * 31) % base
            hashtarget = (hashtarget * 31 + ord(target[i])) % base
 

        hashcode = 0
        for i in range(m):
            hashcode = (hashcode * 31 + ord(source[i])) % base
            if i < n - 1:
                continue
            if i >= n:
                hashcode = hashcode - (ord(source[i - n]) * power) % base
                if hashcode < 0:
                    hashcode += base
            
            if hashcode == hashtarget and source[i - n + 1: i + 1] == target:
                return i - n + 1
        
        return -1

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

Longest Palindromic Substring – Python 3 (Week 13 – 06)

Solution 1 Expand Around Center

class Solution:
    """
    @param s: input string
    @return: the longest palindromic substring
    """
    def longestPalindrome(self, s):
        # write your code here
        if not s:
            return ''
        longest = ''
        for mid in range(len(s)):
            sub = self.find_palindrome_from(s, mid, mid)
            if len(sub) > len(longest):
                longest = sub
            
            sub = self.find_palindrome_from(s, mid, mid + 1)
            if len(sub) > len(longest):
                longest = sub
            
        return longest
           
          
           
           
           
    def find_palindrome_from(self, string, left, right):
        while left >= 0 and right < len(string) and string[left] == string[right]:
            left -= 1
            right += 1
        return string[left + 1 : right]

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

Solution 2 DP

 class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
            
        n = len(s)
        is_palindrome = [[False] * n for _ in range(n)]
        
        for i in range(n):
            is_palindrome[i][i] = True
        for i in range(1, n):
            is_palindrome[i][i - 1] = True
            
        longest, start, end = 1, 0, 0           
        for length in range(1, n):
            for i in range(n - length):
                j = i + length
                #if s[i] == s[j] and is_palindrome[i + 1][j - 1]:
                #    is_palindrome[i][j] = True
                is_palindrome[i][j] = s[i] == s[j] and is_palindrome[i + 1][j - 1]
                if is_palindrome[i][j] and length + 1 > longest:
                    longest = length + 1
                    start, end = i, j
        return s[start : end + 1]

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

Shortest Word Distance III – Python 3 (Week 13 – 05)

class Solution:
    def shortestWordDistance(self, words: List[str], word1: str, word2: str) -> int:
        
    
        w1, w2 = float('inf'), float('inf')
        ans = float('inf')
        same = word1 == word2
        for i in range(len(words)):
            if words[i] == word1:
                w1 = i
                ans = min(ans, abs(w1 - w2))
                if same:
                    w2 = w1
            elif words[i] == word2:
                w2 = i
                ans = min(ans, abs(w1 - w2))
                

        return ans

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

Reorganize String – Python 3 (Week 13 – 04)

heapq is a binary heap, with O(log n) push and O(log n) pop.

Solution 1

    for ct, cha in c:
        if -ct > (len(S) + 1) / 2:
            return ''

    ans = []
    while len(c) > 1:
        ct1, ch1 = heapq.heappop(c)
        ct2, ch2 = heapq.heappop(c)

        ans.append(ch1)
        ans.append(ch2)
        if ct1 + 1: heapq.heappush(c, (ct1 + 1, ch1))
        if ct2 + 1: heapq.heappush(c, (ct2 + 1, ch2))

    return ''.join(ans) + (c[0][1] if c else'')

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

Lexicographical Numbers – Python 3 (Week 13 – 03)

 class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        
        
        #1, 10, 11, 12, 13 ...,100,
        if n < 1:
            return []
        ans = [1]
        
        while len(ans) < n: #1
            new = ans[-1] * 10 #10
            while new > n:
                new //= 10 # new is ans[-1] 
                new += 1 #
                while new % 10 == 0: #not inclue 0, so 10, 100, 1000,
                    new //= 10 # until 2,3,4,5,...
                
            ans.append(new)  #10 if n is 11, 2 if n is 9 
                
            
        return ans

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

Find the nearest store – Python 3 (Week 13 – 02)

class Solution:
    """
    @param stores: The location of each store.
    @param houses: The location of each house.
    @return: The location of the nearest store to each house.
    """
    def findNearestStore(self, stores, houses):
        shmap = []
        ans = [-1] * len(houses)
        for i in range(len(stores)): #T O(n) S O(n)
            shmap.append([i, 's', stores[i]])
        for i in range(len(houses)):
            shmap.append([i, houses[i], houses[i]])
        
        shmap = sorted(shmap, key=lambda x: x[2]) #T nlogn spacen
        import math
        left = -math.inf
        for i in range(len(shmap)):
            if shmap[i][1] == 's':
                left = shmap[i][2]
            else:
                shmap[i][2] = left
                
                
        import math
        right = math.inf
        for i in range(len(shmap) - 1, -1, -1):
            
            if shmap[i][1] == 's':
                right = shmap[i][2]
            else:
                if (shmap[i][1] - shmap[i][2]) > (right - shmap[i][1]):
                    shmap[i][2] = right
                ans[shmap[i][0]] = shmap[i][2]
        
        return ans

Time O(n log n ). Space O(n). n is len(stores) + len(houses).

Encode N-ary Tree to Binary Tree – Python 3 (Week 13 – 01)

"""
class UndirectedGraphNode:
     def __init__(self, x):
         self.label = x
         self.neighbors = []Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: binary tree
    @return: N-ary tree
    """
    def decode(self, root):
        # write your code here
        if not root:
            return None
        naryTree = UndirectedGraphNode(root.val)
        #if root.left:
        #    naryTree.neighbors.append(self.decode(root.left))
            
        #cur = root.left
        #while cur and cur.right:
        #    cur = cur.right
        #    naryTree.neighbors.append(self.decode(cur))
        cur = root.left
        while cur:
            naryTree.neighbors.append(self.decode(cur))
            cur = cur.right
        
        
        
            
        return naryTree
        
        
        
        
    """
    @param root: N-ary tree
    @return: binary tree
    """
    def encode(self, root):
        # write your code here
        if not root:
            return None
            
        binaryTree = TreeNode(root.label)
        
        if root.neighbors:
            binaryTree.left = self.encode(root.neighbors[0])
        cur = binaryTree.left
        for i in range(1, len(root.neighbors)):
            cur.right = self.encode(root.neighbors[i])
            cur = cur.right
        return binaryTree

Time O(h). Space O(h).

Minimum Depth of Binary Tree – Python 3 (Week 12 – 20)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        elif root.right == None and root.left == None:
            return 1
        elif root.right == None:
            depth = self.minDepth(root.left) + 1
        elif root.left == None:
            depth = self.minDepth(root.right) + 1
        else:   
            depth = min(self.minDepth(root.right), self.minDepth(root.left)) + 1
        
        return depth

Time O(d). Space O(d).