Experienced Python

2023-05-04
#python
Programming Language

  • List Comprehension

    1
    2
    3
    m, n = 10, 10
    dp = [0]*n # 1d array
    dp = [[False]*n for _ in range(m)] # 2d array, never use [[False]*n]*m, it is a trap! Because * is copying the address of the object (list)

  • Binary Search

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    import bisect
    """
    https://docs.python.org/3/library/bisect.html

    bisect.bisect_left returns the leftmost place in the sorted list to insert the given element.
    bisect.bisect_right returns the rightmost place in the sorted list to insert the given element.

    They are equivalent when the the element to be inserted is not present in the list. Hence, they are not equivalent when the element to be inserted is in the list.
    """
    nums = [-1,1]

    # The element does not present in nums
    lIdx = bisect.bisect_left(nums, 0) # return 1
    rIdx = bisect.bisect_right(nums, 0) # return 1

    # The element presents in nums
    lIdx = bisect.bisect_left(nums, 1) # return 1
    rIdx = bisect.bisect_right(nums, 1) # return 2

  • Doubly Ended Queue

    1
    2
    3
    4
    5
    q = collections.dequeue([1,2,3]) # initialize a Queue, e.g., tree level order traverse
    q.append() # append at end
    q.appendleft() # append at head
    q.pop() # pop q[-1]
    q.popleft() # pop q[0]

  • Priority Queue

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    import heapq
    """
    # https://docs.python.org/3/library/heapq.html
    """
    h = []
    heapq.heapify(h) # min-heap by default; mulitplying the input with "-1" to use as a max-heap
    heapq.heappush(h, 5)
    heapq.heappop(h)
    heapq.nlargest(3, h)
    heapq.nsmallest(3, h)
    • LeetCode 347. Top K Frequent Elements. Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      def topKFrequent(self, nums: List[int], k: int) -> List[int]:
      	"""
      	Input: nums = [1,1,1,2,2,3], k = 2
      	Output: [1,2]
      	"""
          count = collections.Counter(nums)
          # note the usage of "key" parameter in nlargest()
          return heapq.nlargest(k, count.keys(), key=count.get)

  • misc

    • nonlocal, the nonlocal keyword is used to work with variables inside nested functions, where the variable should not belong to the inner function. Use the keyword nonlocal to declare that the variable is not local, which is particularly useful when updating some global variables in recursive calls.

      • LeetCode 124. Binary Tree Maximum Path Sum. A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        # Definition for a binary tree node.
        # class TreeNode:
        #     def __init__(self, val=0, left=None, right=None):
        #         self.val = val
        #         self.left = left
        #         self.right = right
        class Solution:
            def maxPathSum(self, root: Optional[TreeNode]) -> int:
                max_sum = float('-inf')
                
                def dfs(node):
                    if not node:
                        return 0
                    nonlocal max_sum   
                    # Recursively find the maximum sum in the left and right subtrees
                    left_sum = max(dfs(node.left), 0)
                    right_sum = max(dfs(node.right), 0)
                    
                    # Update the current maximum path sum
                    current_sum = left_sum + node.val + right_sum
                    max_sum = max(max_sum, current_sum)
                    
                    # Return the maximum sum that includes either the left or right subtree
                    return max(left_sum, right_sum) + node.val
                
                dfs(root)
                
                return max_sum

    • chr() vs. ord(); ord() function returns an integer representing the Unicode character; chr() function returns the Unicode character with an integer as input

      • LeetCode 49. Group Anagrams. Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        	"""
        	Input: strs = ["eat","tea","tan","ate","nat","bat"]
        	Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
        	"""
            tmpMap = collections.defaultdict(list)
            for s in strs:
                tmp = [0]*26
                for char in s:
                	# ord('a') returns the integer representation of 'a'
                    tmp[ord(char)-ord('a')] += 1
                tmpMap[tuple(tmp)].append(s)
                #print(tuple(tmp))
            return [val for val in tmpMap.values()]

    • sort() and sorted()

      1
      2
      3
      4
      5
      6
      7
      8
      nums = [[23,1],[4,56]]
      nums.sort(key=lambda x:x[0]) # [[4, 56], [23, 1]], non-descending by default
      nums.sort(key=lambda x:x[0], reverse=True) # [[23, 1], [4, 56]], non-ascending using "reverse"

      nums.sort(key=lambda x:x[1]) # [[23, 1], [4, 56]]
      nums.sort(key=lambda x:x[1], reverse=True) # [[4, 56], [23, 1]]

      newArray = sorted(nums,key=lambda x:x[0],reverse=True) # a deep copy of nums

    • filter(), map() and reduce()[1]

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14

      from functools import reduce

      numbers = range(10)

      # Use map(), filter(), and reduce() to preprocess and aggregate the list of numbers
      even_numbers = filter(lambda x: x % 2 == 0, numbers)
      print(even_numbers) # <filter object at 0x7ff6d0eceda0>, note that filter() returns an iterable object
      print(list(even_numbers)) # [0, 2, 4, 6, 8]

      squares = map(lambda x: x**2, numbers)
      print(squares) # <map object at 0x7ff6d103e950>
      sum_of_squares = reduce(lambda x, y: x + y, squares)
      print(sum_of_squares) # 285

    • any() and all() are built-in functions that allow for checking if any or all elements in an iterable meet a certain condition.

      1
      2
      3
      data = [1, 3, 5, 7]
      print(any(x % 2 == 0 for x in data)) # False
      print(all(x % 2 == 1 for x in data)) # True

    • *args and **kwargs
      Need to fill in examples

    • assert(), raise()

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      a = 1
      assert a>100 # False

      if a > 100:
      	raise Exception('a cannot be higher than 100') # raise standard exception

       class ScoreException(Exception):
       	def __init__(self):
       		super().__init__('score cannot be higher than 100')

       if score > 100:
       	raise ScoreException() # raise customized exception

    • f-string[2]

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      # lambda functions
      from datetime import date

      print(f"Today is {date.today()}") # Today is 2023-03-13
      print(f"This is result from a lambda: {(lambda x: x ** 2)(3)}") # This is result from a lambda: 9

      # percentage formatting: {:.n%}

      jumbo_shrimp = 0.4245

      print(f"42% of something: {jumbo_shrimp:.0%}") # 42% of something: 42%
      print(f"Percentage of something: {jumbo_shrimp:.1%}") # Percentage of something: 42.4%
      print(f"Percentage of another thing: {jumbo_shrimp:.2%}") # Percentage of another thing: 42.45%
         

      # printing the value of a variable: {=}

      sassy = 1
      pants = 0

      print(f"{sassy=}") # sassy=1
      print(f"{pants = }") # pants = 0

  • Classes

    • init(), str() and gt()[3]
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      class Panda():
          def __init__(self, name, age):
              self.name = name
              self.age = age

          def __str__(self):
              return f'Panda(name="{self.name}", age={self.age})'

          def __gt__(self, otherPanda):
              return self.age > otherPanda.age

      p1, p2 = Panda("Yuanyuan", 1), Panda("Huanhuan", 2)

      print(p1) # Panda(name='Yuanyuan',age=1), which calls the __str__() function

      print(p1>p2) # False, it compares 2 objects by the __gt__() function

  • principals

    • Docstrings[4], the first line of the docstring is a brief explanation of the function’s purpose. The next element of a docstring is an explanation of the function’s arguments.
      1
      2
      3
      def population_density(population, land_area):
          """Calculate the population density of an area."""
          return population / land_area