PHP | LeetCode

Задача: 389. Find the Difference
Сложность: easy

Даны две строки s и t.
Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.
Верните букву, которая была добавлена в t.

Пример:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

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

1⃣Отсортируйте строки s и t.

2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s.

3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время.

😎 Решение:

var findTheDifference = function(s, t) {
    let sortedS = s.split('').sort();
    let sortedT = t.split('').sort();

    for (let i = 0; i < sortedS.length; i++) {
        if (sortedS[i] !== sortedT[i]) {
            return sortedT[i];
        }
    }

    return sortedT[sortedS.length];
};

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

Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium

Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.

Пример:

Input: preorder = [5,2,1,3,6]
Output: true

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

1⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек.

2⃣Итерируйте по массиву preorder. Для каждого num:
Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit.
Если num <= minLimit, верните false.
Добавьте num в стек.

3⃣Верните true, если удалось пройти весь массив.

😎 Решение:

class Solution {
    function verifyPreorder($preorder) {
        $minLimit = -PHP_INT_MAX;
        $stack = [];
        
        foreach ($preorder as $num) {
            while (!empty($stack) && end($stack) < $num) {
                $minLimit = array_pop($stack);
            }
            
            if ($num <= $minLimit) {
                return false;
            }
            
            $stack[] = $num;
        }
        
        return true;
    }
}

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

Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

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

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords.

😎 Решение:

class Solution {
    private function storeFirstOptions($s, $startPos, &$firstOptions) {
        if ($s[$startPos] != '{') {
            $firstOptions[] = $s[$startPos];
        } else {
            $startPos++;
            while ($s[$startPos] != '}') {
                if ($s[$startPos] >= 'a' && $s[$startPos] <= 'z') {
                    $firstOptions[] = $s[$startPos];
                }
                $startPos++;
            }
            sort($firstOptions);
        }
        return $startPos + 1;
    }

    private function findAllWords($s, $startPos) {
        if ($startPos == strlen($s)) {
            return [""];
        }

        $firstOptions = [];
        $remStringStartPos = $this->storeFirstOptions($s, $startPos, $firstOptions);
        $wordsWithRemString = $this->findAllWords($s, $remStringStartPos);

        $expandedWords = [];
        foreach ($firstOptions as $c) {
            foreach ($wordsWithRemString as $word) {
                $expandedWords[] = $c . $word;
            }
        }
        return $expandedWords;
    }

    public function expand($s) {
        return $this->findAllWords($s, 0);
    }
}

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

Задача: 83. Remove Duplicates from Sorted List
Сложность: easy

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

Пример:

Input: head = [1,1,2]
Output: [1,2]

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

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

2⃣Если узел является дубликатом, мы изменяем указатель next текущего узла так, чтобы он пропускал следующий узел и напрямую указывал на узел, следующий за следующим.

3⃣Это позволяет исключить дубликаты из списка, продвигаясь вперёд по списку и корректируя связи между узлами для сохранения только уникальных элементов.

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function deleteDuplicates($head) {
    $current = $head;
    while ($current !== null && $current->next !== null) {
        if ($current->next->val === $current->val) {
            $current->next = $current->next->next;
        } else {
            $current = $current->next;
        }
    }
    return $head;
}

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

Задача: 1279. Traffic Light Controlled Intersection
Сложность: easy

Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.
Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.
direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.

Пример:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]

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

1⃣Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar.

2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar.

3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков.

😎 Решение:

class TrafficLight {
    private $greenRoad = 1;
    private $lock;

    public function __construct() {
        $this->lock = new \stdClass();
    }

    public function carArrived($carId, $roadId, $direction, $turnGreen, $crossCar) {
        synchronized($this->lock, function() use ($roadId, $turnGreen, $crossCar) {
            if ($this->greenRoad !== $roadId) {
                $turnGreen();
                $this->greenRoad = $roadId;
            }
            $crossCar();
        });
    }
}

function synchronized($lock, $callback) {
    $fp = fopen($lock, "r+");
    if (flock($fp, LOCK_EX)) {
        try {
            $callback();
        } finally {
            flock($fp, LOCK_UN);
        }
    }
    fclose($fp);
}

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

Задача: 1002. Find Common Characters
Сложность: easy

Если задан массив строк words, верните массив всех символов, которые встречаются во всех строках внутри слов (включая дубликаты). Вы можете вернуть ответ в любом порядке.

Пример:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

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

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

2⃣Обработка каждого слова:
Для каждого слова создайте временный массив для хранения частоты каждого символа в этом слове.
Обновите основной частотный массив, сравнивая его с временным массивом и сохраняя минимальные частоты каждого символа.

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

😎 Решение:

class Solution {
    function commonChars($words) {
        $minFreq = array_fill(0, 26, PHP_INT_MAX);
        
        foreach ($words as $word) {
            $freq = array_fill(0, 26, 0);
            foreach (str_split($word) as $char) {
                $freq[ord($char) - ord('a')]++;
            }
            for ($i = 0; $i < 26; $i++) {
                $minFreq[$i] = min($minFreq[$i], $freq[$i]);
            }
        }
        
        $result = [];
        for ($i = 0; $i < 26; $i++) {
            for ($j = 0; $j < $minFreq[$i]; $j++) {
                $result[] = chr($i + ord('a'));
            }
        }
        return $result;
    }
}

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

Задача: 116. Populating Next Right Pointers in Each Node
Сложность: medium

Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next так, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1⃣Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных.

2⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня заключается в использовании некоторой разграничительной метки между уровнями. Обычно мы вставляем в очередь элемент NULL, который отмечает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого количества памяти, пропорционально количеству уровней в дереве.

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

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Поскольку на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

class Node {
    public $val;
    public $left = null;
    public $right = null;
    public $next = null;

    public function __construct($val) {
        $this->val = $val;
    }
}

class Solution {
    public function connect($root) {
        if ($root === null) {
            return $root;
        }

        $queue = new SplQueue();
        $queue->enqueue($root);

        while (!$queue->isEmpty()) {
            $size = $queue->count();
            for ($i = 0; $i < $size; $i++) {
                $node = $queue->dequeue();
                if ($i < $size - 1) {
                    $node->next = $queue->top();
                }

                if ($node->left !== null) {
                    $queue->enqueue($node->left);
                }
                if ($node->right !== null) {
                    $queue->enqueue($node->right);
                }
            }
        }

        return $root;
    }
}

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

Задача: 668. Kth Smallest Number in Multiplication Table
Сложность: hard

Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1).

Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n.

Пример:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.

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

1⃣Установка границ поиска:
Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n.

2⃣Бинарный поиск:
Используйте бинарный поиск, чтобы найти k-й наименьший элемент.
Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid.

3⃣Проверка количества элементов:
Если количество элементов меньше k, увеличьте нижнюю границу (left).
Если количество элементов больше или равно k, уменьшите верхнюю границу (right).

😎 Решение:

class Solution {
    function findKthNumber($m, $n, $k) {
        $left = 1;
        $right = $m * $n;
        
        while ($left < $right) {
            $mid = intdiv($left + $right, 2);
            if ($this->countLessEqual($m, $n, $mid) < $k) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        
        return $left;
    }
    
    private function countLessEqual($m, $n, $x) {
        $count = 0;
        for ($i = 1; $i <= $m; $i++) {
            $count += min(intdiv($x, $i), $n);
        }
        return $count;
    }
}

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

Задача: 489. Robot Room Cleaner
Сложность: hard

Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка.
Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot.
Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов.
Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке.

Разработайте алгоритм для очистки всей комнаты, используя следующие API:

interface Robot {
  // возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
  // возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
  boolean move();

  // Робот останется на той же ячейке после вызова turnLeft/turnRight.
  // Каждый поворот составляет 90 градусов.
  void turnLeft();
  void turnRight();

  // Очистить текущую ячейку.
  void clean();
}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

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

1⃣Пометьте текущую ячейку как посещенную и очистите её.

2⃣Исследуйте четыре направления (вверх, вправо, вниз, влево) последовательно, двигаясь и очищая новые ячейки, если возможно.

3⃣Если движение невозможно (стена или посещенная ячейка), поверните направо и попробуйте снова, возвращаясь назад, если необходимо.

😎 Решение:

class Solution {
    private $robot;
    private $visited;
    private $directions;

    public function __construct() {
        $this->visited = [];
        $this->directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    }

    private function goBack() {
        $this->robot->turnRight();
        $this->robot->turnRight();
        $this->robot->move();
        $this->robot->turnRight();
        $this->robot->turnRight();
    }

    private function backtrack($row, $col, $d) {
        $this->visited["$row,$col"] = true;
        $this->robot->clean();
        for ($i = 0; $i < 4; $i++) {
            $newD = ($d + $i) % 4;
            $newRow = $row + $this->directions[$newD][0];
            $newCol = $col + $this->directions[$newD][1];
            if (!isset($this->visited["$newRow,$newCol"]) && $this->robot->move()) {
                $this->backtrack($newRow, $newCol, $newD);
                $this->goBack();
            }
            $this->robot->turnRight();
        }
    }

    public function cleanRoom($robot) {
        $this->robot = $robot;
        $this->backtrack(0, 0, 0);
    }
}

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

Задача: 925. Long Pressed Name
Сложность: easy

Ваш друг набирает на клавиатуре свое имя. Иногда, при наборе символа c, клавиша может быть долго нажата, и символ будет набран 1 или более раз. Вы исследуете набранные символы клавиатуры. Верните True, если возможно, что это было имя вашего друга, при этом некоторые символы (возможно, ни один) не были долго нажаты.

Пример:

Input: name = "alex", typed = "aaleex"
Output: true

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

1⃣Инициализировать два указателя i и j для строки имени и набранной строки соответственно.

2⃣Пройти по набранной строке:
Если символы имени и набранной строки совпадают, сдвинуть оба указателя.
Если символы не совпадают, проверить, является ли текущий символ набранной строки повторением предыдущего символа. Если да, сдвинуть указатель набранной строки.
Если символ не совпадает и не является повторением предыдущего символа, вернуть False.
После завершения цикла проверить, что все символы имени были обработаны.

3⃣Вернуть True, если все символы имени были обработаны, иначе False.

😎 Решение:

function isLongPressedName($name, $typed) {
    $i = 0;
    $j = 0;
    while ($j < strlen($typed)) {
        if ($i < strlen($name) && $name[$i] == $typed[$j]) {
            $i++;
        } elseif ($j == 0 || $typed[$j] != $typed[$j - 1]) {
            return false;
        }
        $j++;
    }
    return $i == strlen($name);
}

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

Задача: 629. K Inverse Pairs Array
Сложность: hard

Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3, k = 0
Output: 1

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

1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

3⃣Возвращение результата
Результатом будет значение dp[n][k].

😎 Решение:

function kInversePairs($n, $k) {
    $MOD = 1000000007;
    $dp = array_fill(0, $n + 1, array_fill(0, $k + 1, 0));
    $dp[0][0] = 1;

    for ($i = 1; $i <= $n; $i++) {
        $dp[$i][0] = 1;
        for ($j = 1; $j <= $k; $j++) {
            $dp[$i][$j] = ($dp[$i][$j - 1] + $dp[$i - 1][$j]) % $MOD;
            if ($j >= $i) {
                $dp[$i][$j] = ($dp[$i][$j] - $dp[$i - 1][$j - $i] + $MOD) % $MOD;
            }
        }
    }

    return $dp[$n][$k];
}

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

Я смотрю на эту цифру и до сих пор не верю.

Когда я запускал этот проект, мне реально было страшно. Страшно, что ничего не получится. Что я и мой проект никому не нужен. Страшно, что все увидят, как я публично обосрался.

Я ставил планку в 300т рублей. В самом позитивном сценарии 1млн. Но про 5 миллионов… даже мысли не было. Уже в первые часы стало понятно, что кампания идет не по плану. Сайт краудфандинга не выдержал нашей нагрузки и лег 😁

Особенно в последние три дня — просто какой-то разрыв! Я ощущал, как будто ловлю попутный ветер. В последний час не хватало 50к до 5 млн, и я уже думал сам их докинуть, чтобы красиво закрыть 😁

Но финальная сумма это не так важно. Самое главное это как мы её собрали. Это не инвестиции, не чьи-то деньги под условия и контроль, не кредит. Это вы поверили и поддержали меня напрямую. Вы дали мне возможность оставить за собой полный контроль над easyoffer.

Я чувствую огромную ответственность и нервничаю из-за высоких ожиданий. А вдруг что-то пойдёт не так? А вдруг на релизе кому-то что-то не понравится? Именно поэтому я рад, что могу честно выйти на новый этап и без давления от левых инвесторов.

В такие моменты вспоминаю, с чего всё начиналось. Как 2 года назад я писал свои первые посты на 500 человек о том, как учу программирование. Как записывал первое видео на YouTube про поиск работы. Как пилил первую версию easyoffer, вообще без понимания, что из этого выйдет.

И сейчас я думаю — может, эта история вдохновит кого-то из вас. Может, кто-то запустит свой айтишный проект, найдёт поддержку и соберёт бабки на развитие. Было бы круто

Спасибо за невероятную и колосальную поддержку ❤️
О такой аудитории как вы я не мог мечтать

🚨 60 минут до финала

Через час мы закроем краудфандинг easyoffer 2.0
Это последний шанс вписаться в самые выгодные условия.

👉 https://planeta.ru/campaigns/easyoffer

Финальный отсчёт:
3 часа до конца краудфандинга easyoffer 2.0!

Это не просто скидка. Это шанс поддержать проект, который поможет и вам и тысячам айтишников готовиться к собеседованиям быстрее, эффективнее и увереннее.

За последние недели:
💥 Нас поддержали уже больше 1450 человек;
🔥 Вместе собрали больше 4,5 млн. рублей на запуск проекта;

Но сейчас важнее другое.

⏳ Через 3 часа всё закончится.
– Больше не будет подписки за 3 200 руб. на целый год!
– Не будет шанса первыми воспользоваться EasyOffer 2.0 на бета-тестировании

Если вы:

+ Планируете менять работу в этом или следующем году;
+ Хотите иметь под рукой 40,000+ вопросов собеседований с разборами, видео-ответами и тренажёрами;
+ Хотите зафиксировать лучшую цену на целый год… (потом будет в 12 раз дороже)

👉 Тогда просто переходите и поддержите нас сейчас:
https://planeta.ru/campaigns/easyoffer

📢 Три часа — и всё.
Не откладывайте на потом.

Спасибо всем, кто уже с нами! 💙

Задача: 1482. Minimum Number of Days to Make m Bouquets
Сложность: medium

Вам дан массив целых чисел bloomDay, целое число m и целое число k.

Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада.
Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете.

Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -1.

Пример:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

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

1⃣Инициализация:
Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay.
Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день.

2⃣Поиск минимального числа дней:
Выполняйте бинарный поиск, пока start меньше или равен end:
- рассчитайте mid как среднее значение между start и end.
- используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день.
- если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево.
- иначе переместите start вправо.

3⃣Возвращение результата:
Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно.

😎 Решение:

class Solution {
    private function getNumOfBouquets($bloomDay, $mid, $k) {
        $numOfBouquets = 0;
        $count = 0;
        foreach ($bloomDay as $day) {
            if ($day <= $mid) {
                $count++;
            } else {
                $count = 0;
            }
            if ($count == $k) {
                $numOfBouquets++;
                $count = 0;
            }
        }
        return $numOfBouquets;
    }
    
    function minDays($bloomDay, $m, $k) {
        if (count($bloomDay) < $m * $k) return -1;
        $start = 0;
        $end = max($bloomDay);
        $minDays = -1;
        while ($start <= $end) {
            $mid = (int)(($start + $end) / 2);
            if ($this->getNumOfBouquets($bloomDay, $mid, $k) >= $m) {
                $minDays = $mid;
                $end = $mid - 1;
            } else {
                $start = $mid + 1;
            }
        }
        return $minDays;
    }
}

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

⏳ Такого больше не будет!

Всего пара часов и больше не будет возможности получить:

🚀 PRO подписку к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование

👉 Поддержать: https://planeta.ru/campaigns/easyoffer

Задача: 848. Shifting Letters
Сложность: medium

Вам дана строка s из строчных букв английского алфавита и целочисленный массив shifts такой же длины.

Назовем shift() буквы следующей буквой в алфавите (с переходом так, что 'z' становится 'a').
Например, shift('a') = 'b', shift('t') = 'u', и shift('z') = 'a'.
Теперь для каждого shifts[i] = x мы хотим сдвинуть первые i + 1 букв строки s на x раз.

Верните итоговую строку после применения всех таких сдвигов к s.

Пример:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

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

1⃣Вычислите общее количество сдвигов для всех символов строки, используя массив shifts.

2⃣Пройдите по строке s и примените вычисленные сдвиги к каждому символу, начиная с первого и уменьшая количество сдвигов на текущем шаге.

3⃣Постройте и верните итоговую строку после всех сдвигов.

😎 Решение:

class Solution {
    /**
     * @param String $s
     * @param Integer[] $shifts
     * @return String
     */
    function shiftingLetters($s, $shifts) {
        $totalShifts = array_sum($shifts) % 26;
        $sArray = str_split($s);
        
        for ($i = 0; $i < count($sArray); $i++) {
            $newCharValue = (ord($sArray[$i]) - ord('a') + $totalShifts) % 26;
            $sArray[$i] = chr($newCharValue + ord('a'));
            $totalShifts = ($totalShifts - $shifts[$i] + 26) % 26;
        }
        
        return implode('', $sArray);
    }
}

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

🚨 Последний шанс!

Сегодня — последний день краудфандинга.
Через несколько часов всё закроется, и больше невозможно будет поучаствовать.

Если ты хотел, но откладывал — СЕЙЧАС самое время. Займёт 2 минуты, но изменит твой подход к собеседованиям надолго.

Поддержи easyoffer 2.0 и получи:

🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование

PRO подписка к easyoffer 2.0:

✅ Доступ к списку вопросов, которые задаются на собеседованиях + вероятность встречи этих вопросов + их фильтрация по грейдам, типам интервью, компаниям

✅ Доступ к лучшим ответам на вопросы

✅ Список самых частых задач, которые задаются на собеседовании + их фильтрация по грейдам и компаниям

✅ Доступ к лучшим ответам на задачи

✅ Список тестовых заданий компаний + лучшее решение

✅ Доступ к тренажеру "Проработка вопросов", который позволит очень быстро подготовиться к самым частым вопросам

✅ Доступ к тренажеру "Реальное собеседование", который позволит тренироваться проходить собеседование в конкретную компанию

До конца кампании — остались часы.
Поддержать: https://planeta.ru/campaigns/easyoffer

📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Задача: 461. Hamming Distance
Сложность: easy

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.
Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

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

1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед.

2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов.

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

class Solution {
    public function hammingDistance($x, $y) {
        return substr_count(decbin($x ^ $y), '1');
    }
}

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

Завтра последний день!

Краудфандинг заканчивается уже завтра, и второй попытки не будет.

👉 Поддержи easyoffer 2.0 и получи:

🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование

📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ