1. Merge Sorted Array

Описание: Объединить два отсортированных массива nums1 и nums2 в первый массив nums1, который имеет достаточный размер.

def merge(nums1, m, nums2, n):
    """
    Объединение двух отсортированных массивов in-place в nums1
    """
    i, j, k = m - 1, n - 1, m + n - 1
    
    # Идем с конца, чтобы не перезаписывать элементы nums1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    # Копируем оставшиеся элементы из nums2 (если есть)
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

2. Remove Element

Описание: Удалить все вхождения значения val из массива nums in-place и вернуть новую длину.

def removeElement(nums, val):
    """
    Удаление всех вхождений val in-place
    Возвращает новую длину массива
    """
    k = 0  # Указатель для записи элементов, не равных val
    
    for i in range(len(nums)):
        if nums[i] != val:
            nums[k] = nums[i]
            k += 1
    
    return k

3. Remove Duplicates from Sorted Array

Описание: Удалить дубликаты из отсортированного массива in-place.

def removeDuplicates(nums):
    """
    Удаление дубликатов из отсортированного массива
    Возвращает новую длину
    """
    if not nums:
        return 0
    
    k = 1  # Индекс для записи уникальных элементов
    
    for i in range(1, len(nums)):
        if nums[i] != nums[i-1]:
            nums[k] = nums[i]
            k += 1
    
    return k

4. Remove Duplicates from Sorted Array II

Описание: Удалить дубликаты так, чтобы каждый элемент появлялся не более двух раз.

def removeDuplicates(nums):
    """
    Удаление дубликатов, допуская максимум 2 вхождения
    """
    if len(nums) <= 2:
        return len(nums)
    
    k = 2  # Индекс для записи
    
    for i in range(2, len(nums)):
        # Если текущий элемент не равен двум предыдущим
        if nums[i] != nums[k-2]:
            nums[k] = nums[i]
            k += 1
    
    return k

5. Majority Element

Описание: Найти элемент, который встречается более ⌊n/2⌋ раз (алгоритм Бойера-Мура).

def majorityElement(nums):
    """
    Поиск элемента, встречающегося более n/2 раз
    Алгоритм Бойера-Мура (голосование)
    """
    candidate = None
    count = 0
    
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    return candidate

6. Rotate Array

Описание: Циклически сдвинуть массив на k позиций вправо.

def rotate(nums, k):
    """
    Циклический сдвиг массива вправо на k позиций
    """
    n = len(nums)
    k = k % n  # На случай если k > n
    
    # Переворачиваем весь массив
    nums.reverse()
    
    # Переворачиваем первые k элементов
    nums[:k] = reversed(nums[:k])
    
    # Переворачиваем оставшиеся элементы
    nums[k:] = reversed(nums[k:])

7. Best Time to Buy and Sell Stock

Описание: Найти максимальную прибыль от одной покупки и продажи акций.

def maxProfit(prices):
    """
    Максимальная прибыль от одной сделки
    """
    if not prices:
        return 0
    
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        # Обновляем минимальную цену
        if price < min_price:
            min_price = price
        # Считаем возможную прибыль
        profit = price - min_price
        if profit > max_profit:
            max_profit = profit
    
    return max_profit

8. Best Time to Buy and Sell Stock II

Описание: Максимальная прибыль при множественных покупках/продажах.

def maxProfit(prices):
    """
    Максимальная прибыль при неограниченном числе сделок
    """
    profit = 0
    
    for i in range(1, len(prices)):
        # Покупаем и продаем на каждом росте
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    
    return profit

9. Jump Game

Описание: Определить, можно ли добраться до последнего индекса массива.

def canJump(nums):
    """
    Проверка возможности достичь последнего элемента
    """
    max_reach = 0  # Максимальный индекс, который можем достичь
    
    for i, num in enumerate(nums):
        # Если текущая позиция недостижима
        if i > max_reach:
            return False
        
        # Обновляем максимальную достижимую позицию
        max_reach = max(max_reach, i + num)
        
        # Если можем достичь конца
        if max_reach >= len(nums) - 1:
            return True
    
    return max_reach >= len(nums) - 1

10. Jump Game II

Описание: Найти минимальное количество прыжков до последнего индекса.

def jump(nums):
    """
    Минимальное количество прыжков до конца
    """
    if len(nums) <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(len(nums) - 1):
        # Обновляем максимальную достижимую позицию
        farthest = max(farthest, i + nums[i])
        
        # Если дошли до конца текущего прыжка
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # Если можем достичь конца
            if current_end >= len(nums) - 1:
                break
    
    return jumps

11. H-Index

Описание: Вычислить h-индекс исследователя на основе количества цитирований.

def hIndex(citations):
    """
    Вычисление h-индекса
    h-индекс: h статей имеют как минимум h цитирований каждая
    """
    n = len(citations)
    # Массив для подсчета количества статей с i цитированиями
    counts = [0] * (n + 1)
    
    for c in citations:
        if c >= n:
            counts[n] += 1
        else:
            counts[c] += 1
    
    # Идем с конца и находим h-индекс
    total = 0
    for i in range(n, -1, -1):
        total += counts[i]
        if total >= i:
            return i
    
    return 0

12. Insert Delete GetRandom O(1)

Описание: Реализовать структуру данных с операциями за O(1).

import random

class RandomizedSet:
    def __init__(self):
        self.nums = []  # Массив для хранения элементов
        self.val_to_index = {}  # Словарь: значение -> индекс в массиве

    def insert(self, val: int) -> bool:
        if val in self.val_to_index:
            return False
        
        # Добавляем в конец массива
        self.val_to_index[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        
        # Меняем удаляемый элемент с последним
        last_val = self.nums[-1]
        idx = self.val_to_index[val]
        
        self.nums[idx] = last_val
        self.val_to_index[last_val] = idx
        
        # Удаляем последний элемент
        self.nums.pop()
        del self.val_to_index[val]
        
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)

13. Product of Array Except Self

Описание: Вернуть массив, где каждый элемент - произведение всех элементов, кроме себя.

def productExceptSelf(nums):
    """
    Произведение всех элементов, кроме текущего
    Без использования деления
    """
    n = len(nums)
    result = [1] * n
    
    # Произведение слева от элемента
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]
    
    # Произведение справа от элемента
    right_product = 1
    for i in range(n-1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]
    
    return result

14. Gas Station

Описание: Найти стартовую точку для кругосветного путешествия.

def canCompleteCircuit(gas, cost):
    """
    Поиск начальной точки для завершения круга
    """
    total_gas = 0
    total_cost = 0
    current_gas = 0
    start_index = 0
    
    for i in range(len(gas)):
        total_gas += gas[i]
        total_cost += cost[i]
        
        current_gas += gas[i] - cost[i]
        
        # Если не можем добраться до следующей станции
        if current_gas < 0:
            start_index = i + 1  # Пробуем начать со следующей
            current_gas = 0
    
    # Если общее количество бензина >= общему расходу
    if total_gas >= total_cost:
        return start_index
    else:
        return -1

15. Candy

Описание: Распределить конфеты детям по рейтингу с минимальным количеством.

def candy(ratings):
    """
    Распределение минимального количества конфет
    """
    n = len(ratings)
    candies = [1] * n  # Каждому ребенку минимум 1 конфета
    
    # Слева направо
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    
    # Справа налево
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
    
    return sum(candies)

16. Trapping Rain Water

Описание: Вычислить, сколько воды может задержаться между столбиками.

def trap(height):
    """
    Вычисление объема задержанной воды
    """
    if not height:
        return 0
    
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    
    # Максимальная высота слева для каждого индекса
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])
    
    # Максимальная высота справа для каждого индекса
    right_max[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])
    
    # Вычисляем объем воды для каждого столбика
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    
    return water

17. Roman to Integer

Описание: Преобразовать римское число в целое.

def romanToInt(s):
    """
    Преобразование римского числа в целое
    """
    roman_map = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }
    
    total = 0
    prev_value = 0
    
    # Идем с конца для правильной обработки вычитания
    for char in reversed(s):
        current_value = roman_map[char]
        
        if current_value < prev_value:
            total -= current_value
        else:
            total += current_value
        
        prev_value = current_value
    
    return total

18. Integer to Roman

Описание: Преобразовать целое число в римское.

def intToRoman(num):
    """
    Преобразование целого числа в римское
    """
    # Список значений и соответствующих римских символов
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    
    result = ""
    
    for i in range(len(values)):
        # Добавляем символы, пока число больше значения
        while num >= values[i]:
            result += symbols[i]
            num -= values[i]
    
    return result

19. Length of Last Word

Описание: Найти длину последнего слова в строке.

def lengthOfLastWord(s):
    """
    Длина последнего слова в строке
    """
    # Удаляем пробелы с конца
    s = s.rstrip()
    
    # Ищем последний пробел
    last_space = s.rfind(' ')
    
    if last_space == -1:
        return len(s)
    else:
        return len(s) - last_space - 1

20. Longest Common Prefix

Описание: Найти самый длинный общий префикс среди строк.

def longestCommonPrefix(strs):
    """
    Поиск самого длинного общего префикса
    """
    if not strs:
        return ""
    
    # Берем первую строку как образец
    prefix = strs[0]
    
    for string in strs[1:]:
        # Сокращаем префикс до совпадения
        while not string.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    
    return prefix

21. Reverse Words in a String

Описание: Перевернуть порядок слов в строке.

def reverseWords(s):
    """
    Переворот порядка слов в строке
    """
    # Удаляем лишние пробелы и разделяем на слова
    words = s.strip().split()
    
    # Переворачиваем и объединяем
    return ' '.join(reversed(words))

22. Zigzag Conversion

Описание: Преобразовать строку в зигзагообразный шаблон.

def convert(s, numRows):
    """
    Преобразование строки в зигзагообразный шаблон
    """
    if numRows == 1 or numRows >= len(s):
        return s
    
    # Создаем строки для каждой строки зигзага
    rows = [''] * numRows
    current_row = 0
    going_down = False
    
    for char in s:
        rows[current_row] += char
        
        # Меняем направление в начале и конце
        if current_row == 0 or current_row == numRows - 1:
            going_down = not going_down
        
        # Перемещаемся по строкам
        current_row += 1 if going_down else -1
    
    # Объединяем все строки
    return ''.join(rows)

23. Find the Index of the First Occurrence in a String

Описание: Найти первое вхождение подстроки (аналог str.find()).

def strStr(haystack, needle):
    """
    Поиск первого вхождения подстроки
    """
    if not needle:
        return 0
    
    n, m = len(haystack), len(needle)
    
    for i in range(n - m + 1):
        if haystack[i:i+m] == needle:
            return i
    
    return -1

24. Text Justification

Описание: Выровнять текст по ширине.

def fullJustify(words, maxWidth):
    """
    Выравнивание текста по ширине
    """
    result = []
    current_line = []
    current_length = 0
    
    for word in words:
        # Проверяем, поместится ли слово в текущую строку
        if current_length + len(word) + len(current_line) > maxWidth:
            # Распределяем пробелы для текущей строки
            for i in range(maxWidth - current_length):
                current_line[i % (len(current_line) - 1 or 1)] += ' '
            
            result.append(''.join(current_line))
            current_line = []
            current_length = 0
        
        current_line.append(word)
        current_length += len(word)
    
    # Последняя строка - выравнивание по левому краю
    last_line = ' '.join(current_line)
    last_line += ' ' * (maxWidth - len(last_line))
    result.append(last_line)
    
    return result

25. Valid Palindrome

Описание: Проверить, является ли строка палиндромом (игнорируя регистр и не-буквы).

def isPalindrome(s):
    """
    Проверка, является ли строка палиндромом
    """
    # Очищаем строку: оставляем только буквы и цифры, приводим к нижнему регистру
    cleaned = ''.join(char.lower() for char in s if char.isalnum())
    
    # Проверяем палиндром
    return cleaned == cleaned[::-1]

26. Is Subsequence

Описание: Проверить, является ли s подпоследовательностью t.

def isSubsequence(s, t):
    """
    Проверка, является ли s подпоследовательностью t
    """
    i = j = 0
    
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    
    return i == len(s)

27. Two Sum II - Input Array Is Sorted

Описание: Найти два числа в отсортированном массиве, дающих в сумме target.

def twoSum(numbers, target):
    """
    Поиск двух чисел в отсортированном массиве
    """
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left + 1, right + 1]  # Индексы 1-based
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

28. Container With Most Water

Описание: Найти контейнер с максимальной площадью воды.

def maxArea(height):
    """
    Максимальная площадь контейнера с водой
    """
    max_area = 0
    left, right = 0, len(height) - 1
    
    while left < right:
        # Высота контейнера - минимум из двух сторон
        h = min(height[left], height[right])
        # Ширина контейнера
        w = right - left
        # Площадь
        area = h * w
        
        max_area = max(max_area, area)
        
        # Двигаем указатель с меньшей высотой
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

29. 3Sum

Описание: Найти все уникальные тройки чисел, сумма которых равна 0.

def threeSum(nums):
    """
    Поиск всех уникальных троек с суммой 0
    """
    nums.sort()  # Сортируем для использования двух указателей
    result = []
    
    for i in range(len(nums) - 2):
        # Пропускаем дубликаты
        if i > 0 and nums[i] == nums[i-1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum == 0:
                result.append([nums[i], nums[left], nums[right]])
                
                # Пропускаем дубликаты для left и right
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            
            elif current_sum < 0:
                left += 1
            else:
                right -= 1
    
    return result

30. Minimum Size Subarray Sum

Описание: Найти минимальную длину подмассива с суммой ≥ target.

def minSubArrayLen(target, nums):
    """
    Минимальная длина подмассива с суммой >= target
    """
    min_length = float('inf')
    current_sum = 0
    left = 0
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        # Сжимаем окно слева, пока сумма >= target
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0