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]
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
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"
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