C# | LeetCode

#Easy Задача: 599. Minimum Index Sum of Two Lists Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов. Общая строка - это строка, которая появляется и в list1, и в list2. Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк. Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке. Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

👨‍💻 Алгоритм: 1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме. 2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j. 3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string[] FindRestaurant(string[] list1, string[] list2) {
        var map = new Dictionary<int, List<string>>();
        for (int i = 0; i < list1.Length; i++) {
            for (int j = 0; j < list2.Length; j++) {
                if (list1[i] == list2[j]) {
                    if (!map.ContainsKey(i + j)) {
                        map[i + j] = new List<string>();
                    }
                    map[i + j].Add(list1[i]);
                }
            }
        }
        int minIndexSum = int.MaxValue;
        foreach (var key in map.Keys) {
            minIndexSum = Math.Min(minIndexSum, key);
        }
        return map[minIndexSum].ToArray();
    }
}

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

#easy Задача: 594. Longest Harmonious Subsequence Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1. Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей. Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов. Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

using System;
using System.Collections.Generic;

public class Solution {
    public int FindLHS(int[] nums) {
        var count = new Dictionary<int, int>();
        int res = 0;
        
        foreach (var num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
            if (count.ContainsKey(num + 1)) {
                res = Math.Max(res, count[num] + count[num + 1]);
            }
            if (count.ContainsKey(num - 1)) {
                res = Math.Max(res, count[num] + count[num - 1]);
            }
        }
        
        return res;
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка для вас и 3-х ваших близких 60 дней бесплатно. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте сейчас❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

#Easy Задача: 598. Range Addition II Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi. Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций. Пример:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

👨‍💻 Алгоритм: 1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j). 2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])). 3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y. 😎 Решение:

public class Solution {
    public int MaxCount(int m, int n, int[][] ops) {
        int minA = m;
        int minB = n;
        foreach (var op in ops) {
            minA = Math.Min(minA, op[0]);
            minB = Math.Min(minB, op[1]);
        }
        return minA * minB;
    }
}

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

#medium Задача: 593. Valid Square Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат. Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке. Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов). Пример:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

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

public class Solution {
    private int Dist(int[] p1, int[] p2) {
        return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0]);
    }

    private bool Check(int[] p1, int[] p2, int[] p3, int[] p4) {
        return Dist(p1, p2) > 0 &&
               Dist(p1, p2) == Dist(p2, p3) &&
               Dist(p2, p3) == Dist(p3, p4) &&
               Dist(p3, p4) == Dist(p4, p1) &&
               Dist(p1, p3) == Dist(p2, p4);
    }

    public bool ValidSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        return Check(p1, p2, p3, p4) ||
               Check(p1, p3, p2, p4) ||
               Check(p1, p2, p4, p3);
    }
}

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

Концептуальные офисы в БЦ RUNOVSKY 14 Концептуальное офисное пространство для работы, расположенное в историческом центре Москвы в районе Замоскворечье. Проект имеет свой неповторимый характер. Переосмысление стиля ар-деко нашло свое отражение в черных фасадах с арочным остеклением. БЦ находится в 2 минутах ходьбы от метро "Новокузнецкая", через которую проходят основные пешие маршруты до Третьяковской галереи, парка Зарядья и Московкского Кремля. Проектом предусмотрено большое количество планировочных решений офисов площадью от 27 м2 с возможностью объединения смежных помещений. Тех, кто решит купить лот в "RUNOVSKY 14", ждет премиальный сервис, безопасность и комфортная атмосфера. Перейти на сайт #реклама зиккурат.рф О рекламодателе

#medium Задача: 592. Fraction Addition and Subtraction Дана строка, представляющая выражение сложения и вычитания дробей, верните результат вычисления в строковом формате. Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1. Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

using System;
using System.Collections.Generic;

public class Solution {
    public string FractionAddition(string expression) {
        var sign = new List<char>();
        if (expression[0] != '-') sign.Add('+');
        foreach (char ch in expression) {
            if (ch == '+' || ch == '-') sign.Add(ch);
        }

        int prevNum = 0, prevDen = 1, i = 0;
        var fractions = expression.Replace("-", "+-").Split(new[] { '+' }, StringSplitOptions.RemoveEmptyEntries);
        
        foreach (var sub in fractions) {
            var fraction = sub.Split('/');
            int num = int.Parse(fraction[0]);
            int den = int.Parse(fraction[1]);
            int g = Math.Abs(Gcd(prevDen, den));
            if (sign[i++] == '+') prevNum = prevNum * den / g + num * prevDen / g;
            else prevNum = prevNum * den / g - num * prevDen / g;
            prevDen = prevDen * den / g;
            g = Math.Abs(Gcd(prevDen, prevNum));
            prevNum /= g;
            prevDen /= g;
        }
        
        return $"{prevNum}/{prevDen}";
    }

    private int Gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

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

#easy Задача: 590. N-ary Tree Postorder Traversal Дано корневое дерево с n-арной структурой, верните обход дерева в постфиксном порядке для значений его узлов. Сериализация входных данных n-арного дерева представлена в обходе уровней. Каждая группа детей разделяется значением null (см. примеры). Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

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

using System.Collections.Generic;

public class Node {
    public int val;
    public IList<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}

public class Solution {
    public IList<int> Postorder(Node root) {
        LinkedList<int> output = new LinkedList<int>();
        if (root == null) {
            return output;
        }

        Stack<Node> stack = new Stack<Node>();
        stack.Push(root);
        
        while (stack.Count > 0) {
            Node node = stack.Pop();
            output.AddFirst(node.val);
            foreach (Node child in node.children) {
                if (child != null) {
                    stack.Push(child);
                }
            }
        }
        
        return new List<int>(output);
    }
}

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

Квартиры со скидкой до 1,9 млн ₽. ЖК «Астро» в Тюмени «Астро» — семейный ЖК без студий в Тюменской слободе. Закрытый двор. Все необходимое рядом: школа, детсад, ТРЦ. Квартиры с качественной отделкой от застройщика — живите сразу после сдачи дома. Не упустите свою выгоду: ✅ Скидки до 1 900 000 ₽ ✅ Включим ремонт в ипотеку ✅ 10 мин. до центра Тюмени Зафиксируйте условия и получите подборку планировок! Получить предложение Финансовые услуги оказывает: ПАО "Сбербанк". #реклама mrqz.me О рекламодателе

#easy Задача: 557. Reverse Words in a String III Дана строка s. Необходимо изменить порядок символов в каждом слове в предложении, сохранив при этом пробелы и начальный порядок слов. Пример:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

👨‍💻 Алгоритм: 1⃣Создайте переменную lastSpaceIndex и установите её значение в -1. Пройдите по каждому символу строки s от 0-го до n-го индекса, используя указатель strIndex. 2⃣Когда strIndex указывает на пробел, определите начало (startIndex = lastSpaceIndex + 1) и конец (endIndex = strIndex - 1) текущего слова. Используя два указателя, измените порядок символов в текущем слове. 3⃣Обновите lastSpaceIndex значением strIndex. После окончания цикла измените порядок символов в последнем слове (от lastSpaceIndex + 1 до конца строки). 😎 Решение:

public class Solution {
    public string ReverseWords(string s) {
        char[] chars = s.ToCharArray();
        int lastSpaceIndex = -1;
        int len = chars.Length;
        
        for (int strIndex = 0; strIndex <= len; strIndex++) {
            if (strIndex == len || chars[strIndex] == ' ') {
                int startIndex = lastSpaceIndex + 1;
                int endIndex = strIndex - 1;
                while (startIndex < endIndex) {
                    char temp = chars[startIndex];
                    chars[startIndex] = chars[endIndex];
                    chars[endIndex] = temp;
                    startIndex++;
                    endIndex--;
                }
                lastSpaceIndex = strIndex;
            }
        }
        
        return new string(chars);
    }
}

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

А вы знали что?... 🕵️В Windows есть папка, которая собирает на вас компромат! Посмотрите видео выше — насколько легко узнать всю информацию о вас Простых способов узнать о вас практически всё — сотни, и если вы хотите соблюдать хотя бы минимум сетевой гигиены — подпишитесь на IT ВЕДОМСТВО Они рассказывает о признаках майнеров, как удалить трояны и порно-баннеры за 5 минут Помимо всего этого, сейчас владелец канала проводит розыгрыш умной колонки, для всех новоприбывших подписчиков 💻 Подписываемся на IT ВЕДОМСТВО — выигрываем призы и соблюдаем цифровую гигиену

#medium Задача: 556. Next Greater Element III Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм: Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1. Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1. Пример:

Input: n = 12
Output: 21

👨‍💻 Алгоритм: 1⃣Нахождение и перестановка цифр Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j. 2⃣Обратный порядок оставшихся цифр Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной. 3⃣Проверка результата и преобразование обратно в число Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число. 😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string Swap(string s, int i0, int i1) {
        if (i0 == i1) return s;
        var chars = s.ToCharArray();
        var temp = chars[i0];
        chars[i0] = chars[i1];
        chars[i1] = temp;
        return new string(chars);
    }

    private List<string> list = new List<string>();

    private void Permute(string a, int l, int r) {
        if (l == r) {
            list.Add(a);
        } else {
            for (int i = l; i <= r; i++) {
                a = Swap(a, l, i);
                Permute(a, l + 1, r);
                a = Swap(a, l, i);
            }
        }
    }

    public int NextGreaterElement(int n) {
        string s = n.ToString();
        Permute(s, 0, s.Length - 1);
        list.Sort();
        int index = list.IndexOf(s);
        if (index != -1 && index < list.Count - 1) {
            int result = int.Parse(list[index + 1]);
            if (result <= int.MaxValue) return result;
        }
        return -1;
    }
}

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

Миграция в облако? Это легко! Собственная инфраструктура устарела или не справляется с нагрузками? Используйте облачные ресурсы! Эксперты Yandex Cloud помогут перейти в облако быстро, легко и безопасно. ✅ Мы полностью сопровождаем процесс. ✅ От вас — только инженер с доступом к инфраструктуре. ✅ Архитектура под ваши задачи, миграция и поддержка на каждом шагу — всё включено. ⚡Переходите в Yandex Cloud и забудьте о старом железе. А если успеете подать заявку до 31 декабря, мы покроем расходы на инженеров и тестовую инфраструктуру. Подать заявку #реклама 16+ yandex.cloud О рекламодателе Реклама на Яндексе

#medium Задача: 554. Brick Wall Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова. Нарисуйте вертикальную линию от верха до низа, пересекающую наименьшее количество кирпичей. Если ваша линия проходит по краю кирпича, то кирпич не считается пересеченным. Вы не можете нарисовать линию прямо по одному из двух вертикальных краев стены, так как в этом случае линия очевидно не пересечет ни одного кирпича. Дан двумерный массив wall, содержащий информацию о стене, верните минимальное количество пересеченных кирпичей после проведения такой вертикальной линии. Пример:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

👨‍💻 Алгоритм: 1⃣Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте массив pos, где pos[i] указывает на текущую позицию в i-ом ряду. 2⃣Пройдите по каждой возможной позиции для вертикальной линии (от 1 до общей ширины стены - 1). Для каждой позиции обновите массив pos, проверяя, пересекает ли линия границу кирпича. Если пересекает, увеличьте значение pos[i]. 3⃣Подсчитайте количество кирпичей, которые пересечет вертикальная линия для каждой возможной позиции, обновляя счетчик. Выберите минимальное количество пересеченных кирпичей из всех возможных позиций для вертикальной линии. 😎 Решение:

public class Solution {
    public int LeastBricks(IList<IList<int>> wall) {
        int[] pos = new int[wall.Count];
        int sum = 0, res = int.MaxValue;

        foreach (int el in wall[0])
            sum += el;

        while (sum != 0) {
            int count = 0;
            for (int i = 0; i < wall.Count; i++) {
                if (wall[i][pos[i]] != 0)
                    count++;
                else
                    pos[i]++;
                wall[i][pos[i]]--;
            }
            sum--;
            res = Math.Min(res, count);
        }

        return res;
    }
}

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

#hard Задача: 420. Strong Password Checker Пароль считается надежным, если выполняются следующие условия: в нем не менее 6 и не более 20 символов. он содержит не менее одной строчной буквы, не менее одной заглавной буквы и не менее одной цифры. он не содержит трех повторяющихся символов подряд (например, "Baaabb0" - слабый, а "Baaba0" - сильный). Учитывая строку пароля, верните минимальное количество шагов, необходимых для того, чтобы сделать пароль сильным. Если пароль уже сильный, верните 0. За один шаг можно: вставить один символ в пароль, удалить один символ из пароля или заменить один символ пароля другим символом. Пример:

Input: password = "a"
Output: 5

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

public class Solution {
    public int StrongPasswordChecker(string s) {
        int n = s.Length;
        bool hasLower = false, hasUpper = false, hasDigit = false;
        int repeatCount = 0;
        
        for (int i = 0; i < n;) {
            if (char.IsLower(s[i])) hasLower = true;
            if (char.IsUpper(s[i])) hasUpper = true;
            if (char.IsDigit(s[i])) hasDigit = true;
            
            int start = i;
            while (i < n && s[i] == s[start]) {
                i++;
            }
            repeatCount += (i - start) / 3;
        }
        
        int missingTypes = (hasLower ? 0 : 1) + (hasUpper ? 0 : 1) + (hasDigit ? 0 : 1);
        
        if (n < 6) {
            return Math.Max(missingTypes, 6 - n);
        } else if (n <= 20) {
            return Math.Max(missingTypes, repeatCount);
        } else {
            int excessChars = n - 20;
            int overLenReduction = 0;
            for (int i = 2; i < n && excessChars > 0; i++) {
                if (i % 3 == 2 && s[i] == s[i - 1] && s[i] == s[i - 2]) {
                    overLenReduction++;
                    excessChars--;
                }
            }
            repeatCount -= overLenReduction;
            return (n - 20) + Math.Max(missingTypes, repeatCount);
        }
    }
}

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

Аукцион выделенных серверов от Selectel! Популярные конфигурации выделенных серверов становятся дешевле в реальном времени. Успейте арендовать их, пока это не сделал кто-то другой!🏃‍♂️ Забронировать #реклама selectel.ru О рекламодателе

#medium Задача: 553. Optimal Division Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой. Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4". Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным. Верните соответствующее выражение, которое имеет максимальное значение в строковом формате. Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

👨‍💻 Алгоритм: 1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе. 2⃣Для каждой цифры первого числа: умножьте цифру второго числа на цифру первого числа и добавьте предыдущий перенос к результату умножения. Возьмите остаток от деления на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру к массиву currentResult. Разделите результат умножения на 10, чтобы получить новое значение переноса. 3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его. 😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    private List<int> AddStrings(List<int> num1, List<int> num2) {
        var ans = new List<int>();
        int carry = 0;
        int n1 = num1.Count;
        int n2 = num2.Count;

        for (int i = 0; i < Math.Max(n1, n2) + 1; ++i) {
            int digit1 = i < n1 ? num1[i] : 0;
            int digit2 = i < n2 ? num2[i] : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            ans.Add(sum % 10);
        }
        return ans;
    }

    private List<int> MultiplyOneDigit(string firstNumber, char secondNumberDigit, int numZeros) {
        var currentResult = new List<int>(new int[numZeros]);
        int carry = 0;

        foreach (char digit in firstNumber) {
            int multiplication = (secondNumberDigit - '0') * (digit - '0') + carry;
            carry = multiplication / 10;
            currentResult.Add(multiplication % 10);
        }
        if (carry != 0) {
            currentResult.Add(carry);
        }
        return currentResult;
    }

    public string Multiply(string firstNumber, string secondNumber) {
        if (firstNumber == "0" || secondNumber == "0") {
            return "0";
        }

        firstNumber = new string(firstNumber.Reverse().ToArray());
        secondNumber = new string(secondNumber.Reverse().ToArray());

        var ans = new List<int>(new int[firstNumber.Length + secondNumber.Length]);

        for (int i = 0; i < secondNumber.Length; ++i) {
            ans = AddStrings(MultiplyOneDigit(firstNumber, secondNumber[i], i), ans);
        }

        while (ans.Last() == 0) {
            ans.RemoveAt(ans.Count - 1);
        }

        var answer = new System.Text.StringBuilder();
        for (int i = ans.Count - 1; i >= 0; --i) {
            answer.Append(ans[i]);
        }

        return answer.ToString();
    }
}

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

#medium Задача: 419. Battleships in a Board Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров). Пример:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

👨‍💻 Алгоритм: 1⃣Пройдите по каждой клетке матрицы. 2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров. 3⃣Верните итоговый счетчик. 😎 Решение:

public class Solution {
    public int CountBattleships(char[][] board) {
        int m = board.Length;
        int n = board[0].Length;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

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

#medium Задача: 418. Sentence Screen Fitting Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом. Пример:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1

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

public class Solution {
    public int WordsTyping(string[] sentence, int rows, int cols) {
        string sentenceStr = string.Join(" ", sentence) + " ";
        int length = sentenceStr.Length;
        int count = 0;
        
        for (int i = 0; i < rows; i++) {
            count += cols;
            if (sentenceStr[count % length] == ' ') {
                count++;
            } else {
                while (count > 0 && sentenceStr[(count - 1) % length] != ' ') {
                    count--;
                }
            }
        }
        
        return count / length;
    }
}

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

✅️ GitHub теперь в Telegram! Подписывайтесь: @GitHub