PHP | LeetCode

Задача: 473. Matchsticks to Square
Сложность: medium

Дано целочисленный массив спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.

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

Пример:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

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

1⃣Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True.

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

3⃣Если какой-либо из рекурсивных вызовов возвращает True, возвращаем True, в противном случае возвращаем False.

😎 Решение:

class Solution {
    private $nums;
    private $sums;
    private $possibleSquareSide;

    function __construct() {
        $this->sums = array_fill(0, 4, 0);
    }

    private function dfs($index) {
        if ($index == count($this->nums)) {
            return $this->sums[0] == $this->sums[1] && $this->sums[1] == $this->sums[2] && $this->sums[2] == $this->sums[3];
        }

        $element = $this->nums[$index];

        for ($i = 0; $i < 4; $i++) {
            if ($this->sums[$i] + $element <= $this->possibleSquareSide) {
                $this->sums[$i] += $element;
                if ($this->dfs($index + 1)) {
                    return true;
                }
                $this->sums[$i] -= $element;
            }
        }

        return false;
    }

    function makesquare($nums) {
        if (empty($nums)) {
            return false;
        }

        $perimeter = array_sum($nums);
        $this->possibleSquareSide = intval($perimeter / 4);
        if ($this->possibleSquareSide * 4 != $perimeter) {
            return false;
        }

        rsort($nums);
        $this->nums = $nums;
        return $this->dfs(0);
    }
}

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

Задача: 537. Complex Number Multiplication
Сложность: medium

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

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

1⃣Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

class Solution {
    function complexNumberMultiply($a, $b) {
        list($a_real, $a_img) = explode('+', str_replace('i', '', $a));
        list($b_real, $b_img) = explode('+', str_replace('i', '', $b));
        $realPart = $a_real * $b_real - $a_img * $b_img;
        $imaginaryPart = $a_real * $b_img + $a_img * $b_real;
        return $realPart . "+" . $imaginaryPart . "i";
    }
}

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

Задача: 1672. Richest Customer Wealth
Сложность: easy

Вам дан целочисленный массив размером m x n под названием accounts, где accounts[i][j] — это сумма денег, которую i-й клиент имеет в j-м банке. Верните богатство самого богатого клиента.

Богатство клиента — это сумма денег, которую он имеет во всех своих банковских счетах. Самый богатый клиент — это клиент, который имеет максимальное богатство.

Пример:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

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

1⃣Пройдите по всем клиентам в массиве accounts.

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

3⃣Если текущее богатство больше максимального, обновите максимальное значение. Верните максимальное богатство.

😎 Решение:

class Solution {
    /**
     * @param Integer[][] $accounts
     * @return Integer
     */
    function maximumWealth($accounts) {
        $maxWealthSoFar = 0;
        
        foreach ($accounts as $account) {
            $currCustomerWealth = array_sum($account);
            if ($currCustomerWealth > $maxWealthSoFar) {
                $maxWealthSoFar = $currCustomerWealth;
            }
        }
        
        return $maxWealthSoFar;
    }
}

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

Задача: 746. Min Cost Climbing Stairs
Сложность: easy

Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.

Пример:

Input: cost = [10,15,20]
Output: 15

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

1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.

2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.

3⃣Вернуть минимальную стоимость достижения вершины.

😎 Решение:

function minCostClimbingStairs($cost) {
    $n = count($cost);
    $dp = $cost;
    for ($i = 2; $i < $n; $i++) {
        $dp[$i] += min($dp[$i - 1], $dp[$i - 2]);
    }
    return min($dp[$n - 1], $dp[$n - 2]);
}

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

Задача: 869. Reordered Power of 2
Сложность: medium

Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем.

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

Пример:

Input: n = 1
Output: true

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

1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.

2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.

3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false.

😎 Решение:

class Solution {
    function reorderedPowerOf2($N) {
        $A = str_split(strval($N));
        sort($A);
        for ($i = 0; $i < 30; ++$i) {
            $B = str_split(strval(1 << $i));
            sort($B);
            if ($A == $B) return true;
        }
        return false;
    }
}

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

Задача №25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.
k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то оставшиеся узлы остаются без изменений.
Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

Input: head = [1,2,3,4,5], k = 3  
Output: [3,2,1,4,5]

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

1⃣Определить k-й узел, чтобы проверить, можно ли перевернуть группу.

2⃣Перевернуть k узлов, обновляя связи между ними.

3⃣Перейти к следующей k-группе и повторить процесс.

😎 Решение:

class Solution { 
    public function reverseKGroup($head, $k) { 
        if ($head === null || $k === 1) { 
            return $head; 
        } 

        $dummy = new ListNode(0); 
        $dummy->next = $head; 
        $groupPrev = $dummy; 

        while (true) { 
            $kth = $this->getKthNode($groupPrev, $k); 
            if ($kth === null) { 
                break; 
            } 

            $groupNext = $kth->next; 
            $prev = $groupNext; 
            $curr = $groupPrev->next; 

            while ($curr !== $groupNext) { 
                $tmp = $curr->next; 
                $curr->next = $prev; 
                $prev = $curr; 
                $curr = $tmp; 
            } 

            $tmp = $groupPrev->next; 
            $groupPrev->next = $kth; 
            $groupPrev = $tmp; 
        } 

        return $dummy->next; 
    } 

    private function getKthNode($curr, $k) { 
        while ($curr !== null && $k > 0) { 
            $curr = $curr->next; 
            $k--; 
        } 
        return $curr; 
    } 
}

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

Задача: 1086. High Five
Сложность: easy

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

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

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

Пример:

Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]

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

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

2⃣Создайте список для хранения результата result. Переберите словарь и для каждого студента отсортируйте его оценки в порядке убывания, возьмите пять лучших оценок, вычислите их среднее значение (с целочисленным делением на 5) и добавьте пару [ID, topFiveAverage] в результат.

3⃣Отсортируйте список result по возрастанию ID студента и верните его.

😎 Решение:

import "sort"

type Solution struct {}

func (s *Solution) HighFive(items [][]int) [][]int {
    K := 5
    sort.Slice(items, func(i, j int) bool {
        if items[i][0] != items[j][0] {
            return items[i][0] < items[j][0]
        }
        return items[i][1] > items[j][1]
    })

    var solution [][]int
    i := 0
    n := len(items)
    for i < n {
        id := items[i][0]
        sum := 0
        for k := i; k < i + K; k++ {
            sum += items[k][1]
        }
        for i < n && items[i][0] == id {
            i++
        }
        solution = append(solution, []int{id, sum / K})
    }
    return solution
}

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

Задача: 830. Positions of Large Groups
Сложность: easy

В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.

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

Пример:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

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

1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы.

2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат.

3⃣Обновите i = j + 1 и начните новую группу.

😎 Решение:

class Solution {
    /**
     * @param String $S
     * @return Integer[][]
     */
    function largeGroupPositions($S) {
        $ans = [];
        $i = 0;
        $N = strlen($S);

        for ($j = 0; $j < $N; ++$j) {
            if ($j == $N - 1 || $S[$j] != $S[$j + 1]) {
                if ($j - $i + 1 >= 3) {
                    $ans[] = [$i, $j];
                }
                $i = $j + 1;
            }
        }

        return $ans;
    }
}

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

Задача: 165. Compare Version Numbers
Сложность: medium

Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей.
Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0.
Верните следующее:
- Если version1 < version2, верните -1.
- Если version1 > version2, верните 1.
- В противном случае верните 0.

Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

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

1⃣Разделение строк: Разделите обе строки по символу точки на два массива.

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

3⃣Определение результатов сравнения:
Если два сегмента не равны, верните 1 или -1 в зависимости от того, какой сегмент больше.
Если все сегменты равны после завершения цикла, версии считаются равными. Верните 0

😎 Решение:

class Solution {
    function compareVersion($version1, $version2) {
        $tokens1 = explode('.', $version1);
        $tokens2 = explode('.', $version2);

        $length = max(count($tokens1), count($tokens2));
        for ($i = 0; $i < $length; $i++) {
            $i1 = $i < count($tokens1) ? intval($tokens1[$i]) : 0;
            $i2 = $i < count($tokens2) ? intval($tokens2[$i]) : 0;

            if ($i1 != $i2) {
                return $i1 > $i2 ? 1 : -1;
            }
        }
        return 0;
    }
}

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

Задача: 214. Shortest Palindrome
Сложность: hard

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

Пример:

Input: s = "aacecaaa"
Output: "aaacecaaa"

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

1⃣Создание обратной строки:
Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения.

2⃣Итерация для поиска наибольшего палиндрома:
Перебирайте индекс i от 0 до size(s) - 1.
Для каждой итерации проверяйте, равна ли подстрока s от начала до n - i подстроке rev от i до конца строки.
Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом, так как rev является обратной строкой s.

3⃣Возврат результата:
Как только найден наибольший палиндром, возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s.

😎 Решение:

class Solution {
    public function shortestPalindrome($s) {
        $n = strlen($s);
        $rev = strrev($s);
        for ($i = 0; $i < $n; $i++) {
            if (substr($s, 0, $n - $i) == substr($rev, $i)) {
                return substr($rev, 0, $i) . $s;
            }
        }
        return "";
    }
}

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

Задача: 520. Detect Capital
Сложность: easy

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:
Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

class Solution {
    function detectCapitalUse($word) {
        $pattern = '/^[A-Z]*$|^[a-z]*$|^[A-Z][a-z]*$/';
        return preg_match($pattern, $word) === 1;
    }
}

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

Задача: 343. Integer Break
Сложность: medium

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

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

1⃣Инициализация и базовый случай:
Создайте массив dp длиной n + 1, где dp[i] будет хранить максимальное произведение для числа i. Инициализируйте массив нулями.

2⃣Вычисление максимального произведения:
Для каждого числа i от 2 до n:
Для каждого числа j от 1 до i // 2:
Обновите dp[i] как максимальное значение между текущим dp[i], произведением j и i - j, и произведением j и dp[i - j].

3⃣Возврат результата:
Верните значение dp[n], которое будет максимальным произведением для числа n.

😎 Решение:

class Solution {
    function integerBreak($n) {
        if ($n <= 1) return 0;
        
        $dp = array_fill(0, $n + 1, 0);
        
        for ($i = 2; $i <= $n; $i++) {
            for ($j = 1; $j <= floor($i / 2); $j++) {
                $dp[$i] = max($dp[$i], max($j * ($i - $j), $j * $dp[$i - $j]));
            }
        }
        
        return $dp[$n];
    }
}

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

Задача: 425. Word Squares
Сложность: hard

Дан массив уникальных строк words, верните все квадраты слов, которые можно построить из этих слов. Одно и то же слово из words можно использовать несколько раз. Вы можете вернуть ответ в любом порядке.

Последовательность строк образует допустимый квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(количество строк, количество столбцов).

Например, последовательность слов ["ball", "area", "lead", "lady"] образует квадрат слов, потому что каждое слово читается одинаково как по горизонтали, так и по вертикали.

Пример:

Input: words = ["area","lead","wall","lady","ball"]
Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

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

1⃣Постройте хеш-таблицу из входных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов.

2⃣При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов.

3⃣Используйте алгоритм с возвратом для построения квадрата слов. В каждый момент времени проверьте, совпадают ли строки и столбцы. Если они совпадают, продолжайте добавлять слова; если нет, вернитесь к предыдущему состоянию и попробуйте другое слово.

😎 Решение:

class Solution {
    private $N = 0;
    private $words = [];
    private $prefixHashTable = [];

    function wordSquares($words) {
        $this->words = $words;
        $this->N = strlen($words[0]);

        $results = [];
        $this->buildPrefixHashTable($words);

        foreach ($words as $word) {
            $wordSquares = [$word];
            $this->backtracking(1, $wordSquares, $results);
        }
        return $results;
    }

    function backtracking($step, &$wordSquares, &$results) {
        if ($step == $this->N) {
            $results[] = $wordSquares;
            return;
        }

        $prefix = '';
        foreach ($wordSquares as $word) {
            $prefix .= $word[$step];
        }

        foreach ($this->getWordsWithPrefix($prefix) as $candidate) {
            $wordSquares[] = $candidate;
            $this->backtracking($step + 1, $wordSquares, $results);
            array_pop($wordSquares);
        }
    }

    function buildPrefixHashTable($words) {
        foreach ($words as $word) {
            for ($i = 1; $i < $this->N; $i++) {
                $prefix = substr($word, 0, $i);
                if (!isset($this->prefixHashTable[$prefix])) {
                    $this->prefixHashTable[$prefix] = [];
                }
                $this->prefixHashTable[$prefix][] = $word;
            }
        }
    }

    function getWordsWithPrefix($prefix) {
        return isset($this->prefixHashTable[$prefix]) ? $this->prefixHashTable[$prefix] : [];
    }
}

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

Задача: 1424. Diagonal Traverse II
Сложность: medium

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

Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

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

1⃣Инициализируйте очередь с (0, 0) и список ответов ans.

2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.

3⃣Верните ans.

😎 Решение:

class Solution {
    function findDiagonalOrder($nums) {
        $queue = [[0, 0]];
        $ans = [];
        
        while (!empty($queue)) {
            list($row, $col) = array_shift($queue);
            $ans[] = $nums[$row][$col];
            
            if ($col === 0 && $row + 1 < count($nums)) {
                $queue[] = [$row + 1, $col];
            }
            
            if ($col + 1 < count($nums[$row])) {
                $queue[] = [$row, $col + 1];
            }
        }
        
        return $ans;
    }
}

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

Задача: 1036. Escape a Large Maze
Сложность: hard

Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.

2⃣Проверка простого случая:
Если список blocked пуст, верните true, так как путь не будет заблокирован.
Проверка начальной или целевой клетки:
Если исходная или целевая клетка заблокированы, верните false.

3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.

😎 Решение:

function isEscapePossible($blocked, $source, $target) {
    $blockedSet = [];
    foreach ($blocked as $b) {
        $blockedSet["{$b[0]},{$b[1]}"] = true;
    }
    $src = "{$source[0]},{$source[1]}";
    $tgt = "{$target[0]},{$target[1]}";
    
    if (isset($blockedSet[$src]) || isset($blockedSet[$tgt])) return false;

    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    $maxArea = count($blocked) * (count($blocked) - 1) / 2;

    function bfs($start, $end, $blockedSet, $directions, $maxArea) {
        $queue = [$start];
        $visited = [$start => true];

        while ($queue) {
            if (count($visited) > $maxArea) return true;
            list($x, $y) = explode(',', array_shift($queue));
            foreach ($directions as $dir) {
                $nx = $x + $dir[0];
                $ny = $y + $dir[1];
                $next = "{$nx},{$ny}";
                if ($nx >= 0 && $nx < 1000000 && $ny >= 0 && $ny < 1000000 && !isset($visited[$next]) && !isset($blockedSet[$next])) {
                    if ($next === $end) return true;
                    $queue[] = $next;
                    $visited[$next] = true;
                }
            }
        }
        return false;
    }
    
    return bfs($src, $tgt, $blockedSet, $directions, $maxArea) && bfs($tgt, $src, $blockedSet, $directions, $maxArea);
}

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

Задача: 960. Delete Columns to Make Sorted III

Сложность: hard
Вам дан массив из n строк strs, все одинаковой длины.
Мы можем выбрать любые индексы для удаления, и мы удаляем все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef","uvwxyz"] и индексы удаления {0, 2, 3}, то итоговый массив после удаления будет ["bef", "vyz"].
Предположим, мы выбрали набор индексов удаления answer таким образом, что после удаления итоговый массив имеет каждую строку (ряд) в лексикографическом порядке. (т.е. (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) и (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) и так далее). Верните минимально возможное значение answer.length.

Пример:

Input: strs = ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).
Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.

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

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

2⃣Используйте динамическое программирование, чтобы решить проблему. Пусть dp[k] будет количеством столбцов, которые сохраняются, начиная с позиции k. Мы будем искать максимальное значение dp[k], чтобы найти количество столбцов, которые нужно сохранить.

3⃣Итоговое количество удаляемых столбцов будет равно общей длине строк минус количество сохраненных столбцов.

😎 Решение:

class Solution {
    /**
     * @param String[] $A
     * @return Integer
     */
    function minDeletionSize($A) {
        $W = strlen($A[0]);
        $dp = array_fill(0, $W, 1);

        for ($i = $W - 2; $i >= 0; --$i) {
            for ($j = $i + 1; $j < $W; ++$j) {
                $valid = true;
                foreach ($A as $row) {
                    if ($row[$i] > $row[$j]) {
                        $valid = false;
                        break;
                    }
                }
                if ($valid) {
                    $dp[$i] = max($dp[$i], 1 + $dp[$j]);
                }
            }
        }

        return $W - max($dp);
    }
}

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

Задача: 657. Robot Return to Origin
Сложность: easy

На плоскости с координатами (0, 0) находится робот. Дана последовательность его движений, определите, возвращается ли робот в исходную точку (0, 0) после завершения всех своих движений.

Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз).

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

Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода.

Пример:

Input: moves = "UD"
Output: true

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

1⃣Инициализация координат:
Начните с координат (0, 0).

2⃣Обработка движений:
Пройдите по строке moves и обновляйте координаты в зависимости от движения:
'R' увеличивает координату x на 1.
'L' уменьшает координату x на 1.
'U' увеличивает координату y на 1.
'D' уменьшает координату y на 1.

3⃣Проверка конечных координат:
Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    function judgeCircle($moves) {
        $x = 0;
        $y = 0;
        for ($i = 0; $i < strlen($moves); $i++) {
            switch ($moves[$i]) {
                case 'R': $x++; break;
                case 'L': $x--; break;
                case 'U': $y++; break;
                case 'D': $y--; break;
            }
        }
        return $x == 0 && $y == 0;
    }
}

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

Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy

Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false.

Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

1⃣Инициализировать счетчик нулей значением k для учета первого появления единицы.

2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.

3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.

😎 Решение:

class Solution {
    function kLengthApart($nums, $k) {
        $count = $k;
        foreach ($nums as $num) {
            if ($num == 1) {
                if ($count < $k) {
                    return false;
                }
                $count = 0;
            } else {
                $count++;
            }
        }
        return true;
    }
}

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

Задача: 82. Remove Duplicates from Sorted List II
Сложность: medium

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

Пример:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

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

1⃣Инициализация "стража" и предшественника:
Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены.
Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж.

2⃣Проход по списку с проверкой на дубликаты:
Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val.
Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов.

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

😎 Решение:

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

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

function deleteDuplicates($head) {
    $sentinel = new ListNode(0, $head);
    $pred = $sentinel;
    while ($head !== null) {
        if ($head->next !== null && $head->val === $head->next->val) {
            while ($head->next !== null && $head->val === $head->next->val) {
                $head = $head->next;
            }
            $pred->next = $head->next;
        } else {
            $pred = $pred->next;
        }
        $head = $head->next;
    }
    return $sentinel->next;
}
?>

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

Задача: 988. Smallest String Starting From Leaf
Сложность: medium

Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.

Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.

Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.

Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.

Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

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

1⃣Инициализация и подготовка:
Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк).
Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы.

2⃣Обход дерева:
Если текущий узел пуст (null), просто вернитесь из функции.
Добавьте текущий символ (соответствующий значению узла) в начало строки пути.
Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше.
Рекурсивно вызовите dfs для левого и правого потомков текущего узла.

3⃣Возврат результата:
Вызовите функцию dfs с корневым узлом и пустым путем.
Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня.

😎 Решение:

class Solution {
    private $ans = "~";

    function smallestFromLeaf($root) {
        $this->dfs($root, "");
        return $this->ans;
    }

    private function dfs($node, $path) {
        if ($node === null) return;
        $path = chr($node->val + ord('a')) . $path;
        if ($node->left === null && $node->right === null) {
            if (strcmp($path, $this->ans) < 0) {
                $this->ans = $path;
            }
        }
        $this->dfs($node->left, $path);
        $this->dfs($node->right, $path);
    }
}

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