Scribd
Upload
4 views

algorithms_leetcode

The document contains Python implementations of various algorithms including binary search, quick sort, merge sort, breadth-first search (BFS), depth-first search (DFS), Dijkstra's algorithm, two-pointer technique for the Two Sum problem, sliding window for maximum subarray sum, climbing stairs, and a disjoint set union (Union-Find) class. Each algorithm is provided with a brief description and its corresponding code. These algorithms are fundamental for solving common problems in computer science and programming.

Uploaded by

Денис Шеремет
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views

algorithms_leetcode

The document contains Python implementations of various algorithms including binary search, quick sort, merge sort, breadth-first search (BFS), depth-first search (DFS), Dijkstra's algorithm, two-pointer technique for the Two Sum problem, sliding window for maximum subarray sum, climbing stairs, and a disjoint set union (Union-Find) class. Each algorithm is provided with a brief description and its corresponding code. These algorithms are fundamental for solving common problems in computer science and programming.

Uploaded by

Денис Шеремет
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

■■■■■■■■■ ■ ■■■■■■■■■ ■■■■■■ ■■■

LeetCode ■■ Python

1. ■■■■■■■■ ■■■■■
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

2. ■■■■■■■ ■■■■■■■■■■ (Quick Sort)


def quick_sort(arr):
def _qs(nums, low, high):
if low < high:
pivot = nums[high]
i = low
for j in range(low, high):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[high] = nums[high], nums[i]
_qs(nums, low, i-1)
_qs(nums, i+1, high)
_qs(arr, 0, len(arr)-1)
return arr

3. ■■■■■■■■■■ ■■■■■■■■ (Merge Sort)


def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
res = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
res.append(left[i]); i += 1
else:
res.append(right[j]); j += 1
res.extend(left[i:])
res.extend(right[j:])
return res

4. ■■■■■ ■■■■■: BFS ■ DFS


from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order

def dfs(graph, start):


visited = set()
order = []
def _dfs(node):
if node in visited:
return
visited.add(node)
order.append(node)
for neighbor in graph[node]:
_dfs(neighbor)
_dfs(start)
return order

5. ■■■■■■■■ ■■■■■■■■
import heapq

def dijkstra(graph, start):


distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
dist, node = heapq.heappop(pq)
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distances

6. ■■■ ■■■■■■■■■ (Two Pointers) — ■■■■■■


Two Sum II
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current = arr[left] + arr[right]
if current == target:
return left, right
elif current < target:
left += 1
else:
right -= 1
return -1, -1
7. ■■■■■■■■■■ ■■■■ (Sliding Window) —
■■■■■■ Max Subarray Sum
def max_subarray_sum(arr, k):
max_sum = float('-inf')
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(len(arr)-k):
window_sum = window_sum - arr[i] + arr[i+k]
max_sum = max(max_sum, window_sum)
return max_sum

8. ■■■■■■■■■■■■ ■■■■■■■■■■■■■■■■ —
Climbing Stairs
def climb_stairs(n):
if n <= 2:
return n
first, second = 1, 2
for _ in range(3, n+1):
first, second = second, first + second
return second

9. Disjoint Set Union (Union-Find)


class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0]*n

def find(self, x):


if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]

def union(self, x, y):


rootX = self.find(x)
rootY = self.find(y)
if rootX == rootY:
return False
if self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
return True

You might also like