#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⃣Обновите изображение и верните его.

😎 Решение:

public class Solution {
    public int[][] FloodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }
        
        DFS(image, sr, sc, originalColor, color);
        return image;
    }
    
    private void DFS(int[][] image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.Length || y < 0 || y >= image[0].Length || image[x][y] != originalColor) {
            return;
        }
        image[x][y] = newColor;
        DFS(image, x + 1, y, originalColor, newColor);
        DFS(image, x - 1, y, originalColor, newColor);
        DFS(image, x, y + 1, originalColor, newColor);
        DFS(image, x, y - 1, originalColor, newColor);
    }
}

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

#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 на схожесть, используя словарь и правило, что слово всегда похоже на само себя.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool AreSentencesSimilar(string[] sentence1, string[] sentence2, IList<IList<string>> similarPairs) {
        if (sentence1.Length != sentence2.Length) {
            return false;
        }

        var similar = new Dictionary<string, HashSet<string>>();
        foreach (var pair in similarPairs) {
            var x = pair[0];
            var y = pair[1];
            if (!similar.ContainsKey(x)) {
                similar[x] = new HashSet<string>();
            }
            if (!similar.ContainsKey(y)) {
                similar[y] = new HashSet<string>();
            }
            similar[x].Add(y);
            similar[y].Add(x);
        }

        for (int i = 0; i < sentence1.Length; i++) {
            var w1 = sentence1[i];
            var w2 = sentence2[i];
            if (w1 != w2 && (!similar.ContainsKey(w1) || !similar[w1].Contains(w2))) {
                return false;
            }
        }

        return true;
    }
}

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

#easy
Задача: 744. Find Smallest Letter Greater Than Target

Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

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

2⃣Если найденный символ существует, вернуть его.

3⃣Если такого символа не существует, вернуть первый символ в letters.

😎 Решение:

public class Solution {
    public char NextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.Length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (letters[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return letters[left % letters.Length];
    }
}

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

#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⃣Вернуть минимальную стоимость достижения вершины.

😎 Решение:

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.Min(dp[i - 1], dp[i - 2]);
        }
        return Math.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.

😎 Решение:

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.Min(dp[i - 1], dp[i - 2]);
        }
        return Math.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⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string ShortestCompletingWord(string licensePlate, string[] words) {
        var licenseCount = GetCharCount(licensePlate);

        string result = null;
        foreach (var word in words) {
            if (IsCompletingWord(word, licenseCount)) {
                if (result == null || word.Length < result.Length) {
                    result = word;
                }
            }
        }
        return result;
    }

    private Dictionary<char, int> GetCharCount(string s) {
        var count = new Dictionary<char, int>();
        foreach (var c in s.ToLower()) {
            if (char.IsLetter(c)) {
                count[c] = count.GetValueOrDefault(c, 0) + 1;
            }
        }
        return count;
    }

    private bool IsCompletingWord(string word, Dictionary<char, int> licenseCount) {
        var wordCount = new Dictionary<char, int>();
        foreach (var c in word) {
            wordCount[c] = wordCount.GetValueOrDefault(c, 0) + 1;
        }
        foreach (var entry in licenseCount) {
            if (!wordCount.ContainsKey(entry.Key) || wordCount[entry.Key] < entry.Value) {
                return false;
            }
        }
        return true;
    }
}

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

#easy
Задача: 1287. Element Appearing More Than 25% In Sorted Array

Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число.

Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

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

1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num.

2⃣Установите target = arr.length / 4.

3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    public int FindSpecialInteger(int[] arr) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
        int target = arr.Length / 4;
        foreach (int num in arr) {
            if (!counts.ContainsKey(num)) {
                counts[num] = 0;
            }
            counts[num]++;
            if (counts[num] > target) {
                return num;
            }
        }
        return -1;
    }
}

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