C# | LeetCode

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

#medium Задача: 316. Remove Duplicate Letters Дана строка s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов. Пример:

Input: s = "bcabc"
Output: "abc"

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

public class Solution {
    public string RemoveDuplicateLetters(string s) {
        var stack = new Stack<char>();
        var seen = new HashSet<char>();
        var lastOccurrence = new Dictionary<char, int>();
        for (int i = 0; i < s.Length; i++) {
            lastOccurrence[s[i]] = i;
        }

        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (!seen.Contains(c)) {
                while (stack.Count > 0 && c < stack.Peek() && i < lastOccurrence[stack.Peek()]) {
                    seen.Remove(stack.Pop());
                }
                seen.Add(c);
                stack.Push(c);
            }
        }
        return new string(stack.Reverse().ToArray());
    }
}

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

#easy Задача: 404. Sum of Left Leaves Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 24

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

public class Solution {
    public int SumOfLeftLeaves(TreeNode root) {
        return Dfs(root, false);
    }
    
    private int Dfs(TreeNode node, bool isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return Dfs(node.left, true) + Dfs(node.right, false);
    }
}

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

Москвич 3 – надежно для вас и ваших увлечений Современный городской кроссовер Москвич 3. Ежемесячный платеж 17 500 рублей. Подробности уточняйте на официальном сайте moskvich.ru. Перейти на сайт Финансовые услуги оказывает: АО "Авто Финанс Банк", ПАО "Совкомбанк". #реклама moskvich.ru О рекламодателе

#hard Задача: 403. Frog Jump Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num. Пример:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true

👨‍💻 Алгоритм: 1⃣Инициализация и структура данных Создайте набор для хранения всех камней для быстрого доступа. Используйте динамическое программирование с помощью словаря для отслеживания достижимых позиций и возможных прыжков. 2⃣Итерация по камням Пройдитесь по каждому камню и для каждого возможного прыжка (k-1, k, k+1) проверьте, если он ведет на существующий камень. Если такой камень существует, добавьте его в набор возможных прыжков. 3⃣Проверка достижения последнего камня Если можно достичь последний камень с помощью одного из возможных прыжков, верните True. Если после всех итераций последний камень не достигнут, верните False.Формирование результата: Постройте итоговое число из цифр в стеке и удалите ведущие нули. 😎 Решение:

public class Solution {
    public bool CanCross(int[] stones) {
        var dp = new Dictionary<int, HashSet<int>>();
        foreach (var stone in stones) {
            dp[stone] = new HashSet<int>();
        }
        dp[0].Add(0);
        
        foreach (var stone in stones) {
            foreach (var jump in dp[stone]) {
                for (int step = jump - 1; step <= jump + 1; step++) {
                    if (step > 0 && dp.ContainsKey(stone + step)) {
                        dp[stone + step].Add(step);
                    }
                }
            }
        }
        
        return dp[stones[stones.Length - 1]].Count > 0;
    }
}

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

#medium Задача: 402. Remove K Digits Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num. Пример:

Input: num = "1432219", k = 3
Output: "1219"

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте стек для хранения цифр, которые будут образовывать минимальное число. 2⃣Обработка каждой цифры: Перебирайте каждую цифру в строке num. Если текущая цифра меньше верхней цифры в стеке и у вас есть еще возможность удалить цифры (k > 0), удалите верхнюю цифру из стека. Добавьте текущую цифру в стек. Удаление оставшихся цифр: Если после прохождения всей строки k еще больше нуля, удалите оставшиеся цифры из конца стека 3⃣Формирование результата: Постройте итоговое число из цифр в стеке и удалите ведущие нули. 😎 Решение:

public class Solution {
    public string RemoveKdigits(string num, int k) {
        Stack<char> stack = new Stack<char>();
        foreach (char digit in num) {
            while (k > 0 && stack.Count > 0 && stack.Peek() > digit) {
                stack.Pop();
                k--;
            }
            stack.Push(digit);
        }
        char[] resultArray = stack.ToArray();
        Array.Reverse(resultArray);
        string result = new string(resultArray).Substring(0, resultArray.Length - k).TrimStart('0');
        return result == "" ? "0" : result;
    }
}

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

Помощь в трудоустройстве в IT-сфере! В России из-за дефицита айтишников запустили бесплатную программу по обучению IT-специалистов. Теперь любой желающий может попробовать себя в IT с полного нуля и начать обучение бесплатно! Узнайте про дальнейшее трудоустройство в ведущие IT-компании для восполнения кадрового дефицита. Для этого нужно: - Перейти по ссылке - Заполнить анкету и ответить на вопросы (занимает менее 3 минут) - На основании ваших ответов вы сразу узнаете, подходит ли вам сфера IT и сможете ли вы в ней работать Перейти на сайт #реклама 16+ urban-university.ru О рекламодателе

#easy Задача: 401. Binary Watch Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа. Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

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

public class Solution {
    public IList<string> ReadBinaryWatch(int turnedOn) {
        var results = new List<string>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (CountBits(h) + CountBits(m) == turnedOn) {
                    results.Add($"{h}:{m:D2}");
                }
            }
        }
        return results;
    }

    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

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

#medium Задача: 400. Nth Digit Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]. Пример:

Input: n = 3
Output: 3

👨‍💻 Алгоритм: 1⃣Определение диапазона: Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.). Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра. 2⃣Нахождение конкретного числа: Когда определите диапазон, найдите точное число, содержащее n-ю цифру. Определите индекс цифры в этом числе. 3⃣Возвращение n-й цифры: Извлеките и верните n-ю цифру из найденного числа. 😎 Решение:

public class Solution {
    public int FindNthDigit(int n) {
        long length = 1, count = 9, start = 1;
        
        while (n > length * count) {
            n -= (int)(length * count);
            length++;
            count *= 10;
            start *= 10;
        }
        
        start += (n - 1) / length;
        string s = start.ToString();
        return s[(n - 1) % (int)length] - '0';
    }
}

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

ТОП-4 Курса по Программированию ⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. ✅Хотите стать программистом, но не знаете с какого языка начать? Помогаем разобраться в самых популярных и востребованных языках программирования. Подарок в конце подборки! Выбрать #реклама 16+ tutortop.ru О рекламодателе

#medium Задача: 399. Evaluate Division Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен. Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

👨‍💻 Алгоритм: 1⃣Создание графа: Представьте каждую переменную как узел в графе. Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]). Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]). 2⃣Поиск пути: Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj. Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj. Если путь не найден, верните -1.0. 3⃣Обработка запросов: Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        var graph = new Dictionary<string, Dictionary<string, double>>();

        for (int i = 0; i < equations.Count; i++) {
            string A = equations[i][0], B = equations[i][1];
            double value = values[i];
            if (!graph.ContainsKey(A)) graph[A] = new Dictionary<string, double>();
            if (!graph.ContainsKey(B)) graph[B] = new Dictionary<string, double>();
            graph[A][B] = value;
            graph[B][A] = 1.0 / value;
        }

        double Bfs(string start, string end) {
            if (!graph.ContainsKey(start) || !graph.ContainsKey(end)) return -1.0;
            var q = new Queue<(string, double)>();
            q.Enqueue((start, 1.0));
            var visited = new HashSet<string>();
            
            while (q.Count > 0) {
                var (current, curProduct) = q.Dequeue();
                if (current == end) return curProduct;
                visited.Add(current);
                foreach (var neighbor in graph[current]) {
                    if (!visited.Contains(neighbor.Key)) {
                        q.Enqueue((neighbor.Key, curProduct * neighbor.Value));
                    }
                }
            }
            return -1.0;
        }

        var results = new double[queries.Count];
        for (int i = 0; i < queries.Count; i++) {
            string C = queries[i][0], D = queries[i][1];
            results[i] = Bfs(C, D);
        }
        return results;
    }
}

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

#medium Задача: 398. Random Pick Index Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата. Пример:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

👨‍💻 Алгоритм: 1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования. 2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным. 3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса. 😎 Решение:

public class Solution {
    private int[] nums;
    private Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        this.random = new Random();
    }

    public int Pick(int target) {
        int count = 0;
        int result = -1;
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == target) {
                count++;
                if (random.Next(count) == count - 1) {
                    result = i;
                }
            }
        }
        return result;
    }
}

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

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

😎 База IT собеседований – твоё секретное оружие для успешного прохождения этапов отбора! Собеседования от реальных компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 230 собесов, чтобы ты мог подготовиться к интервью с уверенностью и успехом. 🎯 Присоединяйся к базе и прокачай свои шансы на успешное трудоустройство!

#medium Задача: 397. Integer Replacement К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1. Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

👨‍💻 Алгоритм: 1⃣Начните с данного числа n и выполните одну из следующих операций: Если n четное, замените n на n / 2. Если n нечетное, замените n на n + 1 или n - 1. 2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов. 3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат. 😎 Решение:

public class Solution {
    public int IntegerReplacement(int n) {
        Dictionary<long, int> memo = new Dictionary<long, int>();
        return Helper(n, memo);
    }
    
    private int Helper(long n, Dictionary<long, int> memo) {
        if (n == 1) return 0;
        if (memo.ContainsKey(n)) return memo[n];
        
        if (n % 2 == 0) {
            memo[n] = 1 + Helper(n / 2, memo);
        } else {
            memo[n] = 1 + Math.Min(Helper(n + 1, memo), Helper(n - 1, memo));
        }
        
        return memo[n];
    }
}

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

#hard Задача: 305. Number of Islands II Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0). Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию. Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу. Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой. Пример:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки. Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0. Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу. 2⃣Обработка позиций: Итерация по массиву positions. Для каждой позиции в positions: Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1]. Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count. Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1. 3⃣Определение количества островов: Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer. Верните answer. 😎 Решение

public class UnionFind {
    private int[] parent, rank;
    private int count;
    public UnionFind(int size) { parent = new int[size]; rank = new int[size]; Array.Fill(parent, -1); count = 0; }
    public void AddLand(int x) { if (parent[x] < 0) { parent[x] = x; count++; } }
    public bool IsLand(int x) { return parent[x] >= 0; }
    public int NumberOfIslands() { return count; }
    public int Find(int x) { return parent[x] != x ? parent[x] = Find(parent[x]) : x; }
    public void UnionSet(int x, int y) { int xset = Find(x), yset = Find(y); if (xset != yset) {
        if (rank[xset] < rank[yset]) parent[xset] = yset; else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; } }
}

public class Solution {
    public IList<int> NumIslands2(int m, int n, int[][] positions) {
        var dsu = new UnionFind(m * n);
        int[] x = { -1, 1, 0, 0 }, y = { 0, 0, -1, 1 };
        var answer = new List<int>();
        foreach (var pos in positions) {
            int land = pos[0] * n + pos[1];
            dsu.AddLand(land);
            for (int i = 0; i < 4; ++i) {
                int nx = pos[0] + x[i], ny = pos[1] + y[i], neighbor = nx * n + ny;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.IsLand(neighbor)) dsu.UnionSet(land, neighbor);
            }
            answer.Add(dsu.NumberOfIslands());
        }
        return answer;
    }
}

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

Продажи на автопилоте: настройка триггерных цепочек Как создать триггерные цепочки, которые сами работают на увеличение ваших продаж? 4 декабря CEO REES46 Михаил Кечинов проведёт вебинар для маркетологов и владельцев интернет-магазинов. Он поделится практическими советами и кейсами, как эффективно использовать автоматизацию маркетинга для повышения выручки и лояльности клиентов. 📚 Что вас ждёт на вебинаре: - Какие триггеры работают лучше всего в 2024 году. - Как настроить автоматические цепочки писем и сообщений. - Как измерить эффективность триггерных кампаний. Бонус для всех участников: готовые шаблоны триггерных цепочек и чек-лист для их быстрого внедрения. 📅 Дата: 4 декабря 2024 года ⚡ Время: 19:00 по МСК Не упустите шанс вывести свой бизнес на новый уровень — зарегистрируйтесь на вебинар прямо сейчас! Зарегистрироваться #реклама 16+ rees46.ru О рекламодателе

#medium Задача: 542. 01 Matrix Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки. Расстояние между двумя соседними ячейками равно 1. Пример:

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

👨‍💻 Алгоритм: 1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen. 2⃣Выполните BFS: Пока очередь не пуста, извлекайте текущие row, col, steps из очереди. Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen. 3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix. 😎 Решение:

using System.Collections.Generic;

public class Solution {
    private int m;
    private int n;
    private int[][] directions = new int[][] {
        new int[] {0, 1},
        new int[] {1, 0},
        new int[] {0, -1},
        new int[] {-1, 0}
    };

    public int[][] UpdateMatrix(int[][] mat) {
        m = mat.Length;
        n = mat[0].Length;
        int[][] matrix = new int[m][];
        bool[][] seen = new bool[m][];
        Queue<int[]> queue = new Queue<int[]>();

        for (int i = 0; i < m; i++) {
            matrix[i] = new int[n];
            seen[i] = new bool[n];
            for (int j = 0; j < n; j++) {
                matrix[i][j] = mat[i][j];
                if (matrix[i][j] == 0) {
                    queue.Enqueue(new int[] {i, j, 0});
                    seen[i][j] = true;
                }
            }
        }

        while (queue.Count > 0) {
            int[] curr = queue.Dequeue();
            int row = curr[0], col = curr[1], steps = curr[2];

            foreach (var direction in directions) {
                int nextRow = row + direction[0], nextCol = col + direction[1];
                if (IsValid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
                    seen[nextRow][nextCol] = true;
                    queue.Enqueue(new int[] {nextRow, nextCol, steps + 1});
                    matrix[nextRow][nextCol] = steps + 1;
                }
            }
        }

        return matrix;
    }

    private bool IsValid(int row, int col) {
        return 0 <= row && row < m && 0 <= col && col < n;
    }
}

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

#hard Задача: 588. Design In-Memory File System Спроектируйте структуру данных, которая симулирует файловую систему в памяти. Реализуйте класс FileSystem: FileSystem() Инициализирует объект системы. List<String> ls(String path) Если path является путем к файлу, возвращает список, содержащий только имя этого файла. Если path является путем к директории, возвращает список имен файлов и директорий в этой директории. Ответ должен быть в лексикографическом порядке. void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их. void addContentToFile(String filePath, String content) Если filePath не существует, создает файл, содержащий заданный контент. Если filePath уже существует, добавляет заданный контент к исходному содержимому. String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath. Пример:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

👨‍💻 Алгоритм: 1⃣ Инициализация файловой системы: Создайте класс FileSystem, который будет содержать вложенный класс File. Класс File будет представлять либо файл, либо директорию, содержать флаг isfile, словарь files и строку content. 2⃣ Обработка команд: Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом. Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их. Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его. Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути. 3⃣ Обработка путей и работа с файлами/директориями: Используйте метод split для разделения пути на составляющие и навигации по дереву директорий и файлов. Для каждой команды выполняйте соответствующие операции по созданию, чтению или записи содержимого файлов и директорий. 😎 Решение:

public class FileSystem {
    class File {
        public bool isFile = false;
        public Dictionary<string, File> files = new Dictionary<string, File>();
        public string content = "";
    }

    File root = new File();

    private File Navigate(string path) {
        File t = root;
        if (path != "/") {
            var dirs = path.Split('/');
            foreach (var dir in dirs) {
                if (!string.IsNullOrEmpty(dir)) {
                    if (!t.files.ContainsKey(dir)) {
                        t.files[dir] = new File();
                    }
                    t = t.files[dir];
                }
            }
        }
        return t;
    }

    public IList<string> Ls(string path) {
        var t = Navigate(path);
        if (t.isFile) return new List<string> { path.Substring(path.LastIndexOf("/") + 1) };
        var res = new List<string>(t.files.Keys);
        res.Sort();
        return res;
    }

    public void Mkdir(string path) {
        Navigate(path);
    }

    public void AddContentToFile(string filePath, string content) {
        var t = Navigate(filePath);
        t.isFile = true;
        t.content += content;
    }

    public string ReadContentFromFile(string filePath) {
        return Navigate(filePath).content;
    }
}

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе