Задача: 1030. Matrix Cells in Distance Order
Сложность: easy

Вам даны четыре целых числа row, cols, rCenter и cCenter. Имеется матрица rows x cols, и вы находитесь на ячейке с координатами (rCenter, cCenter). Верните координаты всех ячеек в матрице, отсортированные по их расстоянию от (rCenter, cCenter) от наименьшего расстояния до наибольшего. Вы можете вернуть ответ в любом порядке, удовлетворяющем этому условию. Расстояние между двумя ячейками (r1, c1) и (r2, c2) равно |r1 - r2| + |c1 - c2|.

Пример:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]

👨‍💻 Алгоритм:

1⃣Инициализация и вычисление расстояний:
Создайте список для хранения всех координат ячеек в матрице.
Вычислите расстояние Манхэттена от каждой ячейки до центра и добавьте пару (расстояние, координаты) в список.

2⃣Сортировка списка:
Отсортируйте список по расстоянию в порядке возрастания.

3⃣Извлечение координат:
Извлеките координаты из отсортированного списка и верните их.

😎 Решение:

def allCellsDistOrder(rows, cols, rCenter, cCenter):
    cells = []
    
    for r in range(rows):
        for c in range(cols):
            distance = abs(r - rCenter) + abs(c - cCenter)
            cells.append((distance, r, c))
    
    cells.sort()
    
    return [(r, c) for _, r, c in cells]

Ставь 👍 и забирай 📚 Базу знаний

Задача: 325. Maximum Size Subarray Sum Equals k
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.

Пример:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

👨‍💻 Алгоритм:

1⃣Инициализация переменных
Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов.

2⃣Итерация по массиву
На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i.

3⃣Возврат результата
Верните значение longestSubarray.

😎 Решение:

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        prefixSum = 0
        longestSubarray = 0
        indices = {}
        
        for i, num in enumerate(nums):
            prefixSum += num
            
            if prefixSum == k:
                longestSubarray = i + 1
            if prefixSum - k in indices:
                longestSubarray = max(longestSubarray, i - indices[prefixSum - k])
            if prefixSum not in indices:
                indices[prefixSum] = i
        
        return longestSubarray

Ставь 👍 и забирай 📚 Базу знаний

👩‍💻 Стажировки и вакансии для Python разработчиков.

- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram

👉 @jobs_python

Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.

Задача: 630. Course Schedule III
Сложность: hard

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3

👨‍💻 Алгоритм:

1⃣Сортировка курсов
Отсортируйте курсы по их конечным датам (lastDay). Это позволяет проходить курсы как можно ближе к их крайним срокам.

2⃣Проход по курсам
Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов.

3⃣Добавление и удаление курсов
Для каждого курса: Добавьте его продолжительность в приоритетную очередь и обновите общее время прохождения курсов. Если общее время превышает крайний срок текущего курса, удалите самый длительный курс из очереди и скорректируйте общее время.

😎 Решение:

import heapq

def scheduleCourse(courses):
    courses.sort(key=lambda x: x[1])
    total_time = 0
    max_heap = []

    for duration, last_day in courses:
        heapq.heappush(max_heap, -duration)
        total_time += duration

        if total_time > last_day:
            total_time += heapq.heappop(max_heap)

    return len(max_heap)

Ставь 👍 и забирай 📚 Базу знаний