#easy
Задача: 748. Shortest Completing Word

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

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

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

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

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

function shortestCompletingWord($licensePlate, $words) {
    function getCharCount($s) {
        $count = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $char = strtolower($s[$i]);
            if (ctype_alpha($char)) {
                if (!isset($count[$char])) $count[$char] = 0;
                $count[$char]++;
            }
        }
        return $count;
    }

    $licenseCount = getCharCount($licensePlate);

    function isCompletingWord($word, $licenseCount) {
        $wordCount = [];
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($wordCount[$char])) $wordCount[$char] = 0;
            $wordCount[$char]++;
        }
        foreach ($licenseCount as $char => $cnt) {
            if (!isset($wordCount[$char]) || $wordCount[$char] < $cnt) {
                return false;
            }
        }
        return true;
    }

    $result = null;
    foreach ($words as $word) {
        if (isCompletingWord($word, $licenseCount)) {
            if ($result === null || strlen($word) < strlen($result)) {
                $result = $word;
            }
        }
    }
    return $result;
}

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

#hard
Задача: 928. Minimize Malware Spread II

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

1⃣Определить компоненты связности в графе. Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов.

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

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

😎 Решение:

function minMalwareSpread($graph, $initial) {
    $n = count($graph);

    function dfs($node, &$visited, &$component, $graph, $n) {
        $stack = [$node];
        while (!empty($stack)) {
            $u = array_pop($stack);
            $component[] = $u;
            for ($v = 0; $v < $n; $v++) {
                if ($graph[$u][$v] === 1 && !isset($visited[$v])) {
                    $visited[$v] = true;
                    $stack[] = $v;
                }
            }
        }
    }

    $components = [];
    $visited = [];

    for ($i = 0; $i < $n; $i++) {
        if (!isset($visited[$i])) {
            $component = [];
            $visited[$i] = true;
            dfs($i, $visited, $component, $graph, $n);
            $components[] = $component;
        }
    }

    $infectedInComponent = array_fill(0, count($components), 0);
    $nodeToComponent = [];

    foreach ($components as $idx => $component) {
        foreach ($component as $node) {
            $nodeToComponent[$node] = $idx;
        }
    }

    foreach ($initial as $node) {
        $componentIdx = $nodeToComponent[$node];
        $infectedInComponent[$componentIdx]++;
    }

    sort($initial);
    $minInfected = PHP_INT_MAX;
    $resultNode = $initial[0];

    foreach ($initial as $node) {
        $componentIdx = $nodeToComponent[$node];
        if ($infectedInComponent[$componentIdx] === 1) {
            $componentSize = count($components[$componentIdx]);
            if ($componentSize < $minInfected || ($componentSize === $minInfected && $node < $resultNode)) {
                $minInfected = $componentSize;
                $resultNode = $node;
            }
        }
    }

    return $resultNode;
}

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

#medium
Задача: 930. Binary Subarrays With Sum

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:

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

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

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

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

3⃣Вернуть счетчик подмассивов.

😎 Решение:

function numSubarraysWithSum($nums, $goal) {
    $prefixSumCount = [0 => 1];
    $currentSum = 0;
    $count = 0;

    foreach ($nums as $num) {
        $currentSum += $num;

        if (isset($prefixSumCount[$currentSum - $goal])) {
            $count += $prefixSumCount[$currentSum - $goal];
        }

        if (isset($prefixSumCount[$currentSum])) {
            $prefixSumCount[$currentSum]++;
        } else {
            $prefixSumCount[$currentSum] = 1;
        }
    }

    return $count;
}

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

#medium
Задача: 750. Number Of Corner Rectangles

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

1⃣Пройдите по строкам матрицы. Для каждой пары строк, найдите все столбцы, где оба значения равны 1.

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

3⃣Для каждой пары строк добавьте количество возможных прямоугольников в общий счетчик.

😎 Решение:

function countCornerRectangles($grid) {
    $count = 0;
    for ($i = 0; $i < count($grid); $i++) {
        for ($j = $i + 1; $j < count($grid); $j++) {
            $numPairs = 0;
            for ($k = 0; $k < count($grid[0]); $k++) {
                if ($grid[$i][$k] == 1 && $grid[$j][$k] == 1) {
                    $numPairs++;
                }
            }
            if ($numPairs > 1) {
                $count += $numPairs * ($numPairs - 1) / 2;
            }
        }
    }
    return $count;
}

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

#medium
Задача: 751. IP to CIDR

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

function ipToInt($ip) {
    $parts = explode('.', $ip);
    return ($parts[0] << 24) + ($parts[1] << 16) + ($parts[2] << 8) + $parts[3];
}

function intToIp($num) {
    return (($num >> 24) & 255) . "." . (($num >> 16) & 255) . "." . (($num >> 8) & 255) . "." . ($num & 255);
}

function cidr($ip, $prefixLength) {
    return "$ip/$prefixLength";
}

function findCidrBlocks($startIp, $n) {
    $start = ipToInt($startIp);
    $result = [];
    
    while ($n > 0) {
        $maxSize = 1;
        while ($maxSize <= $start && $maxSize <= $n) {
            $maxSize <<= 1;
        }
        $maxSize >>= 1;
        
        while ($start % $maxSize != 0) {
            $maxSize >>= 1;
        }
        
        $result[] = cidr(intToIp($start), 32 - log($maxSize, 2) + 1);
        $start += $maxSize;
        $n -= $maxSize;
    }
    
    return $result;
}

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

На easyoffer 2.0 появится:
🎯 Тренажер "Проработка вопросов"

✅ Метод интервальных повторений и флеш-карточки
✅ Персональный подход изучения на основе ваших ответов
✅ Упор на самые частые вопросы

📌 Интервальные повторения по карточкам это научно доказанный метод эффективного обучения. Каждая карточка – это вопрос, который задают на собеседовании, вы можете выбрать "Не знаю", "Знаю", "Не спрашивать". После ответа вам показывается правильный ответ и возможность изучить вопрос подробнее (примеры ответов других людей). От ваших ответов зависит то, как часто карточки будут показываться на следующей тренировке. Трудные вопросы показываются чаще, простые – реже. Это позволяет бить в слабые места. Кроме того, изначальный порядок карточек зависит от частотности (вероятности встретить вопрос).

🚀 Благодаря этому тренажеру вы сможете очень быстро подготовиться к собеседованию, т.к. фокусируетесь отвечать на самые частые вопросы. Именно так готовился я сам, когда искал первую работу программистом.

Уже в течение недели я объявлю о старте краудфандинговой кампании на сбор финансирования, чтобы ускорить разработку сайта. Все кто поддержит проект до официального релиза получат самые выгодные условия пользования сервисом. А именно 1 год доступа к сайту по цене месячной подписки.

‼️ Очень важно, чтобы как можно больше людей поддержали проект в первые дни, по-этому те кто окажет поддержку первыми получат еще более выгодную стоимость на годовую подписку и существенный 💎 бонус о котором я позже расскажу в этом телеграм канале. Подписывайтесь, чтобы узнать о старте проекта раньше других и воспользоваться лимитированными вознаграждениями.

#medium
Задача: 752. Open the Lock

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

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

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

function openLock($deadends, $target) {
    function neighbors($node) {
        $res = [];
        for ($i = 0; $i < 4; $i++) {
            $x = intval($node[$i]);
            for ($d = -1; $d <= 1; $d += 2) {
                $y = ($x + $d + 10) % 10;
                $res[] = substr($node, 0, $i) . $y . substr($node, $i + 1);
            }
        }
        return $res;
    }

    $dead = array_flip($deadends);
    $queue = [['0000', 0]];
    $visited = ['0000' => true];

    while (!empty($queue)) {
        list($node, $steps) = array_shift($queue);
        if ($node === $target) return $steps;
        if (isset($dead[$node])) continue;
        foreach (neighbors($node) as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = [$neighbor, $steps + 1];
            }
        }
    }

    return -1;
}

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

#medium
Задача: 753. Cracking the Safe

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

function crackSafe($n, $k) {
    $seen = [];
    $result = [];

    function dfs($node, $k, &$seen, &$result) {
        for ($x = 0; $x < $k; $x++) {
            $neighbor = $node . $x;
            if (!in_array($neighbor, $seen)) {
                $seen[] = $neighbor;
                dfs(substr($neighbor, 1), $k, $seen, $result);
                $result[] = $x;
            }
        }
    }

    $startNode = str_repeat("0", $n - 1);
    dfs($startNode, $k, $seen, $result);

    return $startNode . implode('', $result);
}

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

#medium
Задача: 754. Reach a Number

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

function reachTarget($target) {
    $target = abs($target);
    $position = 0;
    $steps = 0;
    while ($position < $target || ($position - $target) % 2 != 0) {
        $steps += 1;
        $position += $steps;
    }
    return $steps;
}

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

#medium
Задача: 755. Pour Water

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

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

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

function pourWater($heights, $volume, $k) {
    for ($v = 0; $v < $volume; $v++) {
        $dropIndex = $k;
        foreach ([-1, 1] as $d) {
            $i = $k;
            while ($i + $d >= 0 && $i + $d < count($heights) && $heights[$i + $d] <= $heights[$i]) {
                if ($heights[$i + $d] < $heights[$i]) {
                    $dropIndex = $i + $d;
                }
                $i += $d;
            }
            if ($dropIndex != $k) {
                break;
            }
        }
        $heights[$dropIndex]++;
    }
    return $heights;
}

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

#medium
Задача: 756. Pyramid Transition Matrix

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

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

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

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

😎 Решение:

function pyramidTransition($bottom, $allowed) {
    $allowedDict = [];

    foreach ($allowed as $pattern) {
        $key = substr($pattern, 0, 2);
        $value = $pattern[2];
        if (!isset($allowedDict[$key])) {
            $allowedDict[$key] = [];
        }
        $allowedDict[$key][] = $value;
    }

    return canBuild($bottom, $allowedDict);
}

function canBuild($currentLevel, $allowedDict) {
    if (strlen($currentLevel) == 1) return true;

    $nextLevelOptions = [];
    for ($i = 0; $i < strlen($currentLevel) - 1; $i++) {
        $key = substr($currentLevel, $i, 2);
        if (!isset($allowedDict[$key])) return false;
        $nextLevelOptions[] = $allowedDict[$key];
    }

    return canBuildNextLevel($nextLevelOptions, 0, "", $allowedDict);
}

function canBuildNextLevel($options, $index, $nextLevel, $allowedDict) {
    if ($index == count($options)) return canBuild($nextLevel, $allowedDict);
    foreach ($options[$index] as $option) {
        if (canBuildNextLevel($options, $index + 1, $nextLevel . $option, $allowedDict)) return true;
    }
    return false;
}

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

#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

1⃣Отсортируйте интервалы по их конечным точкам.

2⃣Инициализируйте пустое множество для хранения чисел.

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

😎 Решение:

function minSetSize($intervals) {
    usort($intervals, function($a, $b) {
        return $a[1] - $b[1];
    });
    $nums = [];
    foreach ($intervals as $interval) {
        $start = $interval[0];
        $end = $interval[1];
        if (empty($nums) || end($nums) < $start) {
            $nums[] = $end - 1;
            $nums[] = $end;
        } elseif (end($nums) == $end - 1) {
            $nums[] = $end;
        }
    }
    return count($nums);
}

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

На easyoffer 2.0 появится новый раздел:
Задачи с собеседований

🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований
🟠Вероятность встретить ту или иную задачу
🟠Возможность подготовиться к задачам конкретной компании

Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение.

Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Задача: 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, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов.

😎 Решение:

<?php

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;
}
?>

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

Задача: 1510. Stone Game IV
Сложность: hard

Алиса и Боб поочередно играют в игру, причем Алиса начинает первой.

Изначально в куче n камней. В ходе каждого хода игрок удаляет любое ненулевое количество камней, являющееся квадратом целого числа.

Кроме того, если игрок не может сделать ход, он/она проигрывает игру.

Дано положительное целое число n, верните true, если и только если Алиса выиграет игру, иначе верните false, предполагая, что оба игрока играют оптимально.

Пример:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

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

1⃣Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях.

2⃣Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs.

3⃣Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True.

😎 Решение:

class Solution {
    function winnerSquareGame($n) {
        $cache = [0 => false];
        return $this->dfs($cache, $n);
    }

    function dfs(&$cache, $remain) {
        if (isset($cache[$remain])) {
            return $cache[$remain];
        }
        $sqrtRoot = floor(sqrt($remain));
        for ($i = 1; $i <= $sqrtRoot; $i++) {
            if (!$this->dfs($cache, $remain - $i * $i)) {
                $cache[$remain] = true;
                return true;
            }
        }
        $cache[$remain] = false;
        return false;
    }
}

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

На easyoffer 2.0 появится:
Тренажер "Реальное собеседование"

🟠 Сценарии вопросов из реального собеседования
🟠Возможность подготовиться к собеседованию в конкретную компанию
🟠Итоговая статистика (прошёл/не прошёл)

Сценарий вопросов взят из реального собеседования. То есть вы тренируетесь на тех вопросах, которые действительно задавались в компании X.

Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 1228. Missing Number In Arithmetic Progression
Сложность: easy

В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1.

Из массива arr было удалено значение, которое не было первым или последним значением в массиве.

Дан массив arr, вернуть удаленное значение.

Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

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

1⃣Рассчитать разность difference между элементами арифметической прогрессии.

2⃣Начать с первого элемента массива и последовательно увеличивать ожидаемое значение на difference, проверяя каждый элемент массива.

3⃣Вернуть первое ожидаемое значение, которое не совпадает с текущим значением в массиве.

😎 Решение:

class Solution {
    function missingNumber($arr) {
        $n = count($arr);
        $difference = ($arr[$n - 1] - $arr[0]) / $n;
        $expected = $arr[0];

        foreach ($arr as $val) {
            if ($val != $expected) {
                return $expected;
            }
            $expected += $difference;
        }
        return $expected;
    }
}

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

Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium

У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.

Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

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

1⃣Начните с:
Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент.
Сумма чисел на предыдущих кубиках currSum равна 0.
Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию.

1⃣Базовые случаи:
Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target.

3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum.

😎 Решение:

class Solution {
    const MOD = 1000000007;

    function waysToTarget(&$memo, $diceIndex, $n, $currSum, $target, $k) {
        if ($diceIndex == $n) {
            return $currSum == $target ? 1 : 0;
        }

        if ($memo[$diceIndex][$currSum] != -1) {
            return $memo[$diceIndex][$currSum];
        }

        $ways = 0;
        for ($i = 1; $i <= min($k, $target - $currSum); $i++) {
            $ways = ($ways + $this->waysToTarget($memo, $diceIndex + 1, $n, $currSum + $i, $target, $k)) % self::MOD;
        }
        return $memo[$diceIndex][$currSum] = $ways;
    }

    function numRollsToTarget($n, $k, $target) {
        $memo = array_fill(0, $n + 1, array_fill(0, $target + 1, -1));
        return $this->waysToTarget($memo, 0, $n, 0, $target, $k);
    }
}

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

Задача: 371. Sum of Two Integers
Сложность: medium

Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -.

Пример:

Input: a = 1, b = 2
Output: 3

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

1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата.

2⃣Если нужно вычислить сумму:
Пока перенос не равен нулю (y != 0):
Текущий ответ без переноса равен XOR x и y: answer = x ^ y.
Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1.
Подготовьтесь к следующему циклу: x = answer, y = carry.
Верните x * sign.

3⃣Если нужно вычислить разность:
Пока заимствование не равно нулю (y != 0):
Текущий ответ без заимствования равен XOR x и y: answer = x ^ y.
Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1.
Подготовьтесь к следующему циклу: x = answer, y = borrow.
Верните x * sign.

😎 Решение:

class Solution {
    function getSum($a, $b) {
        $x = abs($a);
        $y = abs($b);
        if ($x < $y) return $this->getSum($b, $a);
        $sign = $a > 0 ? 1 : -1;

        if ($a * $b >= 0) {
            while ($y != 0) {
                $carry = ($x & $y) << 1;
                $x ^= $y;
                $y = $carry;
            }
        } else {
            while ($y != 0) {
                $borrow = ((~$x) & $y) << 1;
                $x ^= $y;
                $y = $borrow;
            }
        }
        return $x * $sign;
    }
}

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

Задача: 240. Search a 2D Matrix II
Сложность: medium

Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства:

Целые числа в каждой строке отсортированы по возрастанию слева направо.
Целые числа в каждом столбце отсортированы по возрастанию сверху вниз.

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

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

1⃣Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null.

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

3⃣Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы.

😎 Решение:

class Solution {
    private function binarySearch($matrix, $target, $start, $vertical) {
        $lo = $start;
        $hi = $vertical ? count($matrix[0]) - 1 : count($matrix) - 1;

        while ($hi >= $lo) {
            $mid = intdiv($lo + $hi, 2);
            $value = $vertical ? $matrix[$start][$mid] : $matrix[$mid][$start];
            if ($value < $target) {
                $lo = $mid + 1;
            } else if ($value > $target) {
                $hi = $mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public function searchMatrix($matrix, $target) {
        if ($matrix === null || count($matrix) === 0) return false;

        $shorterDim = min(count($matrix), count($matrix[0]));
        for ($i = 0; $i < $shorterDim; $i++) {
            if ($this->binarySearch($matrix, $target, $i, true) || $this->binarySearch($matrix, $target, $i, false)) {
                return true;
            }
        }
        return false;
    }
}

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