Leetcode Interview Preparation Notes #

arr = []          # O(1)
arr = [1, 2, 3]   # O(n), where n is the number of elements
first_element = arr[0]  # O(1)
arr[1] = 10  # O(1)
arr.append(6)  # O(1) on average for appending
arr.insert(2, 15)  # O(n), where n is the number of elements after the insertion index
arr.remove(15)  # O(n), where n is the number of elements in the list [remove the first 15 in the array]
del arr[2]  # O(n), where n is the number of elements after the deleted index
last_element = arr.pop()  # O(1)
arr.sort()  # 原地排序
sorted_arr = sorted(arr)  # 返回排序后的数组
arr[::-1] # arr 倒序

## Counter() 的常用语法和使用情况
from collections import Counter
arr = [1, 2, 2, 3, 3, 3]
counts = Counter(arr)  # 结果：Counter({3: 3, 2: 2, 1: 1})

## 找到出现次数最多的元素
most_common_element = counts.most_common(1)[0]  # 结果：(3, 3)

## 判断出现的元素是否相同
arr1 = [1, 2, 3]
arr2 = [3, 2, 1]
is_anagram = Counter(arr1) == Counter(arr2)  # 结果：True

## set() 的常用语法和使用情况
arr = [1, 2, 2, 3, 4, 4]

## 快速查找
seen = set(arr)
if 3 in seen:
    print("3 is in array")

## 去重
unique_elements = list(set(arr))  # 结果：[1, 2, 3, 4]

## 两个数组的交集
arr1 = [1, 2, 2, 3]
arr2 = [2, 3, 4]
intersection = list(set(arr1) & set(arr2))  # 结果：[2, 3]

s = "Hello, World!"  # O(n), where n is the length of the string
first_char = s[0]  # O(1)
substring = s[7:12]  # O(k), where k is the length of the substring
combined = s + " Python"  # O(n + m), where n and m are the lengths of the two strings
repeated = s * 2  # O(n * k), where k is the number of repetitions

upper_s = s.upper()  # O(n), where n is the length of the string
lower_s = s.lower()  # O(n), where n is the length of the string
starts_with_hello = s.startswith("Hello")  # O(n), where n is the length of the prefix
contains_world = "World" in s  # O(n * m), where n is the length of the string and m is the length of the substring
replaced_s = s.replace("World", "Python")  # O(n * m), where n is the length of the string and m is the length of the substring

words = s.split(", ")  # O(n), where n is the length of the string
joined = " - ".join(words)  # O(n), where n is the total length of the resulting string

string = "Hello, World!"
reversed_string = string[::-1] # 使用切片语法将字符串的顺序反过来 -> !dlroW ,olleH

## A node in a linked list can be represented as a class

class ListNode:
    def __init__(self, data=0, next=None):
        self.data = data  # Data of the node
        self.next = next  # Pointer to the next node

##  Inserting Nodes

def insert_at_beginning(head, data):
    new_node = ListNode(data)  # Create a new node
    new_node.next = head       # Link the new node to the current head
    return new_node            # New node becomes the head

## Deleting Nodes

def delete_from_beginning(head):
    if not head:
        return None
    return head.next  # The second node becomes the new head

## Searching for a Node

def search(head, key):
    current = head
    while current:
        if current.data == key:
            return True  # Found the data
        current = current.next
    return False  # Data not found

stack = []

# Push elements onto the stack
stack.append(1)
stack.append(2)

# Pop element from the stack
top = stack.pop()  # Removes and returns 2

# Peek the top element
top = stack[-1] if stack else None  # Returns 1

# Check if the stack is empty
is_empty = len(stack) == 0

from collections import deque

# Initialize a queue
queue = deque()

# Enqueue elements
queue.append(1)
queue.append(2)

# Dequeue element
front = queue.popleft()  # Removes and returns 1

# Peek at the front element
front = queue[0] if queue else None

# Check if the queue is empty
is_empty = len(queue) == 0

from collections import deque

# Initialize a deque
dq = deque()

# Add elements
dq.append(1)       # Add to the right
dq.appendleft(2)   # Add to the left

# Remove elements
dq.pop()           # Remove from the right
dq.popleft()       # Remove from the left

# Access and manipulation
dq.extend([3, 4])          # Add multiple elements to the right
dq.extendleft([0, -1])     # Add multiple elements to the left (reversed order)
dq.rotate(1)               # Rotate elements right
dq.rotate(-1)              # Rotate elements left
dq.clear()                 # Clear all elements

import heapq

# Initialize a heap
heap = []

# Add elements
heapq.heappush(heap, 3)  # Push element into the heap
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)

# Access the smallest element
smallest = heap[0]

# Remove elements
min_element = heapq.heappop(heap)  # Pop the smallest element

# Heapify an existing list
nums = [4, 1, 7, 3]
heapq.heapify(nums)

# Get n largest or smallest elements
largest = heapq.nlargest(2, nums)
smallest = heapq.nsmallest(2, nums)

my_dict = {}  # Creating an empty dictionary
my_dict = {'key1': 'value1', 'key2': 'value2'}  # Creating a dictionary with initial values
value = my_dict['key1']   # Accessing a value by key
my_dict['key3'] = 'value3'  # Adding a new key-value pair
my_dict['key2'] = 'new_value2'  # Updating an existing key-value pair
del my_dict['key1']   # Removing an entry by key
value = my_dict.pop('key2')  # Popping an entry (removes and returns the value)
exists = 'key3' in my_dict  # # Checking if a key is in the dictionary [True]

for key in my_dict:
    print(key, my_dict[key]) # Iterating through keys
for key, value in my_dict.items(): # Iterating through key-value pairs
    print(key, value)
for value in my_dict.values(): # Iterating through values
    print(value)

# defaultdict 使用方法，没见过的元素不会报错。适用于计数、分组和嵌套字典等应用。

from collections import defaultdict

# 使用 int 类型的 defaultdict
dd = defaultdict(int)
print(dd['missing_key'])  # 输出：0，因为 int() 的默认值是 0
print(dd)  # 输出：defaultdict(<class 'int'>, {'missing_key': 0})

# 统计元素出现次数
data = "abracadabra"
counter = defaultdict(int)
for char in data:
    counter[char] += 1
print(counter)  # 输出：defaultdict(<class 'int'>, {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

# defaultdict(list)常用于将多个值归类到同一个键下。
data = [("apple", 1), ("banana", 2), ("apple", 3), ("banana", 4)]
grouped_data = defaultdict(list)
for fruit, count in data:
    grouped_data[fruit].append(count)
print(grouped_data)  # 输出：defaultdict(<class 'list'>, {'apple': [1, 3], 'banana': [2, 4]})

# 可以使用dict()将defaultdict转换为普通字典。
dd = defaultdict(int)
dd['a'] += 1
print(dict(dd))  # 输出：{'a': 1}

## Trees are often represented using classes. 

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

## Preorder Traversal (Root, Left, Right)
def preorder_traversal(root):
    if root:
        print(root.val)
        preorder_traversal(root.left)
        preorder_traversal(root.right)

## Inorder Traversal (Left, Root, Right)
def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val)
        inorder_traversal(root.right)

## Postorder Traversal (Left, Right, Root)
def postorder_traversal(root):
    if root:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val)

## Binary Search Tree (BST) Operations

## 1. Insert a Node
def insert_into_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

## 	2. Search for a Value
def search_bst(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search_bst(root.left, val)
    return search_bst(root.right, val)

## 	3. Delete a Node
def delete_node(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        min_larger_node = root.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        root.val = min_larger_node.val
        root.right = delete_node(root.right, root.val)
    return root

## Input [1, 2, 3, 4] -> Output [2x3x4, 1x3x4, 1x2x4, 1x2x3] = [24, 12, 8, 6]
## Predix -> [0, 1, 1x2, 1x2x3] = [0, 1, 2, 6]
## Suffix -> [2x3x4, 3x4, 4, 0] = [24, 12, 4, 0]

def productExceptSelf(self, nums: List[int]) -> List[int]:
  res = [1] * len(nums)
  prefix, suffix = 1, 1

  for i in range(len(nums)):
    res[i] = prefix
    prefix *= nums[i]

  for j in range(len(nums)-1,-1,-1):
    res[j] *= suffix
    suffix *= nums[j]
        
  return res

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid  # 找到目标
        elif arr[mid] < target:
            left = mid + 1  # 目标值在右侧
        else:
            right = mid - 1  # 目标值在左侧
    return -1  # 未找到目标

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

def fibonacci(n):
    if n <= 1:
        return n  # 基准情况
    return fibonacci(n-1) + fibonacci(n-2)  # 递归关系

def permutations(nums):
    result = []
    
    def backtrack(path, remaining):
        if not remaining:  # 终止条件：所有元素已被使用
            result.append(path)
            return
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
    
    backtrack([], nums)
    return result

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

graph = {0: [1, 2], 1: [0, 3], 2: [0, 4], 3: [1], 4: [2]}
print(dfs(graph, 0))  # Output: {0, 1, 2, 3, 4}

from collections import deque

def bfs_tree(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")  # 访问当前节点
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

bfs_tree(root)  # 输出: 1 2 3 4 5