Scribd
Upload
38 views3 pages

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
38 views3 pages

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

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

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]:
[Link](left[i]); i += 1
else:
[Link](right[j]); j += 1
[Link](left[i:])
[Link](right[j:])
return res

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


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

def dfs(graph, start):


visited = set()
order = []
def _dfs(node):
if node in visited:
return
[Link](node)
[Link](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 = [Link](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
[Link](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):
[Link] = list(range(n))
[Link] = [0]*n

def find(self, x):


if [Link][x] != x:
[Link][x] = [Link]([Link][x])
return [Link][x]

def union(self, x, y):


rootX = [Link](x)
rootY = [Link](y)
if rootX == rootY:
return False
if [Link][rootX] < [Link][rootY]:
[Link][rootX] = rootY
elif [Link][rootX] > [Link][rootY]:
[Link][rootY] = rootX
else:
[Link][rootY] = rootX
[Link][rootX] += 1
return True

You might also like