C# | LeetCode

#medium Задача: 304. Range Sum Query 2D - Immutable Дана двумерная матрица matrix. Обработайте несколько запросов следующего типа: Вычислите сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2). Реализуйте класс NumMatrix: - NumMatrix(int[][] matrix) Инициализирует объект целочисленной матрицей matrix.- int sumRegion(int row1, int col1, int row2, int col2) Возвращает сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2). Необходимо разработать алгоритм, где метод sumRegion работает за O(1) по времени. Пример:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями. 2⃣Предварительное вычисление сумм: Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени. 😎 Решение:

public class NumMatrix {
    private int[,] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix.Length == 0 || matrix[0].Length == 0) return;
        dp = new int[matrix.Length + 1, matrix[0].Length + 1];
        for (int r = 0; r < matrix.Length; r++) {
            for (int c = 0; c < matrix[0].Length; c++) {
                dp[r + 1, c + 1] = dp[r + 1, c] + dp[r, c + 1] + matrix[r][c] - dp[r, c];
            }
        }
    }

    public int SumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1, col2 + 1] - dp[row1, col2 + 1] - dp[row2 + 1, col1] + dp[row1, col1];
    }
}

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

#hard Задача: 587. Erect the Fence Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду. Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены. Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке. Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

👨‍💻 Алгоритм: 1⃣ Сортировка точек и построение нижней оболочки: Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам. Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот. 2⃣ Построение верхней оболочки: Пройдитесь по точкам в обратном порядке, чтобы построить верхнюю оболочку. Добавляйте точки к оболочке и удаляйте последние точки, если они не образуют против часовой стрелки поворот. 3⃣ Удаление дублирующих элементов и возврат результата: Используйте HashSet, чтобы удалить дублирующиеся точки из стека. Преобразуйте результат в массив и верните его. 😎 Решение:

public class Solution {
    public int Orientation(int[] p, int[] q, int[] r) {
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    }

    public IList<IList<int>> OuterTrees(int[][] points) {
        Array.Sort(points, (p, q) => p[0] == q[0] ? p[1].CompareTo(q[1]) : p[0].CompareTo(q[0]));
        List<int[]> hull = new List<int[]>();

        foreach (var point in points) {
            while (hull.Count >= 2 && Orientation(hull[hull.Count - 2], hull[hull.Count - 1], point) > 0)
                hull.RemoveAt(hull.Count - 1);
            hull.Add(point);
        }

        hull.RemoveAt(hull.Count - 1);

        for (int i = points.Length - 1; i >= 0; i--) {
            while (hull.Count >= 2 && Orientation(hull[hull.Count - 2], hull[hull.Count - 1], points[i]) > 0)
                hull.RemoveAt(hull.Count - 1);
            hull.Add(points[i]);
        }

        HashSet<int[]> ret = new HashSet<int[]>(hull, new ArrayComparer());
        return ret.ToList<IList<int>>();
    }

    private class ArrayComparer : IEqualityComparer<int[]> {
        public bool Equals(int[] x, int[] y) {
            return x[0] == y[0] && x[1] == y[1];
        }

        public int GetHashCode(int[] obj) {
            return obj[0].GetHashCode() ^ obj[1].GetHashCode();
        }
    }
}

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

Мастер-класс по Python для школьников. Бесплатно! Онлайн-урок от ведущего ИТ ВУЗа страны - Университета Иннополис для учеников 6-11 классов. 👍Бесплатно! ✅Познакомим с профессией тестировщика. ✅Научим проверять программы, находить баги. ✅На практике отработаем использование инструментов и методов тестирования. ⚡Ваш ребёнок за один час создаст автоматический тест на языке программирования Python и сможет использовать полученные знания в дальнейшем! Для участия важно знание основ программирования на Python. Помогите ребёнку освоить востребованную профессию. Регистрируйтесь! Зарегистрироваться #реклама 16+ progmatica.innopolis.university О рекламодателе

#medium Задача: 583. Delete Operation for Two Strings Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми. На одном шаге можно удалить ровно один символ в любой строке. Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

👨‍💻 Алгоритм: 1⃣ Инициализация массива: Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2. 2⃣ Заполнение массива: Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки. 3⃣ Обновление и результат: Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений. 😎 Решение:

public class Solution {
    public int MinDistance(string word1, string word2) {
        int m = word1.Length;
        int n = word2.Length;
        int[] dp = new int[n + 1];

        for (int i = 0; i <= m; i++) {
            int[] temp = new int[n + 1];
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    temp[j] = i + j;
                } else if (word1[i - 1] == word2[j - 1]) {
                    temp[j] = dp[j - 1];
                } else {
                    temp[j] = 1 + Math.Min(dp[j], temp[j - 1]);
                }
            }
            dp = temp;
        }

        return dp[n];
    }
}

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

#medium Задача: 537. Complex Number Multiplication Комплексное число можно представить в виде строки в формате "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⃣ Формирование строки результата: Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её. 😎 Решение:

public class Solution {
    public string ComplexNumberMultiply(string a, string b) {
        var x = a.Split(new char[] { '+', 'i' });
        var y = b.Split(new char[] { '+', 'i' });
        int a_real = int.Parse(x[0]);
        int a_img = int.Parse(x[1]);
        int b_real = int.Parse(y[0]);
        int b_img = int.Parse(y[1]);
        int realPart = a_real * b_real - a_img * b_img;
        int imaginaryPart = a_real * b_img + a_img * b_real;
        return realPart + "+" + imaginaryPart + "i";
    }
}

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

Yandex DataLens Festival, 2-18 декабря Для аналитиков, тимлидов, разработчиков, продактов и маркетологов. Эксперты Яндекса поделятся опытом. Онлайн и бесплатно Зарегистрироваться #реклама 16+ yandex.cloud О рекламодателе

#easy Задача: 303. Range Sum Query - Immutable Дан целочисленный массив nums. Обработайте несколько запросов следующего типа: Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right. Реализуйте класс NumArray: - NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums. - int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]). Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums. 2⃣Предварительное вычисление сумм: Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат. 😎 Решение:

public class NumArray {
    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.Length + 1];
        for (int i = 0; i < nums.Length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int SumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

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

#medium Задача: 536. Construct Binary Tree from String Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел. Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой. Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует. Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

👨‍💻 Алгоритм: 1⃣ Извлечение числа: Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть. 2⃣ Построение поддерева: Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки. Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют. 3⃣ Основная функция: Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево. 😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode Str2Tree(string s) {
        return Str2TreeInternal(s, 0).Item1;
    }
    
    private Tuple<int, int> GetNumber(string s, int index) {
        bool isNegative = false;
        if (s[index] == '-') {
            isNegative = true;
            index++;
        }
        int number = 0;
        while (index < s.Length && char.IsDigit(s[index])) {
            number = number * 10 + (s[index] - '0');
            index++;
        }
        return Tuple.Create(isNegative ? -number : number, index);
    }

    private Tuple<TreeNode, int> Str2TreeInternal(string s, int index) {
        if (index == s.Length) return Tuple.Create<TreeNode, int>(null, index);
        
        var numberData = GetNumber(s, index);
        int value = numberData.Item1;
        index = numberData.Item2;
        
        TreeNode node = new TreeNode(value);
        
        if (index < s.Length && s[index] == '(') {
            var leftData = Str2TreeInternal(s, index + 1);
            node.left = leftData.Item1;
            index = leftData.Item2;
        }

        if (index < s.Length && s[index] == '(') {
            var rightData = Str2TreeInternal(s, index + 1);
            node.right = rightData.Item1;
            index = rightData.Item2;
        }
        
        return Tuple.Create(node, index < s.Length && s[index] == ')' ? index + 1 : index);
    }
}

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

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#medium Задача: 535. Encode and Decode TinyURL Спроектируйте класс для кодирования URL и декодирования короткого URL. Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL. Реализуйте класс Solution: Solution() Инициализирует объект системы. String encode(String longUrl) Возвращает короткий URL для данного longUrl. String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом. Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

👨‍💻 Алгоритм: 1⃣ Инициализация: Создайте строку, содержащую все возможные символы (цифры и буквы), которые могут быть использованы для генерации кода. Создайте хэш-таблицу для хранения соответствий коротких и длинных URL-адресов. Создайте объект для генерации случайных чисел. 2⃣ Кодирование: Сгенерируйте случайный 6-символьный код. Если такой код уже существует в хэш-таблице, повторите генерацию. Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице. Верните полный короткий URL. 3⃣ Декодирование: Удалите префикс короткого URL, чтобы получить код. Используйте код для поиска длинного URL в хэш-таблице. Верните длинный URL. 😎 Решение:

public class Codec {
    private static string alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private Dictionary<string, string> map = new Dictionary<string, string>();
    private Random rand = new Random();
    
    private string GetRand() {
        var sb = new StringBuilder();
        for (int i = 0; i < 6; i++) {
            sb.Append(alphabet[rand.Next(62)]);
        }
        return sb.ToString();
    }

    public string Encode(string longUrl) {
        string key = GetRand();
        while (map.ContainsKey(key)) {
            key = GetRand();
        }
        map[key] = longUrl;
        return "http://tinyurl.com/" + key;
    }

    public string Decode(string shortUrl) {
        string key = shortUrl.Replace("http://tinyurl.com/", "");
        return map[key];
    }
}

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

– Помощь с pet-проектом – Составление roadmap – Общая консультация – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

– Помощь с pet-проектом – Составление roadmap – Общая консультация – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

#hard Задача: 302. Smallest Rectangle Enclosing Black Pixels Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель. Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали. Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели. Вы должны написать алгоритм со сложностью менее O(mn). Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно. 2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника: left = min(left, x) right = max(right, x + 1) top = min(top, y) bottom = max(bottom, y + 1) 3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top). 😎 Решение:

public class Solution {
    public int MinArea(char[][] image, int x, int y) {
        int m = image.Length, n = image[0].Length;
        int left = SearchColumns(image, 0, y, 0, m, true);
        int right = SearchColumns(image, y + 1, n, 0, m, false);
        int top = SearchRows(image, 0, x, left, right, true);
        int bottom = SearchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }

    private int SearchColumns(char[][] image, int i, int j, int top, int bottom, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int t = top;
            while (t < bottom && image[t][k] == '0') t++;
            if ((t < bottom) == opt) {
                j = k;
            } else {
               ### Go
```go
package main

func minArea(image [][]byte, x int, y int) int {
    m, n := len(image), len(image[0])
    left := searchColumns(image, 0, y, 0, m, true)
    right := searchColumns(image, y+1, n, 0, m, false)
    top := searchRows(image, 0, x, left, right, true)
    bottom := searchRows(image, x+1, m, left, right, false)
    return (right - left) * (bottom - top)
}

func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        t := top
        for t < bottom && image[t][k] == '0' {
            t++
        }
        if (t < bottom) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
    for i != j {
        k := (i + j) / 2
        l := left
        for l < right && image[k][l] == '0' {
            l++
        }
        if (l < right) == opt {
            j = k
        } else {
            i = k + 1
        }
    }
    return i
}

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

Аренда облачного сервера в Selectel. От 286,34 рублей в месяц! - Гибкие конфигурации; - Бэкап по расписанию; - 3 ТБ трафика в месяц бесплатно; - Защита от DDoS-атак на уровне L3-L4; - Соответствие 152-ФЗ, PCI DSS. Перейти на сайт #реклама 16+ selectel.ru О рекламодателе

#medium Задача: 532. K-diff Pairs in an Array Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве. Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия: 0 <= i, j < nums.length i != j |nums[i] - nums[j]| == k Обратите внимание, что |val| обозначает абсолютное значение val. Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

👨‍💻 Алгоритм: 1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums. 2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям: Если k > 0, проверьте, существует ли ключ, равный x + k. Если k == 0, проверьте, есть ли более одного вхождения x. 3⃣ Увеличьте счётчик результатов, если условие выполняется. 😎 Решение:

public class Solution {
    public int FindPairs(int[] nums, int k) {
        var counter = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!counter.ContainsKey(num)) {
                counter[num] = 0;
            }
            counter[num]++;
        }
        
        int result = 0;
        foreach (var entry in counter) {
            int x = entry.Key;
            int val = entry.Value;
            if (k > 0 && counter.ContainsKey(x + k)) {
                result++;
            } else if (k == 0 && val > 1) {
                result++;
            }
        }
        
        return result;
    }
}

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

#medium Задача: 531. Lonely Pixel I Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей. Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей. Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

👨‍💻 Алгоритм: 1⃣ Подсчёт количества чёрных пикселей в строках и столбцах: Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1. 2⃣ Поиск одиночных чёрных пикселей: Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1. 3⃣ Возврат результата: Верните answer. 😎 Решение:

public class Solution {
    public int FindLonelyPixel(char[][] picture) {
        int n = picture.Length;
        int m = picture[0].Length;
        
        int[] rowCount = new int[n];
        int[] columnCount = new int[m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] == 'B') {
                    rowCount[i]++;
                    columnCount[j]++;
                }
            }
        }
        
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] == 'B' && rowCount[i] == 1 && columnCount[j] == 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
}

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

Обучение на Frontend-разработчика. С нуля за 9 месяцев. На курсе вы получите все навыки, необходимые для старта в профессии Frontend-разработчика. Персональный наставник middle/senior уровня. 14 проектов, лайвкодинг, хакатоны, репетиции техсобеседования. Освоите JavaScript, React, TypeScript Официальный диплом и сертификат школы. Поддержка наставника по JS в течение 3-х месяцев после диплома. Гарантия трудоустройства. Если вы не устроитесь, вернём деньги. Это закреплено в договоре п. 6.14 С 9 по 30 ноября 2024 г. скидка 40% на все программы Result School Узнать больше #реклама 16+ result.school О рекламодателе

#easy Задача: 541. Reverse String II Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки. Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть. Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

👨‍💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:

class Solution {
    public string ReverseStr(string s, int k) {
        char[] a = s.ToCharArray();
        for (int start = 0; start < a.Length; start += 2 * k) {
            int i = start, j = Math.Min(start + k - 1, a.Length - 1);
            while (i < j) {
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return new string(a);
    }
}

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

#medium Задача: 540. Single Element in a Sorted Array Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз. Верните единственный элемент, который встречается только один раз. Ваше решение должно работать за время O(log n) и использовать O(1) памяти. Пример:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

👨‍💻 Алгоритм: 1⃣Начиная с первого элемента, итерируемся через каждый второй элемент, проверяя, является ли следующий элемент таким же, как текущий. Если нет, то текущий элемент — это искомый элемент. 2⃣Если доходим до последнего элемента, то он является искомым элементом. Обрабатываем этот случай после завершения цикла, чтобы избежать выхода за пределы массива. 3⃣Возвращаем найденный элемент. 😎 Решение:

class Solution {
    public int SingleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.Length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[^1];
    }
}

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

Помощь в трудоустройстве в IT-сфере! По всей России объявили бесплатную программу на шестимесячное обучение по IT-cпециальностям. Запись на участие в программе продлится до конца июля, но чтобы туда попасть, нужно пройти специальный профтест. По результату тестирования сразу узнаете, какая профессия вам подойдет, и проходите ли вы на бесплатное обучение. Перейти на сайт #реклама 16+ urban-university.ru О рекламодателе