6. Стек и сортировки

Задачи

Стек (скобки)

• 20. Valid Parentheses #баян #домклик РЕШЕНИЕ

• Balanced Parantheses! РЕШЕНИЕ

• 1249. Minimum Remove to Make Valid Parentheses РЕШЕНИЕ

Стек

• 739. Daily Temperatures #яндекс РЕШЕНИЕ

Сортировки

• Bubble sort (тут лимит по времени на 10 тесте поймаеете)

• Merge Sort РЕШЕНИЕ

• Quick sort РЕШЕНИЕ

Доп. вопросы

• Вопрос: Какая временная сложность у quick sort? #авито
  • Ответ: …

• Вопрос: Как отсортировать массив, который не помещается в память? #сбердевайсы

• Вопрос: Когда применять квадратичные сортировки на практике? #отменя
  • Когда размер массива не большой (32 или меньше)

  • Когда не хочется тратить дополнительную память вообще

  • Когда рекурсивная сортировка тратит слишком много стек фреймов (например, можно в merge sort если меньше 32 элементов делать bubble sort)

Самому прорешать для закрепления

Задачи

• 1475. Final Prices With a Special Discount in a Shop

• 151. Reverse Words in a String

Теория

Сортировка пузырьком без оптимизаций

class Solution:
    # Bubble sort
    # time:      O(n * n)
    # mem (доп): O(1)
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            for j in range(len(nums) - 1):
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
        return nums

Сортировка пузырьком с оптимизациями

class Solution:
    # Bubble sort
    # time:      O(n * n)
    # mem (доп): O(1)
    def sortArray(self, nums: List[int]) -> List[int]:
        swapCount = -1
        i = 0
        while swapCount != 0:
            swapCount = 0
            for j in range(len(nums) - i - 1):
                if nums[j] > nums[j + 1]:
                    swapCount += 1
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
            i += 1
        return nums

После курса

Задачи

• 907. Sum of Subarray Minimums #авито(?) #hard