Python Coding Cheat Sheet
1. Bitwise Operation
Find the lowest set bit
a & -a
Finds the rightmost bit 1 (the lowest set bit).
For example:
Decimal 12 is bianry 1100.
Decimal -12 (assuming 8-bit representation) is 11110011 + 1 = 11110100 (inverting all bits and plus 1).
AND operation of 12 and -12 gives 0100. Which is gives the location of the rightmost set bit.
Right and left shift
a >> 1 and a // 2 is the same.
a << 1 and a * 2 is the same.
Binary representation of integers
As String
bin_str = str(bin(N))[2:]
Count bits
n = 23
# number of total 1 bits
num_ones = n.bit_count()
num_ones = bin(n).count('1')
# number of total bits
num_bits = n.bit_length()
num_bits = len(bin(n)) - 2
XOR
If the bits are different, the result is 1. If the bits are the same, the result is 0.
a = 5 # Binary: 0101
b = 3 # Binary: 0011
result = a ^ b # Binary: 0110, Decimal: 6
print(result) # Output: 6
Special property when a number xor with 0:
a = 5 # Binary: 0101
b = 0 # Binary: 0000
result = a ^ b # Binary: 0101, Decimal: 5
a = 5 # Binary: 0101
b = 5 # Binary: 0101
result = a ^ b # Binary: 0000, Decimal: 0
when xor with 0, the number is unchanged when xor with itself, the number is changed to 0
2. list
Create a list
dp = [-inf] * m + [0]
For example, if m = 3, this creates a list [-inf, -inf, -inf, 0]
If m = 0, the list would be [0]
Create a 2D list
dp = [[0] * m for _ in range(n)]
This creates a 2D list of size n * m.
Note:
dp = [[0] * m] * n
This creates a 2D list where each row is a reference to the same inner list. As a result, modifying one element in one row modifies the corresponding element in all rows because they all point to the same memory location. This leads to incorrect behavior when updating the dp table.
Reverse a list
res[::-1]
This creates a new list.
my_list.reverse()
This modifies the original list.
Compare all elements of two lists
Returns true if all elements are equal. False otherwise.
return list1[:] == list2[:]
All elements are true
if all(A):
# do something if all elements are True
if all(v == 0 for v in dict.values()):
# do something if all elements equals to something
Sorting a list
# Example list of lists
data = [[3, 2], [1, 5], [3, 1], [2, 4], [1, 3]]
# Sort by the first integer, and if they are equal, sort by the second integer
sorted_data = sorted(data, key=lambda x: (x[0], x[1]))
print(sorted_data)
or, using list.sort()
# Example list of lists
data = [[3, 2], [1, 5], [3, 1], [2, 4], [1, 3]]
# Sort in-place by the first integer, and if they are equal, by the second integer
data.sort(key=lambda x: (x[0], x[1]))
print(data)
3. Dict
Create a default dict
This default dict will increment 1 whenever the key is accessed. Default value is 0.
from collections import defaultdict, Counter
dp = defaultdict(Counter)
dp = Counter()
dp = defaultdict(int)
To iterate over a defaultdict
for k,v in d.items():
print (f"{k} - {v}")
We can also iterate over its values/keys
for i in d.keys():
print(i)
for i in d.values():
print(i)
4. Heap
Heap is min-heap by default. Store negative values to represent a max-heap.
import heapq
max_heap = []
# Insert values into the max-heap by pushing the negative value
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -40)
# Convert back to positive to get the max value
max_value = -heapq.heappop(max_heap)
print("Max value:", max_value)
# To get all items in sorted descending order
sorted_items = [-heapq.heappop(max_heap) for _ in range(len(max_heap))]
print("Max-Heap items sorted:", sorted_items)
For a min_heap, min_heap[0] is the head of the heap, which returns the minimum value in the heap.
heappop(min_heap) also pops the min value out, which is the head.
5. String
Convert a list to string
res = ["a", "b", "c"]
print(''.join(res))
This should print abc.
String Slicing
Python string slicing is a way to access a subset of a string using the slicing syntax:
string[start:stop:step]
Note, start is inclusive but stop is exclusive.
For example, s[0:2] of s = "hello" should return "he"
Split String
string = "one,two,three"
words = string.split(',')
6. Deque
Double-ended queue
from collections import deque
def bfs(root: TreeNode)
# Declare and initiate a deque and store the root node.
q = deque([root])
You can also init deque with a list
from collections import deque
# See Leetcode #1926
def bfs(entrance: list[int])
# Declare and initiate a deque and store the entrance position.
q = deque([entrance])
7. Tuple
Convert list into a tuple to see if one position has been visited before.
tuple(list)
Construct a tuple with two integers.
(1, 2)
def nearestExit(maze: List[List[str]], entrance: List[int]) -> int:
def findNeighbor(currentPos: List[int], v: set) -> List[List[int]]:
neighbors = []
row, col = currentPos
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for dr, dc in directions:
newRow, newCol = row + dr, col + dc
if 0 <= newRow < len(maze) and 0 <= newCol < len(maze[0]) and maze[newRow][newCol] == '.' and (newRow, newCol) not in v:
neighbors.append([newRow, newCol])
return neighbors
def isExit(currentPos: List[int]) -> bool:
row, col = currentPos
if currentPos == entrance:
return False
return row == 0 or row == len(maze) - 1 or col == 0 or col == len(maze[0]) - 1
visited = set()
q = deque([entrance])
distance = 0
while q:
N = len(q)
for _ in range(N):
currentPos = q.popleft()
# NOTE: convert list of two elements into tuple
if tuple(currentPos) in visited:
continue
visited.add(tuple(currentPos))
if isExit(currentPos):
return distance
for neighbor in findNeighbor(currentPos, visited):
q.append(neighbor)
distance += 1
return -1