Python | LeetCode

#medium Задача: 79. Word Search Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке. Слово можно составить из букв последовательно смежных ячеек, где смежные ячейки находятся рядом по горизонтали или вертикали. Одна и та же ячейка с буквой не может быть использована более одного раза. Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

👨‍💻 Алгоритм: 1️⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки. 2️⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова. 3️⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования. 😎 Решение:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.ROWS = len(board)
        self.COLS = len(board[0])
        self.board = board

        for row in range(self.ROWS):
            for col in range(self.COLS):
                if self.backtrack(row, col, word):
                    return True
        return False

    def backtrack(self, row: int, col: int, suffix: str) -> bool:
        if len(suffix) == 0:
            return True

        if (row < 0 or row == self.ROWS or col < 0 or col == self.COLS or self.board[row][col] != suffix[0]):
            return False

        ret = False
        self.board[row][col] = "#"
        for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])
            if ret:
                break

        self.board[row][col] = suffix[0]
        return ret

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#medium Задача: 78. Subsets Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор). Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке. Пример:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

👨‍💻 Алгоритм: 1️⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов. 2️⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод. 3️⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr. 😎 Решение:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first=0, curr=[]):
            if len(curr) == k:
                output.append(curr[:])
                return
            for i in range(first, n):
                curr.append(nums[i])
                backtrack(i + 1, curr)
                curr.pop()

        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Доставка от 30 минут из кафе и ресторанов в Яндекс Еде Заказывайте без очередей в приложении или на сайте. Скидки и акции каждый день 👍 Попробовать #реклама 16+ plms.adj.st О рекламодателе

#medium Задача: 77. Combinations Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Ответ можно вернуть в любом порядке. Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

👨‍💻 Алгоритм: 1️⃣Инициализировать массив ответов ans и массив для построения комбинаций curr. 2️⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum: Если длина curr равна k, добавить копию curr в ans и вернуться. Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле. Итерировать num от firstNum до firstNum + available включительно. Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr. 3️⃣Вызвать backtrack с изначально пустым curr и firstNum = 1. Вернуть ans. 😎 Решение:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(curr, first_num):
            if len(curr) == k:
                ans.append(curr[:])
                return

            need = k - len(curr)
            remain = n - first_num + 1
            available = remain - need

            for num in range(first_num, first_num + available + 1):
                curr.append(num)
                backtrack(curr, num + 1)
                curr.pop()

        ans = []
        backtrack([], 1)
        return ans

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

#hard Задача: 76. Minimum Window Substring Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "". Тестовые примеры будут сформированы таким образом, что ответ будет уникальным. Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

👨‍💻 Алгоритм: 1️⃣Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S. 2️⃣Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T. 3️⃣Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее. 😎 Решение:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        dict_t = Counter(t)
        required = len(dict_t)
        l, r = 0, 0
        formed = 0
        window_counts = {}
        ans = float("inf"), None, None

        while r < len(s):
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            while l <= r and formed == required:
                character = s[l]
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1

                l += 1

            r += 1
        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 75. Sort Colors Дан массив nums, содержащий n объектов, окрашенных в красный, белый или синий цвет. Отсортируйте их на месте так, чтобы объекты одного цвета находились рядом, а цвета располагались в порядке красный, белый и синий. Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно. Вы должны решить эту задачу без использования функции сортировки библиотеки. Пример:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

👨‍💻 Алгоритм: 1️⃣Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0. 2️⃣Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2. 3️⃣Инициализация индекса текущего элемента для рассмотрения: curr = 0. Пока curr <= p2: Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо. Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево. Если nums[curr] = 1: сдвинуть указатель curr вправо. 😎 Решение:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0 = curr = 0
        p2 = len(nums) - 1

        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

🔵 Практический интенсив «Python-разработчик: основы за 2 дня» — 16-17 июля в 19:00 мск. О перспективах направления Python и многом другом расскажет Грегори Салиба, старший разработчик ЭквантаЛаб с опытом в разработке более 3 лет.  На вебинаре вы: ☑️ Самостоятельно напишете Telegram-бота с карточными мини-играми. ☑️ Познакомитесь с синтаксисом языка и сферами его применения. ☑️ Поймете как продолжить обучение, какие навыки потребуются, чтобы стать backend-разработчиком на Python. ☑️ Узнаете, чего ждут работодатели от junior-разработчиков и что делать, чтобы найти работу без опыта. 🎁 Приятные бонусы: полезный гайд для начинающего Python-разработчика и гайд о сленге в IT всем участникам интенсива!

#medium Задача: 74. Search a 2D Matrix Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами: Каждая строка отсортирована в порядке неубывания. Первое число каждой строки больше последнего числа предыдущей строки. Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае. Вы должны написать решение с временной сложностью O(log(m * n)). Пример:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

👨‍💻 Алгоритм: 1️⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1. 2️⃣Пока left <= right: Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2. 3️⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части. Сравните pivot_element и target, чтобы определить, в какой части нужно искать target. 😎 Решение:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])

        left, right = 0, m * n - 1
        while left <= right:
            pivot_idx = (left + right) // 2
            pivot_element = matrix[pivot_idx // n][pivot_idx % n]
            if target == pivot_element:
                return True
            else:
                if target < pivot_element:
                    right = pivot_idx - 1
                else:
                    left = pivot_idx + 1
        return False

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 73. Set Matrix Zeroes Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца. Необходимо выполнить это действие на месте, не используя дополнительное пространство для другой матрицы. Пример:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

👨‍💻 Алгоритм: 1️⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0. 2️⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки. 3️⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми. 😎 Решение:

class Solution(object):
    def setZeroes(self, matrix: List[List[int]]) -> None:
        is_col = False
        R = len(matrix)
        C = len(matrix[0])
        for i in range(R):
            if matrix[i][0] == 0:
                is_col = True
            for j in range(1, C):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        for i in range(1, R):
            for j in range(1, C):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0

        if matrix[0][0] == 0:
            for j in range(C):
                matrix[0][j] = 0

        if is_col:
            for i in range(R):
                matrix[i][0] = 0

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Все надоело и пропал интерес, чувствуешь себя амебой и хочется только залипать в телефоне. Бывает? Психолог взрослого человека - канал для айтишников, у которых периодически опускаются руки и отключается мозг, ибо переработки и постоянная тревожность не приводят к другим исходам. ▪️ Как научиться отвлекаться от работы и отдыхать? ▪️ Как совместить кучу рабочих задач и время с семьей? ▪️ Как справиться с прокрастинацией? ▪️ Как не растерять запал, даже если начальник и коллеги 💩 и кажется, что ничего не выходит? Подписывайтесь на канал @vadimpetrov_psy и научитесь работать без упахивания, выгорания и ущерба для личной жизни! 👨🏻‍💻 Псс. Заходите в закреп канала - там много полезного.

#medium Задача: 72. Edit Distance Даны два слова word1 и word2. Верните минимальное количество операций, необходимых для преобразования word1 в word2. Доступны следующие три операции над словом: Вставить символ. Удалить символ. Заменить символ. Пример:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

👨‍💻 Алгоритм: 1️⃣Подход динамического программирования с верху вниз реализуется путем добавления кэширования в рекурсивные вызовы функций. Например, в рекурсивном вызове будут следующие параметры: word1 = abc, word2 = ad, word1Index = 2 (с индексацией от нуля) и word2Index = 1 (с индексацией от нуля). 2️⃣Для кэширования результата данной подзадачи необходимо использовать структуру данных, которая хранит результат для word1, заканчивающегося на индексе word1Index, то есть 2, и word2, заканчивающегося на word2Index, то есть 1. Один из возможных способов реализации - использование двумерного массива, например, memo, где memo[word1Index][word2Index] кэширует результат для word1, заканчивающегося на word1Index, и word2, заканчивающегося на word2Index. 3️⃣Индексы word1Index и word2Index указывают на текущие символы строк word1 и word2 соответственно. Алгоритм реализуется по следующей схеме: перед вычислением результата подзадачи проверяется, не сохранен ли он уже в memo[word1Index][word2Index]. Если да, то возвращается сохраненный результат. После вычисления результата каждой подзадачи результат сохраняется в memo для будущего использования. 😎 Решение:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        memo = [
            [None for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)
        ]

        def minDistanceRecur(word1, word2, word1Index, word2Index):
            if word1Index == 0:
                return word2Index
            if word2Index == 0:
                return word1Index
            if memo[word1Index][word2Index] is not None:
                return memo[word1Index][word2Index]
            if word1[word1Index - 1] == word2[word2Index - 1]:
                minEditDistance = minDistanceRecur(
                    word1, word2, word1Index - 1, word2Index - 1
                )
            else:
                insertOperation = minDistanceRecur(
                    word1, word2, word1Index, word2Index - 1
                )
                deleteOperation = minDistanceRecur(
                    word1, word2, word1Index - 1, word2Index
                )
                replaceOperation = minDistanceRecur(
                    word1, word2, word1Index - 1, word2Index - 1
                )
                minEditDistance = (
                    min(insertOperation, deleteOperation, replaceOperation) + 1
                )
            memo[word1Index][word2Index] = minEditDistance
            return minEditDistance

        return minDistanceRecur(word1, word2, len(word1), len(word2))

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Канал приближается к 20к подписчиков, а здесь так и нет нормального контент плана 😒 Ищу талантливых журналистов, способных писать клевые и авторские посты на тему "Карьера в IT" и все что с этим связано: поиск работы, повышение з/п, разбор кейсов, переезд в другие страны по рабочим визам, аналитика, исследование рынка и т.д. Важно глубокое понимание IT индустрии, вы должны иметь опыт работы в ней Если интересно отправьте мне свое резюме @kivaiko

#medium Задача: 71. Simplify Path Дан абсолютный путь для файловой системы в стиле Unix, который начинается с символа '/'. Преобразуйте этот путь в его упрощенный канонический путь. В контексте файловой системы Unix-style одинарная точка '.' обозначает текущий каталог, двойная точка '..' означает переход на один уровень каталога вверх, а несколько слэшей, таких как '//', интерпретируются как один слэш. В этой задаче последовательности точек, не охваченные предыдущими правилами (например, '...'), следует рассматривать как допустимые имена для файлов или каталогов. Упрощенный канонический путь должен соответствовать следующим правилам: Он должен начинаться с одного слэша '/'. Каталоги в пути должны быть разделены только одним слэшем '/'. Он не должен заканчиваться слэшем '/', если только это не корневой каталог. Он должен исключать любые одинарные или двойные точки, используемые для обозначения текущих или родительских каталогов. Верните новый путь. Пример:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

👨‍💻 Алгоритм: 1️⃣Инициализируем стек S, который будет использоваться в нашей реализации. Разделяем входную строку, используя символ '/' в качестве разделителя. Этот шаг очень важен, поскольку входные данные всегда являются допустимым путем, и наша задача — лишь его сократить. Таким образом, все, что находится между двумя символами '/', является либо именем каталога, либо специальным символом, и мы должны соответственно обработать их. 2️⃣Как только входной путь разделен, мы обрабатываем каждый компонент по отдельности. Если текущий компонент — это точка '.' или пустая строка, мы ничего не делаем и просто продолжаем. Если вспомнить, массив строк, полученный при разделении строки '/a//b', будет [a, , b], где между a и b находится пустая строка, что в контексте общего пути не имеет значения. Если мы сталкиваемся с двойной точкой '..', это означает, что нужно подняться на один уровень выше в текущем пути каталога. Поэтому мы удаляем запись из нашего стека, если он не пуст. 3️⃣Наконец, если обрабатываемый нами в данный момент компонент не является одним из специальных символов, мы просто добавляем его в наш стек, так как это законное имя каталога. Как только все компоненты обработаны, нам просто нужно соединить все имена каталогов в нашем стеке, используя '/' в качестве разделителя, и мы получим самый короткий путь, который приведет нас в тот же каталог, что и предоставленный на входе. 😎 Решение:

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for portion in path.split("/"):
            if portion == "..":
                if stack:
                    stack.pop()
            elif portion == "." or not portion:
                continue
            else:
                stack.append(portion)
        
        final_str = "/" + "/".join(stack)
        return final_str

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Почему тебя не зовут на интервью? Исправь это в своем резюме… Получить приглашение на интервью сейчас сложнее, чем с нуля обучиться разработке. И к сожалению, это не шутка. Скорее всего только 1-2% работодателей сейчас позовут тебя на интервью. Это статистика, которую мы собирали по 10.000 откликам. Но над этой цифрой можно и нужно работать. Если правильно оформить свое резюме, и поменять свою стратегию с откликами, то конверсию можно увеличить до 10%. Т.е почти в 10 раз! Как это сделать? 1. Проверить свое резюме по нашему чек листу, и внести в него то, чего будет не хватать. 2. Поменять свой подход к поиску работы, ведь одними откликами на hh.ru сыт не будешь. 16 июля, в 18:00 по москве, мы вместе с Максом из CodeReview проведем вебинар на тему эффективного поиска работы в 2024 году. На нем Макс покажет как сейчас нужно искать работу. В прямом эфире. А также раскроет что именно нужно писать в свое резюме, чтобы оно ПРОДАВАЛО. Получить чек лист по составлению резюме, а также зарегистрироваться на вебинар можно по этой ссылке. Регистрируйся сейчас и увидимся 16 июля, в 18:00 по мск. 👉 Зарегистрироваться и получить чек-лист по резюме.

#easy Задача: 70. Climbing Stairs Ты поднимаешься по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек. Каждый раз ты можешь подняться на 1 или 2 ступеньки. Сколькими различными способами ты можешь добраться до вершины? Пример:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

👨‍💻 Алгоритм: 1️⃣В этом методе грубой силы мы рассматриваем все возможные комбинации шагов, то есть 1 и 2, на каждом шаге. 2️⃣На каждом шаге мы вызываем функцию climbStairs для шага 1 и шага 2, и возвращаем сумму возвращаемых значений обеих функций. 3️⃣Формула вызова функции: climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n), где i определяет текущий шаг, а n — целевой шаг. 😎 Решение:

class Solution:
    def climbStairs(self, n: int) -> int:
        return self.climb_Stairs(0, n)

    def climb_Stairs(self, i: int, n: int) -> int:
        if i > n:
            return 0
        if i == n:
            return 1
        return self.climb_Stairs(i + 1, n) + self.climb_Stairs(i + 2, n)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

👩‍💻 Программирование теперь в телеграм! Вот обширная база материалов, которая ежедневно обновляется, выбирай своё направление: Обучение Python с нуля Обучение JavaScript с нуля Обучение HTML/CSS с нуля Обучение Java с нуля Обучение C/С++ с нуля Обучение С# с нуля Обучение SQL/GO/PHP с нуля Обучение Kotlin/Swift с нуля ⛓ Архив на 1789ГБ: Курсы, книги, шпаргалки, статьи, видео ресурсы — всё собрано в одном месте: @roadmap_ready

#easy Задача: 69. Sqrt(x) Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным. Вы не должны использовать встроенные функции или операторы для возведения в степень. Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python. Пример:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

👨‍💻 Алгоритм: 1️⃣Если x < 2, верните x. Установите левую границу left = 2 и правую границу right = x / 2. 2️⃣Пока left ≤ right: Возьмите num = (left + right) / 2 в качестве предположения. Вычислите num × num и сравните его с x: Если num × num > x, переместите правую границу right = pivot − 1. В противном случае, если num × num < x, переместите левую границу left = pivot + 1. В противном случае num × num == x, целочисленный квадратный корень найден, давайте вернем его. 3️⃣Верните right. 😎 Решение:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        left, right = 2, x // 2

        while left <= right:
            pivot = left + (right - left) // 2
            num = pivot * pivot
            if num > x:
                right = pivot - 1
            elif num < x:
                left = pivot + 1
            else:
                return pivot

        return right

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Привет! Ты сейчас ищешь работу? Если да, то у меня для тебя классные новости. Мы с Максом решили провести вебинар на тему поиска работы и того, как быстрее получить оффер. Зачем? Да потому что найти работу просто откликаясь на вакансии теперь практически нереально. На Junior вакансии откликаются по 1500 кандидатов. 1500 человек, Карл... Вопрос: Как искать работу в таких условиях? Ответ: Нужно менять подходы, и использовать новые способы поиска работы. А вот какие способы, и как искать работу в 2024 году, расскажет мой товарищ - Макс, который помогает разработчикам с трудоустройством. Он расскажет тебе как ПРАВИЛЬНО откликаться на вакансии, на что смотрят рекрутеры, и как ты должен быть упакован, чтобы получить работу в это непростое время. 🗓 Когда? Во вторник – 16 июля, в 18:00 по мск. 🎁 После регистрации он также обещал прислать: 1) Анализ рынка труда. 2) Разбор кейсов тех, кто сейчас находит работу. 3) Пошаговый план, что нужно делать, чтобы прийти к оферу. 👉 Записаться на вебинар по поиску работы.