#easy
Задача: 733. Flood Fill

Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.

Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

1⃣Получите цвет начального пикселя.

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

3⃣Обновите изображение и верните его.

😎 Решение:

function floodFill($image, $sr, $sc, $color) {
    $originalColor = $image[$sr][$sc];
    if ($originalColor == $color) {
        return $image;
    }
    
    $dfs = function($x, $y) use (&$image, &$dfs, $originalColor, $color) {
        if ($x < 0 || $x >= count($image) || $y < 0 || $y >= count($image[0]) || $image[$x][$y] != $originalColor) {
            return;
        }
        $image[$x][$y] = $color;
        $dfs($x + 1, $y);
        $dfs($x - 1, $y);
        $dfs($x, $y + 1);
        $dfs($x, $y - 1);
    };
    
    $dfs($sr, $sc);
    return $image;
}

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

#easy
Задача: 734. Sentence Similarity

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false.

2⃣Создайте словарь для хранения всех пар похожих слов.

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

😎 Решение:

function areSentencesSimilar($sentence1, $sentence2, $similarPairs) {
    if (count($sentence1) != count($sentence2)) {
        return false;
    }

    $similar = [];
    foreach ($similarPairs as $pair) {
        list($x, $y) = $pair;
        if (!isset($similar[$x])) {
            $similar[$x] = [];
        }
        if (!isset($similar[$y])) {
            $similar[$y] = [];
        }
        $similar[$x][] = $y;
        $similar[$y][] = $x;
    }

    for ($i = 0; $i < count($sentence1); $i++) {
        $w1 = $sentence1[$i];
        $w2 = $sentence2[$i];
        if ($w1 != $w2 && (!isset($similar[$w1]) || !in_array($w2, $similar[$w1]))) {
            return false;
        }
    }

    return true;
}

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

#easy
Задача: 746. Min Cost Climbing Stairs

Вам дан целочисленный массив 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]);
}

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

#easy
Задача: 747. Largest Number At Least Twice of Others

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

Пример:

Input: nums = [3,6,1,0]
Output: 1

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

1⃣Найдите максимальный элемент в массиве и его индекс.

2⃣Проверьте, является ли этот максимальный элемент по крайней мере в два раза больше всех остальных элементов массива.

3⃣Если условие выполняется, верните индекс максимального элемента, иначе верните -1.

😎 Решение:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp = cost;
        for (int i = 2; i < n; i++) {
            dp[i] += min(dp[i - 1], dp[i - 2]);
        }
        return min(dp[n - 1], dp[n - 2]);
    }
};

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

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

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