Задача: 1218. Longest Arithmetic Subsequence of Given Difference
Сложность: medium

Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference.

Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов.

Пример:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

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

1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1.

2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]:
Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference:
- если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference].
- в противном случае, установите before_a = 0.
Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]).

3⃣Верните answer после завершения итерации.

😎 Решение:

class Solution {
    function longestSubsequence($arr, $difference) {
        $dp = [];
        $answer = 1;
        
        foreach ($arr as $a) {
            $beforeA = isset($dp[$a - $difference]) ? $dp[$a - $difference] : 0;
            $dp[$a] = $beforeA + 1;
            $answer = max($answer, $dp[$a]);
        }
        
        return $answer;
    }
}

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

Задача: 1426. Counting Elements
Сложность: easy

Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно.

Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

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

1⃣ Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве.

2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве.

3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика.

😎 Решение:

class Solution {
    function countElements($arr) {
        $count = 0;
        foreach ($arr as $x) {
            if ($this->integerInArray($arr, $x + 1)) {
                $count++;
            }
        }
        return $count;
    }

    function integerInArray($arr, $target) {
        foreach ($arr as $x) {
            if ($x == $target) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 1066. Campus Bikes II
Сложность: medium

На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.

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

Верните минимально возможную сумму Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом.

Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

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

1⃣Для каждого рабочего, начиная с рабочего с индексом 0, пройдите по всем велосипедам и назначьте велосипед рабочему, если он доступен (visited[bikeIndex] = false). После назначения велосипеда отметьте его как недоступный (visited[bikeIndex] = true). Добавьте Манхэттенское расстояние от этого назначения к общей текущей сумме расстояний, представленной currDistanceSum, и выполните рекурсивный вызов для следующего рабочего.

2⃣Когда рекурсивный вызов завершится, сделайте велосипед снова доступным, установив visited[bikeIndex] в false. Если мы назначили велосипеды всем рабочим, сравните currDistanceSum с smallestDistanceSum и обновите smallestDistanceSum соответственно.

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

😎 Решение:

class Solution {
    private $smallestDistanceSum = PHP_INT_MAX;
    private $visited = array_fill(0, 10, false);
    
    private function findDistance($worker, $bike) {
        return abs($worker[0] - $bike[0]) + abs($worker[1] - $bike[1]);
    }
    
    private function minimumDistanceSum($workers, $workerIndex, $bikes, $currDistanceSum) {
        if ($workerIndex >= count($workers)) {
            $this->smallestDistanceSum = min($this->smallestDistanceSum, $currDistanceSum);
            return;
        }
        
        if ($currDistanceSum >= $this->smallestDistanceSum) {
            return;
        }
        
        foreach ($bikes as $bikeIndex => $bike) {
            if (!$this->visited[$bikeIndex]) {
                $this->visited[$bikeIndex] = true;
                $this->minimumDistanceSum($workers, $workerIndex + 1, $bikes, 
                    $currDistanceSum + $this->findDistance($workers[$workerIndex], $bike));
                $this->visited[$bikeIndex] = false;
            }
        }
    }
    
    public function assignBikes($workers, $bikes) {
        $this->minimumDistanceSum($workers, 0, $bikes, 0);
        return $this->smallestDistanceSum;
    }
}

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

Задача: 1094. Car Pooling
Сложность: medium

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

Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.

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

Пример:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

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

1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity.

2⃣Чтобы узнать фактическую вместимость, нужно просто знать изменение количества пассажиров в каждый момент времени.

3⃣Мы можем сохранить изменения количества пассажиров в каждый момент времени, отсортировать их по меткам времени и, наконец, пройтись по ним, чтобы проверить фактическую вместимость.

😎 Решение:

class Solution {
    function carPooling($trips, $capacity) {
        $timestamp = [];
        foreach ($trips as $trip) {
            $timestamp[$trip[1]] = ($timestamp[$trip[1]] ?? 0) + $trip[0];
            $timestamp[$trip[2]] = ($timestamp[$trip[2]] ?? 0) - $trip[0];
        }
        ksort($timestamp);
        $usedCapacity = 0;
        foreach ($timestamp as $change) {
            $usedCapacity += $change;
            if ($usedCapacity > $capacity) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 782. Transform to Chessboard
Сложность: hard

Дана бинарная сетка размером n x n. В каждом ходе можно поменять местами любые две строки или любые два столбца.

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

Шахматная доска — это доска, на которой ни один 0 и ни одна 1 не соприкасаются друг с другом по вертикали и горизонтали.

Пример:

Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation: One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.

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

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

2⃣Затем для каждой возможной идеальной трансформации этой линии найдите минимальное количество перестановок, чтобы преобразовать эту линию в её идеальную и добавьте это к ответу. Например, [0, 1, 1, 1, 0, 0] имеет два идеала [0, 1, 0, 1, 0, 1] или [1, 0, 1, 0, 1, 0]; но [0, 1, 1, 1, 0] имеет только один идеал [1, 0, 1, 0, 1].

3⃣В Java мы используем целые числа для представления строк как двоичных чисел. Мы проверяем количество различий с [1, 0, 1, 0, 1, 0, ...] с помощью побитового исключающего ИЛИ с 0b010101010101.....01 = 0x55555555. Чтобы убедиться, что мы не добавляем излишне большие элементы.

😎 Решение:

class Solution {
    function movesToChessboard($board) {
        $N = count($board);
        $ans = 0;
        
        foreach ([$this->getCount($board), $this->getCount($this->transpose($board))] as $count) {
            $values = array_values($count);
            sort($values);
            if (count($values) !== 2 || $values[0] !== intdiv($N, 2) || $values[1] !== intdiv($N + 1, 2)) {
                return -1;
            }

            $keys = array_keys($count);
            $line1 = $keys[0];
            $line2 = $keys[1];
            if (!$this->allOpposite($line1, $line2)) {
                return -1;
            }

            $starts = $N % 2 === 0 ? [0, 1] : [substr_count($line1, '1') * 2 > $N ? 1 : 0];

            $minSwaps = PHP_INT_MAX;
            foreach ($starts as $start) {
                $swaps = 0;
                for ($i = 0; $i < $N; $i++) {
                    if ((int)$line1[$i] !== ($i % 2 === $start ? 1 : 0)) {
                        $swaps++;
                    }
                }
                $minSwaps = min($minSwaps, intdiv($swaps, 2));
            }
            $ans += $minSwaps;
        }
        
        return $ans;
    }

    private function getCount($board) {
        $count = [];
        foreach ($board as $row) {
            $key = implode('', $row);
            if (!isset($count[$key])) {
                $count[$key] = 0;
            }
            $count[$key]++;
        }
        return $count;
    }

    private function transpose($board) {
        $N = count($board);
        $transposed = array_fill(0, $N, array_fill(0, $N, 0));
        for ($i = 0; $i < $N; $i++) {
            for ($j = 0; $j < $N; $j++) {
                $transposed[$j][$i] = $board[$i][$j];
            }
        }
        return $transposed;
    }

    private function allOpposite($line1, $line2) {
        for ($i = 0; $i < strlen($line1); $i++) {
            if ((int)$line1[$i] ^ (int)$line2[$i] === 0) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 922. Sort Array By Parity II4
Сложность: medium

Дан массив целых чисел nums, половина целых чисел в нем нечетные, а другая половина - четные. Отсортируйте массив так, чтобы во всех случаях, когда nums[i] нечетный, i был нечетным, а во всех случаях, когда nums[i] четный, i был четным. Верните любой массив ответов, удовлетворяющий этому условию.

Пример:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

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

1⃣Инициализировать два указателя even_idx и odd_idx для отслеживания позиций четных и нечетных индексов соответственно.

2⃣Пройти по массиву nums и для каждого элемента:
Если элемент четный, поместить его на позицию even_idx и увеличить even_idx на 2.
Если элемент нечетный, поместить его на позицию odd_idx и увеличить odd_idx на 2.

3⃣Вернуть отсортированный массив.

😎 Решение:

function sortArrayByParityII($nums) {
    $result = array_fill(0, count($nums), 0);
    $evenIdx = 0;
    $oddIdx = 1;
    
    foreach ($nums as $num) {
        if ($num % 2 == 0) {
            $result[$evenIdx] = $num;
            $evenIdx += 2;
        } else {
            $result[$oddIdx] = $num;
            $oddIdx += 2;
        }
    }
    
    return $result;
}

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

Задача: 319. Bulb Switcher
Сложность: medium

Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.
На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.
Верните количество лампочек, которые будут включены после n раундов.

Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

1⃣Инициализация
Лампочка остается включенной, если она переключалась нечетное количество раз. Лампочка будет переключаться на каждом делителе её номера.

2⃣Определение состояния лампочки
Лампочка останется включенной только в том случае, если у нее нечетное количество делителей, что возможно только для квадратных чисел.

3⃣Подсчет включенных лампочек
Количество лампочек, которые будут включены после n раундов.

😎 Решение:

class Solution {
    function bulbSwitch($n) {
        return floor(sqrt($n));
    }
}

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

Задача №21. Merge Two Sorted Lists
Сложность: easy

Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Верните заголовок объединенного связанного списка.

Пример:

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]

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

1⃣Создать новый список для объединенного результата.

2⃣Использовать указатели для прохождения по обоим спискам и добавления наименьшего элемента.

3⃣Добавить оставшиеся элементы после окончания одного из списков.

😎 Решение:

class Solution { 

    function mergeTwoLists($list1, $list2) { 
        $newList = new ListNode(); 
        $current = $newList; 

        while($list1 || $list2) { 
            if ($list1 && !$list2) { 
                $current->next = new ListNode($list1->val); 
                $list1 = $list1->next; 
            } elseif (!$list1 && $list2) { 
                $current->next = new ListNode($list2->val); 
                $list2 = $list2->next; 
            } else { 
                if ($list1->val <= $list2->val) { 
                    $current->next = new ListNode($list1->val); 
                    $list1 = $list1->next; 
                } else { 
                    $current->next = new ListNode($list2->val); 
                    $list2 = $list2->next; 
                } 
            } 
            $current = $current->next; 
        } 

        return $newList->next; 
    } 
}

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

Задача: 1003. Check If Word Is Valid After Substitutions
Сложность: medium

Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false.

Пример:

Input: s = "aabcbc"
Output: true

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

1⃣Проверка допустимости длины строки:
Проверьте, что длина строки s кратна 3. Если нет, верните false.

2⃣Использование стека для проверки:
Инициализируйте пустой стек. Проходите по каждому символу строки s.
Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false.
Если текущий символ не 'c', добавьте его в стек.

3⃣Проверка остатка стека:
В конце, если стек пуст, верните true. Иначе верните false.

😎 Решение:

class Solution {
    function isValid($s) {
        if (strlen($s) % 3 != 0) return false;

        $stack = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if ($char == 'c') {
                if (count($stack) < 2 || array_pop($stack) != 'b' || array_pop($stack) != 'a') {
                    return false;
                }
            } else {
                $stack[] = $char;
            }
        }

        return empty($stack);
    }
}

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

Задача: 1429. First Unique Number
Сложность: medium

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

Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.

Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

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

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

2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет.

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

😎 Решение:

class FirstUnique {
    private $queue;
    private $isUnique;

    function __construct($nums) {
        $this->queue = new SplDoublyLinkedList();
        $this->isUnique = [];
        foreach ($nums as $num) {
            $this->add($num);
        }
    }

    function showFirstUnique() {
        while (!$this->queue->isEmpty() && !$this->isUnique[$this->queue->bottom()]) {
            $this->queue->shift();
        }
        if ($this->queue->isEmpty()) {
            return -1;
        }
        return $this->queue->bottom();
    }

    function add($value) {
        if (!isset($this->isUnique[$value])) {
            $this->isUnique[$value] = true;
            $this->queue->push($value);
        } elseif ($this->isUnique[$value]) {
            $this->isUnique[$value] = false;
        }
    }
}

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

Задача: 553. Optimal Division
Сложность: medium

Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой.
Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4".
Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным.
Верните соответствующее выражение, которое имеет максимальное значение в строковом формате.

Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

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

1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе.

2⃣Для каждой цифры первого числа: умножьте цифру второго числа на цифру первого числа и добавьте предыдущий перенос к результату умножения. Возьмите остаток от деления на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру к массиву currentResult. Разделите результат умножения на 10, чтобы получить новое значение переноса.

3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его.

😎 Решение:

class Solution {
    private function addStrings($num1, $num2) {
        $ans = [];
        $carry = 0;
        $n1 = count($num1);
        $n2 = count($num2);

        for ($i = 0; $i < max($n1, $n2) || $carry; $i++) {
            $digit1 = $i < $n1 ? $num1[$i] : 0;
            $digit2 = $i < $n2 ? $num2[$i] : 0;
            $sum = $digit1 + $digit2 + $carry;
            $carry = intdiv($sum, 10);
            $ans[] = $sum % 10;
        }
        return $ans;
    }

    private function multiplyOneDigit($firstNumber, $secondNumberDigit, $numZeros) {
        $currentResult = array_fill(0, $numZeros, 0);
        $carry = 0;

        for ($i = 0; $i < strlen($firstNumber); $i++) {
            $multiplication = (intval($secondNumberDigit) * intval($firstNumber[$i])) + $carry;
            $carry = intdiv($multiplication, 10);
            $currentResult[] = $multiplication % 10;
        }
        if ($carry != 0) {
            $currentResult[] = $carry;
        }
        return $currentResult;
    }

    public function multiply($firstNumber, $secondNumber) {
        if ($firstNumber === "0" || $secondNumber === "0") {
            return "0";
        }

        $firstNumber = strrev($firstNumber);
        $secondNumber = strrev($secondNumber);

        $ans = array_fill(0, strlen($firstNumber) + strlen($secondNumber), 0);

        for ($i = 0; $i < strlen($secondNumber); $i++) {
            $ans = $this->addStrings($this->multiplyOneDigit($firstNumber, $secondNumber[$i], $i), $ans);
        }

        while (end($ans) === 0) {
            array_pop($ans);
        }

        return implode('', array_reverse($ans));
    }
}

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

Задача: 433. Minimum Genetic Mutation
Сложность: medium

Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.
Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.
Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.
Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.
Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк.

Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

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

1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene.

2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen.

3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1.

😎 Решение:

function minMutation($start, $end, $bank) {
    $queue = [$start];
    $seen = [$start => true];
    $steps = 0;

    while (count($queue) > 0) {
        $nodesInQueue = count($queue);

        for ($j = 0; $j < $nodesInQueue; $j++) {
            $node = array_shift($queue);

            if ($node === $end) {
                return $steps;
            }

            foreach (str_split("ACGT") as $c) {
                for ($i = 0; $i < strlen($node); $i++) {
                    $neighbor = substr($node, 0, $i) . $c . substr($node, $i + 1);
                    if (!isset($seen[$neighbor]) && in_array($neighbor, $bank)) {
                        $queue[] = $neighbor;
                        $seen[$neighbor] = true;
                    }
                }
            }
        }

        $steps++;
    }

    return -1;
}

echo minMutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"]) . "\n"; // Output: 1
echo minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]) . "\n"; // Output: 2
echo minMutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"]) . "\n"; // Output: 3

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

Задача: 860. Lemonade Change
Сложность: easy

На лимонадной стойке каждый лимонад стоит $5. Покупатели стоят в очереди, чтобы купить лимонад, и заказывают по одному (в порядке, указанном в массиве bills). Каждый покупатель покупает только один лимонад и платит либо $5, $10, либо $20. Вы должны предоставить правильную сдачу каждому покупателю, чтобы чистая сделка была такой, что покупатель платит $5.

Обратите внимание, что изначально у вас нет никакой сдачи.

Дан целочисленный массив bills, где bills[i] — купюра, которой платит i-й покупатель. Верните true, если вы можете предоставить каждому покупателю правильную сдачу, или false в противном случае.

Пример:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

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

1⃣Инициализируем переменные для хранения количества пятерок и десяток. Если покупатель платит $5, добавляем эту купюру в наш запас.

2⃣Если покупатель платит $10, проверяем наличие пятерки для сдачи. Если пятерки нет, возвращаем false. В противном случае, уменьшаем количество пятерок и увеличиваем количество десяток.

3⃣Если покупатель платит $20, сначала пытаемся дать сдачу десяткой и пятеркой. Если это невозможно, проверяем наличие трех пятерок. Если не можем дать сдачу, возвращаем false. После обработки всех покупателей, возвращаем true.

😎 Решение:

class Solution {
    function lemonadeChange($bills) {
        $five = 0;
        $ten = 0;
        foreach ($bills as $bill) {
            if ($bill == 5) {
                $five++;
            } elseif ($bill == 10) {
                if ($five == 0) return false;
                $five--;
                $ten++;
            } else {
                if ($five > 0 && $ten > 0) {
                    $five--;
                    $ten--;
                } elseif ($five >= 3) {
                    $five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

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

Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy

Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.

На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).

Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.

Пример:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

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

1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.

2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.

3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.

😎 Решение:

class Solution {
    function minStartValue($nums) {
        $startValue = 1;
        while (true) {
            $total = $startValue;
            $isValid = true;
            foreach ($nums as $num) {
                $total += $num;
                if ($total < 1) {
                    $isValid = false;
                    break;
                }
            }
            if ($isValid) {
                return $startValue;
            }
            $startValue++;
        }
    }
}

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

Задача: 1046. Last Stone Weight
Сложность: easy

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

1⃣Создай максимальную кучу из массива камней.

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

3⃣Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0, если камней не осталось.

😎 Решение:

function lastStoneWeight($stones) {
    rsort($stones);
    
    while (count($stones) > 1) {
        $first = array_shift($stones);
        $second = array_shift($stones);
        if ($first != $second) {
            array_push($stones, $first - $second);
            rsort($stones);
        }
    }
    
    return count($stones) ? $stones[0] : 0;
}

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

Задача: 136. Single Number
Сложность: easy

Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент.

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

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

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

1⃣Переберите все элементы в массиве nums.

2⃣Если какое-то число в nums новое для массива, добавьте его.

3⃣Если какое-то число уже есть в массиве, удалите его.

😎 Решение:

function singleNumber($nums) {
    $noDuplicateList = [];
    foreach ($nums as $i) {
        if (!in_array($i, $noDuplicateList)) {
            array_push($noDuplicateList, $i);
        } else {
            $index = array_search($i, $noDuplicateList);
            array_splice($noDuplicateList, $index, 1);
        }
    }
    return $noDuplicateList[0];
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

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

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.

3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.

😎 Решение:

function prevPermOpt1($arr) {
    $n = count($arr);
    for ($i = $n - 2; $i >= 0; $i--) {
        if ($arr[$i] > $arr[$i + 1]) {
            break;
        }
    }
    if ($i == -1) {
        return $arr;
    }
    
    for ($j = $n - 1; $j > $i; $j--) {
        if ($arr[$j] < $arr[$i] && ($j == $n - 1 || $arr[$j] != $arr[$j + 1])) {
            break;
        }
    }
    
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
    
    return $arr;
}

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

Задача: 161. One Edit Distance
Сложность: medium

Даны две строки s и t. Верните true, если они отличаются ровно на одну операцию редактирования, иначе верните false.
Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:
- Вставить ровно один символ в строку s, чтобы получить t.
- Удалить ровно один символ из строки s, чтобы получить t.
- Заменить ровно один символ в строке s на другой символ, чтобы получить t.

Пример:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

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

1⃣Проверка длины строк:
Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку.
Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.

2⃣Сравнение строк посимвольно:
Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t.
Если находите различающийся символ:
Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false.
Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false

3⃣Проверка на возможное добавление символа в конец s:
Если после посимвольного сравнения не было найдено различий на всей длине s и t длиннее s на один символ, это означает, что t можно получить добавлением одного символа в конец s. В этом случае верните true.
В противном случае верните false, так как это означает, что t либо имеет больше отличий, либо такой же размер как s без возможности привести их к равенству одной операцией редактирования.

😎 Решение:

class Solution {
    function isOneEditDistance($s, $t) {
        $ns = strlen($s);
        $nt = strlen($t);
        if ($ns > $nt) return $this->isOneEditDistance($t, $s);
        if ($nt - $ns > 1) return false;

        for ($i = 0; $i < $ns; $i++) {
            if ($s[$i] != $t[$i]) {
                if ($ns == $nt) return substr($s, $i + 1) == substr($t, $i + 1);
                else return substr($s, $i) == substr($t, $i + 1);
            }
        }
        return $ns + 1 == $nt;
    }
}

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