Как строить алгоритмы в Python: основные принципы и примеры

Как найти сумму элементов списка без встроенной функции sum?

Можно использовать цикл, рекурсию или reduce.

def sum_loop(numbers):
    total = 0
    for n in numbers:
        total += n
    return total
print(sum_loop([1,2,3,4,5]))  # 15

базовые задачи python (базовые задачи python)

def sum_recursive(numbers):
    if not numbers:
        return 0
    return numbers[0] + sum_recursive(numbers[1:])
print(sum_recursive([1,2,3,4,5]))  # 15

задачи для обучения python (задачи для обучения python)

from functools import reduce
def sum_reduce(numbers):
    return reduce(lambda x, y: x + y, numbers, 0)
print(sum_reduce([1,2,3,4,5]))  # 15

задачи на классы в python (задачи на классы в python)

Как проверить, является ли строка палиндромом?

Самый простой способ - сравнить строку с её перевернутой версией.

def is_palindrome_slice(s):
    s = s.lower().replace(' ', '')
    return s == s[::-1]
print(is_palindrome_slice('А роза упала на лапу Азора'))  # True

множество python задачи (задачи на множества в python)

def is_palindrome_two_pointers(s):
    s = s.lower().replace(' ', '')
    left, right = 0, len(s)-1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

задачи на модули python (задачи на модули в python)

Как реализовать бинарный поиск в отсортированном массиве?

Итеративная версия с циклом while:

def binary_search_iterative(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
print(binary_search_iterative([1,3,5,7,9], 5))  # 2

задачи на операторы в python (задачи на операторы в python)

Рекурсивная версия:

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid+1, high)
    else:
        return binary_search_recursive(arr, target, low, mid-1)
arr = [1,3,5,7,9]
print(binary_search_recursive(arr, 5, 0, len(arr)-1))  # 2

задачи на последовательности python (задачи на последовательности в python)

Как отсортировать список пузырьковой сортировкой?

Обычная пузырьковая сортировка:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

задачи на списки python (задачи на списки в python)

Оптимизированная версия с флагом:

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n-1):
        swapped = False
        for j in range(n-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr