Задача: 1429. First Unique Number
Сложность: medium

У вас есть очередь целых чисел, необходимо извлечь первый уникальный элемент из очереди.

Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.

Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

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

1⃣Инициализируйте объект FirstUnique с числами в очереди, добавляя их в структуру данных для отслеживания уникальности и порядка.

2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет.

3⃣Метод add добавляет новое значение в очередь. Если значение уже было добавлено ранее, обновляет его статус уникальности и удаляет его из множества уникальных значений, если оно больше не уникально.

😎 Решение:

public class FirstUnique {
    private LinkedList<int> queue;
    private Dictionary<int, LinkedListNode<int>> map;
    private HashSet<int> duplicates;

    public FirstUnique(int[] nums) {
        queue = new LinkedList<int>();
        map = new Dictionary<int, LinkedListNode<int>>();
        duplicates = new HashSet<int>();
        foreach (var num in nums) {
            Add(num);
        }
    }

    public int ShowFirstUnique() {
        if (queue.Count > 0) {
            return queue.First.Value;
        }
        return -1;
    }

    public void Add(int value) {
        if (duplicates.Contains(value)) {
            return;
        }

        if (map.ContainsKey(value)) {
            queue.Remove(map[value]);
            map.Remove(value);
            duplicates.Add(value);
        } else {
            var node = new LinkedListNode<int>(value);
            queue.AddLast(node);
            map[value] = node;
        }
    }
}

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

"Ты че, дурак?" – базовая реакция сеньора на тех, кто покупает IT курсы

Дело в том, что онлайн школы создают инкубаторных айтишников, которые в реальных условиях попросту зависнут.

Трушные ребята учатся на жизненных каналах для айтишников. Вот топ-5 от тимлида из Сбера:

⚙️ Технолоджия – для тех, кто хочет быть в курсе новостей в айти

🧠 Ai-чница – способы превратить нейросети в заработок $$$

💻 ИИ тебя заменит! – тенденции айти рынка в связке с нейросетями

4️⃣ Войти в IT – тонны бесплатного обучения для прогеров

😄 IT индус – сборник айти мемов

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing
Сложность: hard

Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим.

В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j].

Если нет способа сделать arr1 строго возрастающим, верните -1.

Пример:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

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

1⃣ Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение.

2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]).

3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1.

😎 Решение:

public class Solution {
    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
        Array.Sort(arr2);
        int answer = Dfs(0, -1, arr1, arr2);
        return answer < 2001 ? answer : -1;
    }

    Dictionary<(int, int), int> dp = new Dictionary<(int, int), int>();

    private int Dfs(int i, int prev, int[] arr1, int[] arr2) {
        if (i == arr1.Length) {
            return 0;
        }
        var key = (i, prev);
        if (dp.ContainsKey(key)) {
            return dp[key];
        }

        int cost = 2001;
        if (arr1[i] > prev) {
            cost = Dfs(i + 1, arr1[i], arr1, arr2);
        }

        int idx = Array.BinarySearch(arr2, prev + 1);
        if (idx < 0) {
            idx = ~idx;
        }
        if (idx < arr2.Length) {
            cost = Math.Min(cost, 1 + Dfs(i + 1, arr2[idx], arr1, arr2));
        }

        dp[key] = cost;
        return cost;
    }
}

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

Задача: 983. Minimum Cost For Tickets
Сложность: medium

Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365.

Билеты на поезд продаются тремя различными способами:

однодневный билет продаётся за costs[0] долларов,
семидневный билет продаётся за costs[1] долларов, и
тридцатидневный билет продаётся за costs[2] долларов.
Билеты позволяют путешествовать указанное количество дней подряд.

Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8.
Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days.

Пример:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

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

1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days.

2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его.

3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    private HashSet<int> isTravelNeeded = new HashSet<int>();
    
    private int Solve(int[] dp, int[] days, int[] costs, int currDay) {
        if (currDay > days[days.Length - 1]) {
            return 0;
        }
        
        if (!isTravelNeeded.Contains(currDay)) {
            return Solve(dp, days, costs, currDay + 1);
        }
        
        if (dp[currDay] != -1) {
            return dp[currDay];
        }
        
        int oneDay = costs[0] + Solve(dp, days, costs, currDay + 1);
        int sevenDay = costs[1] + Solve(dp, days, costs, currDay + 7);
        int thirtyDay = costs[2] + Solve(dp, days, costs, currDay + 30);
        
        dp[currDay] = Math.Min(oneDay, Math.Min(sevenDay, thirtyDay));
        return dp[currDay];
    }
    
    public int MincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.Length - 1];
        int[] dp = new int[lastDay + 1];
        for (int i = 0; i <= lastDay; i++) {
            dp[i] = -1;
        }
        
        foreach (int day in days) {
            isTravelNeeded.Add(day);
        }
        
        return Solve(dp, days, costs, 1);
    }
}

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

Задача: 861. Score After Flipping Matrix
Сложность: medium

Вам дана бинарная матрица grid размером m x n.

Ход состоит из выбора любой строки или столбца и переключения каждого значения в этой строке или столбце (т.е. изменение всех 0 на 1, и всех 1 на 0).

Каждая строка матрицы интерпретируется как двоичное число, и счёт матрицы — это сумма этих чисел.

Верните наивысший возможный счёт после выполнения любого количества ходов (включая ноль ходов).

Пример:

Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

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

1⃣Инициализируйте переменные: m и n для количества строк и столбцов в grid, score для хранения максимального счёта матрицы. Пройдитесь по первому столбцу матрицы. Если элемент равен 0, переверните всю строку.

2⃣Пройдитесь по матрице от второго до последнего столбца. Для каждого столбца посчитайте количество нулей (countZero). Если количество нулей больше, переверните весь столбец.

3⃣Пройдитесь по модифицированной матрице. Для каждого элемента добавьте его к score, сдвинув влево на значение текущего столбца. Верните score, который хранит наивысший возможный счёт матрицы.

😎 Решение:

public class Solution {
    public int MatrixScore(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;

        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] ^= 1;
                }
            }
        }

        for (int j = 1; j < n; j++) {
            int countZero = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 0) {
                    countZero++;
                }
            }
            if (countZero > m / 2) {
                for (int i = 0; i < m; i++) {
                    grid[i][j] ^= 1;
                }
            }
        }

        int score = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    score += 1 << (n - j - 1);
                }
            }
        }

        return score;
    }
}

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