Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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);
    }
}

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

Задача: 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);
}

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

Задача: 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;
    }
}

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

Задача: 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] : [];
    }
}

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

Задача: 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];
    }
}

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

Задача: 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;
    }
}

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

Задача: 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 "";
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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
}

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

Задача №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; 
    } 
}

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

Задача: 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;
    }
}

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

Задача: 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]);
}

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

Задача: 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;
    }
}

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

Задача: 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";
    }
}

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

Задача: 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);
    }
}

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

Задача: 528. Random Pick with Weight
Сложность: medium

Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i.
Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).
Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).

Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

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

1⃣Инициализация и предобработка весов:
В конструкторе создайте массив накопительных сумм prefixSums, где каждая позиция будет содержать сумму всех предыдущих весов до текущего индекса включительно.
Также в конструкторе сохраните общую сумму весов totalSum.

2⃣Генерация случайного числа и выбор индекса:
В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum.
Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу.

3⃣Возврат результата:
Верните найденный индекс.

😎 Решение:

class Solution {
    private $prefixSums;
    private $totalSum;

    /**
     * @param Integer[] $w
     */
    function __construct($w) {
        $this->prefixSums = array_fill(0, count($w), 0);
        $prefixSum = 0;
        for ($i = 0; $i < count($w); $i++) {
            $prefixSum += $w[$i];
            $this->prefixSums[$i] = $prefixSum;
        }
        $this->totalSum = $prefixSum;
    }

    /**
     * @return Integer
     */
    function pickIndex() {
        $target = $this->totalSum * (mt_rand() / mt_getrandmax());
        for ($i = 0; $i < count($this->prefixSums); $i++) {
            if ($target < $this->prefixSums[$i]) {
                return $i;
            }
        }
        return count($this->prefixSums) - 1;
    }
}

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

Задача: 945. Minimum Increment to Make Array Unique
Сложность: medium

Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.

Пример:

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

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

1⃣Отсортировать массив nums.
Инициализировать переменную moves для подсчета количества ходов.

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

3⃣Вернуть общее количество ходов.

😎 Решение:

function minIncrementForUnique($nums) {
    sort($nums);
    $moves = 0;
    for ($i = 1; $i < count($nums); $i++) {
        if ($nums[$i] <= $nums[$i - 1]) {
            $moves += $nums[$i - 1] + 1 - $nums[$i];
            $nums[$i] = $nums[$i - 1] + 1;
        }
    }
    return $moves;
}

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

Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard

Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.

Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами:

Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение.
В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше.
Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты.

Пример:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

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

1⃣Инициализируйте переменные: n для размера массивов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте массив wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию.

2⃣Создайте приоритетную очередь workers (максимальная куча) для хранения выбранных работников. Итерируйте через отсортированный wageToQualityRatio: добавляйте качество текущего работника в workers и обновляйте currentTotalQuality.

3⃣Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. Верните totalCost.

😎 Решение:

class Solution {
    function mincostToHireWorkers($quality, $wage, $k) {
        $n = count($quality);
        $totalCost = PHP_FLOAT_MAX;
        $currentTotalQuality = 0;
        $wageToQualityRatio = [];

        for ($i = 0; $i < $n; $i++) {
            $wageToQualityRatio[] = [$wage[$i] / $quality[$i], $quality[$i]];
        }

        usort($wageToQualityRatio, fn($a, $b) => $a[0] <=> $b[0]);
        $workers = new SplMaxHeap();

        foreach ($wageToQualityRatio as [$ratio, $q]) {
            $workers->insert($q);
            $currentTotalQuality += $q;

            if ($workers->count() > $k) {
                $currentTotalQuality -= $workers->extract();
            }

            if ($workers->count() == $k) {
                $totalCost = min($totalCost, $currentTotalQuality * $ratio);
            }
        }

        return $totalCost;
    }
}

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