Blog Feed – Page 43 – 步步发财

LeetCode 141 – Python 3 (Week 2 – 10)

Solution 1

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):#the input is head.We do not have pos.
        """
        :type head: ListNode
        :rtype: bool
        """
        s = set()
        
        while head and head.next:
            if head in s:
                return True
            else:
                s.add(head)
                head = head.next
        return False

Time complexity is O(n). Space complexity is O(n).

Solution 2

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):#the input is head.We do not have pos.
        """
        :type head: ListNode
        :rtype: bool
        """
        slow, fast = head, head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
            
        return False

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

LeetCode 136 – Python 3 (Week 2 – 09)

Solution 1

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        
        #Use Exclusive or 
        #a XOR 0 = a
        #a XOR a = a
        #a XOR b XOR a = a XOR a XOR b = b
        
        res = 0
        for num in nums:
            res ^= num
        return res

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

Solution 2

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        
    res = []
    for num in nums:
        if num in res:
            res.remove(num)
        else:
            res.append(num)
    return res.pop() #retur an int, not a list

Time complexity is O(n*n). Iterating through nums takes O(n) time * search num in the list takes O(n) time. Space complexity is O(n). n is the size of the list.

Solution 3

class Solution:
    def singleNumber(self, nums: List[int]) -> int:

    dic = {}
    for num in nums:
        if num in hash_table:
            dic.pop(num)
        else:
            dic[num] = 0
    return hash_table.popitem()[0] #retur an int, not a list

#pop(): Removes and returns an element from a dictionary having the given key.
#popitem():Removes the arbitrary key-value pair from the dictionary and returns it as tuple.

Time complexity is O(n). Iterating through nums takes O(n) time * search num in the dictionary takes O(1) time. Space complexity is O(n). n is the size of the nums.

Solution 4

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
   return 2 * sum(set(nums)) -sum(nums) #set() is used for creating sets

Time complexity is O(n). O(n+n)=O(n). Space complexity is O(n).

LeetCode 121 – Python 3 (Week 2 – 08)

Solution 1

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        max_profit = 0
        min_price = float('inf') #there is no infinite integer.
        
        for price in prices:
            min_price = min(price, min_price)
            max_profit = max(price-min_price, max_profit)
            
        return max_profit

Time complexity is 0(n). Space complexity is O(1).

LeetCode 94 – Python 3 (Week 2 – 07)

Inorder traversal a tree: traverse the left subtree -> the root -> traverse the right subtree.

Solution 1

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        inordertree = []
        #Recursive solution
        #Inorder traversal a tree: traverse the left subtree -> the root -> traverse the right subtree. 
        self.helper(root, inordertree)
        return inordertree
        
    
    def helper(self, root: TreeNode, res):
        if root is not None:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)

Solution 2

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        inordertree = []
        stack = []
        #Iterasive solution
        #Inorder traversal a tree: traverse the left subtree -> the root -> traverse the right subtree. The first value is the value of left leaf. Use a stack to store the nodes we traversed. This method is from bottom to top.
        
        while stack or root:
            if root:
                stack.append(root)
                root = root.left #in the last step, root is None
            ##when root is not trure, stack store the left leaf
            else:
                #store the left leaf
                node = stack.pop()
                inordertree.append(node.val) #store the root of left leaf.
                root = node.right

        return inordertree

Both time complexities are O(n). Both space complexities are O(n).

LeetCode 175 – MySQL (Week 2 – 06)

select FirstName, LastName, City, State
from Person left join Address
on Person.PersonId = Address.PersonId;

LeetCode 104 – Python 3 (Week 2 – 05)

Solution 1

class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
else:
return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

Time complexity is O(n). Space complexity is O(n).

LeetCode 101 – Python 3 (Week 2 – 04)

A tree is symmetric if the left subtree is a mirror reflection of the right subtree. If the left subtree is a mirror reflection of the right subtree, two subtrees should have same root value. The left subtree of left subtree should also be a mirror reflection of the right subtree of right subtree.

Solution 1

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

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.isMirror(root, root) #can not use (left,right). Should make sure the root is not None
    
    def isMirror(self, left, right) -> bool:
        if left is None and right is None:
            return True
        elif left is None or right is None or left.val != right.val:
            return False
        else:
            return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

We compare every pair of nodes. Time complexity is O(n). n is the number of nodes. Space complexity is O(n). The number of recursive calls is bound by the height of tree. n is the hight of tree.

LeetCode 70 – Python 3 (Week 2 – 03)

There are two ways to climb n steps: (1) climb n-1 steps + climb one step (2) climb n-2 steps + climb two step. The basic idea is that the ways for n steps is the sum of ways for n-1 steps and n-2 steps. If we use recurrence, the time complexity is high. Thus, we want to store the previous results in an array or a dictionary. But we just need return the ways for n steps which is only dependent on the ways for n-1 and n-2 steps. So, only two integer variables are needed. The link below explain all methods very clear:

https://leetcode.com/problems/climbing-stairs/discuss/163347/Python-3000DP-or-tm

Solution 1: time complexity O(n), space complexity O(1)

class Solution:
    def climbStairs(self, n: int) -> int:

        
        if n == 1: return 1
        previous, current = 1, 2 #n=1 n=2
        for _ in range(2, n):
            previous, current = current, previous + current #n-2 and n-1 starirs to n-1 and n stairs.
        return current

LeetCode 53 – Python 3 (Week 2 – 02)

Solution 1

class Solution:
   def maxSubArray(self, nums: List[int]) -> int:
        
        
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
                
        return max(nums)

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

LeetCode 21 – Python 3 (Week 2 – 01)

Solution 1 (Runtime: 40 ms Memory Usage: 13.9 MB)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

        ##### Iterative Solution
        tmp = dummy = ListNode(0)
        
        while l1 and l2:
            if l1.val < l2.val:
                tmp.next = l1
                l1 = l1.next
            else:
                tmp.next = l2
                l2 = l2.next
            tmp = tmp.next # important
        tmp.next = l1 or l2
        
        return dummy.next # not dummy

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

Solution 2 (Runtime: 44 ms Memory Usage: 13.8 MB)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        # Recursive
        
        if not l1:
            return l2
        elif not l2:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

Time complexity is O(m+n). Space complexity is O(m+n).