Задача: 996. Number of Squareful Arrays
Сложность: hard

Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].

Пример:

Input: nums = [1,17,8]
Output: 2

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

1⃣Генерация перестановок:
Сгенерируйте все возможные перестановки массива nums.
Для каждой перестановки проверьте, является ли она квадратной.

2⃣Проверка квадратности:
Для каждой перестановки проверьте, является ли сумма каждой пары соседних элементов совершенным квадратом.
Для этого используйте функцию для проверки, является ли число совершенным квадратом.

3⃣Подсчет квадратных перестановок:
Подсчитайте количество перестановок, которые являются квадратными, и верните это значение.

😎 Решение:

public class Solution {
    public int NumSquarefulPerms(int[] nums) {
        Array.Sort(nums);
        var used = new bool[nums.Length];
        var result = new HashSet<string>();
        var path = new List<int>();
        Backtrack(nums, used, path, result);
        return result.Count;
    }
    
    private void Backtrack(int[] nums, bool[] used, List<int> path, HashSet<string> result) {
        if (path.Count == nums.Length) {
            if (IsSquareful(path)) {
                result.Add(string.Join(",", path));
            }
            return;
        }
        
        for (int i = 0; i < nums.Length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            path.Add(nums[i]);
            used[i] = true;
            Backtrack(nums, used, path, result);
            path.RemoveAt(path.Count - 1);
            used[i] = false;
        }
    }
    
    private bool IsSquareful(List<int> perm) {
        for (int i = 0; i < perm.Count - 1; i++) {
            int sum = perm[i] + perm[i + 1];
            int root = (int)Math.Sqrt(sum);
            if (root * root != sum) return false;
        }
        return true;
    }
}

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

Задача: 58. Length of Last Word
Сложность: easy

Дана строка s, содержащая слова и пробелы. Нужно вернуть длину последнего слова.

Пример:

Input: s = "Hello World"  
Output: 5  
Explanation: Последнее слово — "World", его длина 5.  

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

1⃣Пройти строку с конца, игнорируя пробелы.

2⃣Найдя последнее слово, считать его длину.

3⃣Вернуть длину последнего слова.

😎 Решение:

public class Solution {
    public int LengthOfLastWord(string s) {
        int length = 0, i = s.Length - 1;

        while (i >= 0 && s[i] == ' ') i--; // Пропуск пробелов
        while (i >= 0 && s[i] != ' ') {   // Подсчет длины слова
            length++;
            i--;
        }

        return length;
    }
}

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

Задача: 258. Add Digits
Сложность: easy

Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1⃣Инициализируйте переменную digital_root значением 0.

2⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3⃣Верните значение digital_root.

😎 Решение:

public class Solution {
    public int AddDigits(int num) {
        int digital_root = 0;
        while (num > 0) {
            digital_root += num % 10;
            num /= 10;
            if (num == 0 && digital_root > 9) {
                num = digital_root;
                digital_root = 0;
            }
        }
        return digital_root;
    }
}

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

Задача: 247. Strobogrammatic Number II
Сложность: medium

Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.

Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: n = 2
Output: ["11","69","88","96"]

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

1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.

2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.

3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private List<List<char>> reversiblePairs = new List<List<char>> {
        new List<char>{'0', '0'}, new List<char>{'1', '1'}, 
        new List<char>{'6', '9'}, new List<char>{'8', '8'}, new List<char>{'9', '6'}
    };
    
    public List<string> GenerateStroboNumbers(int n, int finalLength) {
        if (n == 0) {
            return new List<string> { "" };
        }
        
        if (n == 1) {
            return new List<string> { "0", "1", "8" };
        }
        
        List<string> prevStroboNums = GenerateStroboNumbers(n - 2, finalLength);
        List<string> currStroboNums = new List<string>();
        
        foreach (string prevStroboNum in prevStroboNums) {
            foreach (List<char> pair in reversiblePairs) {
                if (pair[0] != '0' || n != finalLength) {
                    currStroboNums.Add(pair[0] + prevStroboNum + pair[1]);
                }
            }
        }
        
        return currStroboNums;
    }
    
    public List<string> FindStrobogrammatic(int n) {
        return GenerateStroboNumbers(n, n);
    }
}

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

Задача: 916. Word Subsets
Сложность: medium

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2.

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎 Решение:

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

public class Solution {
    public IList<string> WordSubsets(string[] words1, string[] words2) {
        int[] maxCount = new int[26];
        foreach (string word in words2) {
            int[] count = GetCount(word);
            for (int i = 0; i < 26; i++) {
                maxCount[i] = Math.Max(maxCount[i], count[i]);
            }
        }

        List<string> result = new List<string>();
        foreach (string word in words1) {
            int[] count = GetCount(word);
            if (IsUniversal(count, maxCount)) {
                result.Add(word);
            }
        }

        return result;
    }

    private int[] GetCount(string word) {
        int[] count = new int[26];
        foreach (char c in word) {
            count[c - 'a']++;
        }
        return count;
    }

    private bool IsUniversal(int[] count, int[] maxCount) {
        for (int i = 0; i < 26; i++) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 553. Optimal Division
Сложность: medium

Дано целочисленный массив 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();
    }
}

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

Задача: 1114. Print in Order
Сложность: easy

Предположим, у нас есть класс:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Один и тот же экземпляр Foo будет передан трем разным потокам. Поток A вызовет first(), поток B вызовет second(), и поток C вызовет third(). Спроектируйте механизм и модифицируйте программу, чтобы гарантировать, что second() выполняется после first(), а third() выполняется после second().

Примечание:
Мы не знаем, как потоки будут планироваться в операционной системе, даже если числа в вводе подразумевают порядок выполнения. Формат ввода, который вы видите, в основном предназначен для обеспечения полноты наших тестов.

Пример:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

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

1⃣Инициализация переменных:
Инициализируйте координационные переменные firstJobDone и secondJobDone, чтобы указать, что задания еще не выполнены.

2⃣Функция first():
В этой функции нет зависимости, поэтому можно сразу приступить к выполнению задания. В конце функции обновите переменную firstJobDone, чтобы указать, что первое задание выполнено.

3⃣Функции second() и third():
В функции second() проверьте статус firstJobDone. Если она не обновлена, подождите, иначе переходите к выполнению второго задания. В конце функции обновите переменную secondJobDone, чтобы отметить завершение второго задания.
В функции third() проверьте статус secondJobDone. Аналогично функции second(), подождите сигнала secondJobDone перед тем, как приступить к выполнению третьего задания.

😎 Решение:

using System;
using System.Threading;

public class Foo {
    private SemaphoreSlim firstJobDone = new SemaphoreSlim(0, 1);
    private SemaphoreSlim secondJobDone = new SemaphoreSlim(0, 1);

    public void First(Action printFirst) {
        printFirst();
        firstJobDone.Release();
    }

    public void Second(Action printSecond) {
        firstJobDone.Wait();
        printSecond();
        secondJobDone.Release();
    }

    public void Third(Action printThird) {
        secondJobDone.Wait();
        printThird();
    }
}

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

Задача: 1361. Validate Binary Tree Nodes
Сложность: easy

У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.

Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.

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

Пример:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

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

1⃣Проверка количества родителей для каждого узла:
Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.

2⃣Поиск корневого узла и проверка на единственное дерево:
Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов.

3⃣Проверка на достижение всех узлов:
Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.
😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] parents = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                if (++parents[leftChild[i]] > 1) {
                    return false;
                }
            }
            if (rightChild[i] != -1) {
                if (++parents[rightChild[i]] > 1) {
                    return false;
                }
            }
        }
        
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == 0) {
                if (root == -1) {
                    root = i;
                } else {
                    return false;
                }
            }
        }
        
        if (root == -1) {
            return false;
        }
        
        HashSet<int> visited = new HashSet<int>();
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            if (!visited.Add(node)) {
                return false;
            }
            if (leftChild[node] != -1) {
                queue.Enqueue(leftChild[node]);
            }
            if (rightChild[node] != -1) {
                queue.Enqueue(rightChild[node]);
            }
        }
        
        return visited.Count == n;
    }
}

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

Задача: 868. Binary Gap
Сложность: easy

Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0.

Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3.

Пример:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

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

1⃣Создайте список A индексов i, таких что в двоичном представлении числа n i-й бит установлен в 1.

2⃣Используйте список A, чтобы найти максимальное расстояние между соседними значениями. Для этого пройдите по списку и вычислите разницу между каждым соседним элементом.

3⃣Верните найденное максимальное расстояние.

😎 Решение:

public class Solution {
    public int BinaryGap(int N) {
        int[] A = new int[32];
        int t = 0;
        for (int i = 0; i < 32; ++i)
            if (((N >> i) & 1) != 0)
                A[t++] = i;

        int ans = 0;
        for (int i = 0; i < t - 1; ++i)
            ans = Math.Max(ans, A[i + 1] - A[i]);
        return ans;
    }
}

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

Задача: 1234. Replace the Substring for Balanced String
Сложность: medium

Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.

Пример:

Input: s = "QWER"
Output: 0

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

1⃣Проверка баланса:
Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0.

2⃣Подсчет частоты символов:
Подсчитаем количество каждого символа в строке s.

3⃣Использование скользящего окна:
Используем метод двух указателей (скользящее окно) для нахождения минимальной подстроки, которую можно заменить, чтобы строка стала сбалансированной.
Начнем с окна, которое захватывает всю строку, и будем постепенно уменьшать его, проверяя при каждом шаге, становится ли строка сбалансированной.

😎 Решение:

public class Solution {
    public int BalancedString(string s) {
        int n = s.Length;
        var count = new Dictionary<char, int>();
        foreach (char c in s) {
            if (count.ContainsKey(c)) count[c]++;
            else count[c] = 1;
        }
        int target = n / 4;

        bool IsBalanced() {
            return count['Q'] <= target && count['W'] <= target && count['E'] <= target && count['R'] <= target;
        }

        if (IsBalanced()) return 0;

        int minLength = n;
        int left = 0;

        for (int right = 0; right < n; right++) {
            count[s[right]]--;
            while (IsBalanced()) {
                minLength = Math.Min(minLength, right - left + 1);
                count[s[left]]++;
                left++;
            }
        }

        return minLength;
    }
}

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

Задача: 1496. Path Crossing
Сложность: easy

Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.

Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

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

1⃣Инициализация переменных:
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями.
Инициализировать множество visited с начальной точкой (0, 0).
Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path:
Для каждого символа c в path получить значения (dx, dy) из moves[c].
Обновить координаты: добавить dx к x и dy к y.
Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true.
Добавить текущую точку (x, y) в visited.

3⃣Возврат результата:
Если ни одна точка не пересекалась, вернуть false.

😎 Решение:

public class Solution {
    public bool IsPathCrossing(string path) {
        var moves = new Dictionary<char, (int, int)> {
            {'N', (0, 1)}, {'S', (0, -1)}, {'E', (1, 0)}, {'W', (-1, 0)}
        };
        var visited = new HashSet<(int, int)> { (0, 0) };
        int x = 0, y = 0;

        foreach (char c in path) {
            var move = moves[c];
            x += move.Item1;
            y += move.Item2;
            if (visited.Contains((x, y))) {
                return true;
            }
            visited.Add((x, y));
        }

        return false;
    }
}

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

Задача: 424. Longest Repeating Character Replacement
Сложность: medium

Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз.

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

Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo.

😎 Решение:

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int lo = 1;
        int hi = s.Length + 1;

        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (CanMakeValidSubstring(s, mid, k)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    private bool CanMakeValidSubstring(string s, int substringLength, int k) {
        int[] freqMap = new int[26];
        int maxFrequency = 0;
        int start = 0;
        for (int end = 0; end < s.Length; end++) {
            freqMap[s[end] - 'A']++;

            if (end + 1 - start > substringLength) {
                freqMap[s[start] - 'A']--;
                start++;
            }

            maxFrequency = Math.Max(maxFrequency, freqMap[s[end] - 'A']);
            if (substringLength - maxFrequency <= k) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

1⃣Пройти по всей сетке и для каждой башни (ячейки) посчитать начальную площадь поверхности: добавить площадь верхней и нижней граней, а также четыре боковые грани.

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

3⃣Просуммировать все значения площадей для получения итоговой площади поверхности.

😎 Решение:

public int SurfaceArea(int[][] grid) {
    int n = grid.Length;
    int area = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                area += (grid[i][j] * 4) + 2;
            }
            if (i > 0) {
                area -= Math.Min(grid[i][j], grid[i-1][j]) * 2;
            }
            if (j > 0) {
                area -= Math.Min(grid[i][j], grid[i][j-1]) * 2;
            }
        }
    }
    return area;
}

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

Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy

Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.

Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

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

1⃣Создать словарь для подсчета частоты каждого числа в массиве deck.

2⃣Найти наибольший общий делитель (НОД) всех частот.

3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы.

😎 Решение:

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

public class Solution {
    public bool HasGroupsSizeX(int[] deck) {
        var count = deck.GroupBy(x => x).ToDictionary(g => g.Key, g => g.Count());
        var freqValues = count.Values.ToList();
        var g = freqValues.Aggregate(Gcd);
        return g > 1;
    }

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

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

Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

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

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями.

3⃣Начните обход в глубину (DFS).

😎 Решение:

public class Solution {
    private int[] Dfs(int node, int parent, Dictionary<int, List<int>> adj, char[] labels, int[] ans) {
        int[] nodeCounts = new int[26];
        nodeCounts[labels[node] - 'a'] = 1;

        if (!adj.ContainsKey(node))
            return nodeCounts;

        foreach (int child in adj[node]) {
            if (child == parent) {
                continue;
            }
            int[] childCounts = Dfs(child, node, adj, labels, ans);
            for (int i = 0; i < 26; i++) {
                nodeCounts[i] += childCounts[i];
            }
        }

        ans[node] = nodeCounts[labels[node] - 'a'];
        return nodeCounts;
    }

    public int[] CountSubTrees(int n, int[][] edges, string labels) {
        var adj = new Dictionary<int, List<int>>();
        foreach (var edge in edges) {
            if (!adj.ContainsKey(edge[0])) {
                adj[edge[0]] = new List<int>();
            }
            if (!adj.ContainsKey(edge[1])) {
                adj[edge[1]] = new List<int>();
            }
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }

        var ans = new int[n];
        Dfs(0, -1, adj, labels.ToCharArray(), ans);
        return ans;
    }
}

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

Задача: 1535. Find the Winner of an Array Game
Сложность: medium

Дан целочисленный массив arr из различных целых чисел и целое число k.

Игра будет проводиться между первыми двумя элементами массива (т.е. arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов.

Верните число, которое выиграет игру.

Гарантируется, что у игры будет победитель.

Пример:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

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

1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.

2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.

3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.

😎 Решение:

public class Solution {
    public int GetWinner(int[] arr, int k) {
        int maxElement = arr[0];
        Queue<int> queue = new Queue<int>();
        for (int i = 1; i < arr.Length; i++) {
            maxElement = Math.Max(maxElement, arr[i]);
            queue.Enqueue(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (queue.Count > 0) {
            int opponent = queue.Dequeue();
            
            if (curr > opponent) {
                queue.Enqueue(opponent);
                winstreak++;
            } else {
                queue.Enqueue(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

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

Задача: 667. Beautiful Arrangement II
Сложность: medium

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

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

1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎 Решение:

public class Solution {
    public int[] ConstructArray(int n, int k) {
        int[] answer = new int[n];
        int left = 1, right = n;
        
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0) {
                answer[i] = left++;
            } else {
                answer[i] = right--;
            }
        }
        
        if (k % 2 == 0) {
            for (int i = k + 1; i < n; i++) {
                answer[i] = right--;
            }
        } else {
            for (int i = k + 1; i < n; i++) {
                answer[i] = left++;
            }
        }
        
        return answer;
    }
}

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

Задача: 985. Sum of Even Numbers After Queries
Сложность: medium

Дан целочисленный массив nums и массив queries, где queries[i] = [vali, indexi].

Для каждого запроса i, сначала примените nums[indexi] = nums[indexi] + vali, затем выведите сумму четных значений nums.

Верните целочисленный массив answer, где answer[i] - это ответ на i-й запрос.

Пример:

Input: nums = [1], queries = [[4,0]]
Output: [0]

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

1⃣Инициализация переменных:
Завести переменную evenSum для хранения суммы всех четных чисел в массиве nums.
Пройти по массиву nums и вычислить начальное значение evenSum, сложив все четные числа в nums.

2⃣Обработка запросов:
Создать пустой массив result для хранения ответов на каждый запрос.
Для каждого запроса [val, index] из массива queries выполнить следующие действия:
Если значение nums[index] четное, вычесть его из evenSum.
Обновить nums[index] добавлением val.
Если новое значение nums[index] четное, добавить его к evenSum.
Добавить текущее значение evenSum в массив result.

3⃣Возврат результата:
Вернуть массив result, содержащий ответы на все запросы.

😎 Решение:

public class Solution {
    public int[] SumEvenAfterQueries(int[] nums, int[][] queries) {
        int evenSum = nums.Where(x => x % 2 == 0).Sum();
        int[] result = new int[queries.Length];

        for (int i = 0; i < queries.Length; i++) {
            int val = queries[i][0], index = queries[i][1];
            if (nums[index] % 2 == 0) {
                evenSum -= nums[index];
            }
            nums[index] += val;
            if (nums[index] % 2 == 0) {
                evenSum += nums[index];
            }
            result[i] = evenSum;
        }
        
        return result;
    }
}

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

Задача: 789. Escape The Ghosts
Сложность: medium

Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами.

Каждый ход вы и все привидения можете независимо выбирать перемещение на 1 единицу в любом из четырех основных направлений: север, восток, юг или запад, или оставаться на месте. Все действия происходят одновременно.

Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом.

Верните true, если можно сбежать независимо от того, как движутся привидения, иначе верните false.

Пример:

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

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

1⃣Проверьте, что наше таксическое расстояние до цели меньше, чем расстояние от любого привидения до цели.

2⃣Если это так, мы можем гарантированно добраться до цели раньше любого привидения.

3⃣Если привидение может добраться до цели раньше нас или одновременно с нами, побег невозможен.

😎 Решение:

public class Solution {
    public bool EscapeGhosts(int[][] ghosts, int[] target) {
        int playerDistance = Taxi(new int[] {0, 0}, target);
        foreach (var ghost in ghosts) {
            if (Taxi(ghost, target) <= playerDistance) {
                return false;
            }
        }
        return true;
    }

    private int Taxi(int[] P, int[] Q) {
        return Math.Abs(P[0] - Q[0]) + Math.Abs(P[1] - Q[1]);
    }
}

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

Задача: 662. Maximum Width of Binary Tree
Сложность: medium

Дан корень бинарного дерева, верните максимальную ширину данного дерева.

Максимальная ширина дерева - это максимальная ширина среди всех уровней.

Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.

Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

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

1⃣Инициализация:
Создайте очередь для хранения узлов и их позиций на уровне.
Начните с корневого узла и его позиции 0.

2⃣Обработка каждого уровня:
Для каждого уровня дерева получите его узлы и их позиции.
Вычислите ширину уровня как разницу между максимальной и минимальной позициями плюс один.

3⃣Обновление максимальной ширины:
Обновите максимальную ширину, если текущая ширина уровня больше.

😎 Решение:

using System;
using System.Collections.Generic;

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

public class Solution {
    public int WidthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        int maxWidth = 0;
        Queue<(TreeNode node, int pos)> queue = new Queue<(TreeNode, int)>();
        queue.Enqueue((root, 0));
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            int firstPos = queue.Peek().pos;
            for (int i = 0; i < levelSize; i++) {
                var (node, pos) = queue.Dequeue();
                if (node.left != null) queue.Enqueue((node.left, 2 * pos));
                if (node.right != null) queue.Enqueue((node.right, 2 * pos + 1));
            }
            maxWidth = Math.Max(maxWidth, queue.Peek().pos - firstPos + 1);
        }
        
        return maxWidth;
    }
}

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

Задача: 1246. Palindrome Removal
Сложность: hard

Вам дан целочисленный массив arr. За один ход вы можете выбрать палиндромный подмассив arr[i], arr[i + 1], ..., arr[j], где i <= j, и удалить этот подмассив из данного массива. Обратите внимание, что после удаления подмассива элементы слева и справа от него перемещаются, чтобы заполнить пробел, образовавшийся в результате удаления. Верните минимальное количество ходов, необходимое для удаления всех чисел из массива.

Пример:

Input: arr = [1,2]
Output: 2

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

1⃣Базовый случай:
Если подмассив состоит из одного элемента, то его удаление займет 1 ход, поэтому dp[i][i] = 1.

2⃣Рекурсивный случай:
Если arr[i] == arr[j], то мы можем удалить их в одном ходе, если подмассив arr[i+1...j-1] можно удалить за dp[i+1][j-1] ходов, тогда dp[i][j] = dp[i+1][j-1] (если удалим подмассив arr[i+1...j-1] и затем удалим arr[i] и arr[j]).

3⃣В противном случае, минимальное количество ходов для удаления подмассива arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подмассивов arr[i...k] и arr[k+1...j], где i <= k < j. То есть, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех k от i до j-1.

😎 Решение:

using System;

public class Solution {
    public int MinMovesToDelete(int[] arr) {
        int n = arr.Length;
        int[,] dp = new int[n, n];

        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i, j] = length > 2 ? dp[i + 1, j - 1] : 1;
                } else {
                    dp[i, j] = int.MaxValue;
                    for (int k = i; k < j; k++) {
                        dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k + 1, j]);
                    }
                }
            }
        }
        return dp[0, n - 1];
    }
}

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