Условие

Дан массив из n пар pairs гдеpairs[i] = [lefti, righti] и lefti < righti.

Пара p2 = [c, d] следует за парой p1 = [a, b] если b < c. Таким образом можно сформировать цепочку пар.

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

Вам не обязательно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.

Пример 1:

Ввод: pairs = [[1,2],[2,3],[3,4]]
Вывод: 2
Объяснение: Самая длинная цепочка [1,2] -> [3,4].

Пример 2:

Ввод: pairs = [[1,2],[7,8],[4,5]]
Вывод: 3
Объяснение: Самая длинная цепочка [1,2] -> [4,5] -> [7,8].

Ограничения:

• n == pairs.length
• 1 <= n <= 1000
• -1000 <= lefti < righti <= 1000

Решение

Итак, представим наши пары в виде графа, где вершина - это одна пара, и две вершины соединяются ребром, если две пары могут образовать цепочку. То есть, если есть пары pair1 и pair2 и pair1[1] < pair2[0], то будет ребро от pair1 до pair2.
Например, массив [[1,2],[7,8],[4,5]]

Далее я буду употреблять слова "пара" и "вершина" как синонимы.
Если мы будем отмечать у каждой вершины длину максимальной цепочки, которая оканчивается этой вершиной, то следующуя вершина будет иметь длину цепочки + 1:

Если две цепочки с длинами N и M оканчиваются на двух вершинах, и у этих двух вершин один и тот же сосед, то чтобы составить максимальную цепочку, нужно выбрать цепочку с наибольшей длиной:

Кажется можно сделать такой алгоритм:

1. Пометить все вершины единицами (цепочка из одной вершины всегда есть).
2. Пройтись по всем вершинам:
• У каждой вершины взять длину цепочки, которая у неё сейчас (длину цепочки, которая оканчивается этой вершиной).
• Пройтись по соседям вершины. Каждому соседу проставить длину цепочки + 1, если у соседа длина его текущей цепочки (цепочки, которая оканчивается этим соседом) меньше чем длина цепочки взятой вершиы + 1

Но этот алгоритм обламывается на таком случае, когда у нас есть массив
[[4,5], [7,8],[1,2]]
Мы сначала возьмем вершину [4,5] возьмем её длину (изначально у всех по единице). Пройдем от неё к соседу [7,8], поставим соседу длину + 1, то есть 2.
Потом возьмем вершину [7,8] от неё нет никаких вершин дальше, потому что нет пары, у которой первый элемент больше 8. Потом пройдем к паре [1,2] от неё перейдем к соседу [4,5], и проставим соседу длину 2. Получится, что максимальная длина равна якобы 2, хотя она на самом деле 3.
[[1,2],[4,5],[7,8]].
Порядок обхода имеет значение. Если мы начинаем с вершины A, мы должны быть уверены, что сейчас у вершины максимальная длина цепочки, которая на ней оканчивается. Если длина цепочки у вершины поменялась, то надо перестроить всех соседей, соседей соседей, и т.д. дальше. Если мы посмотрим на ограничения к задаче, то увидим, что у pair[lefti, righti] lefti < righti.
Если мы отсортируем массив по первому или последнему элементу пары, то мы гарантировано будем начинать с пары, у которой не будет другой пары, которая могла бы стоять перед ней, и если на очередной итерации мы перешли к новой паре, то в этот момент у неё уже будет максимальная вершина.

Итак, алгоритм дополняется сортировкой:

1. Отсортировать массив пар (по первому или последнему числу в паре).
2. Пометить все вершины единицами (цепочка из одной вершины всегда есть).
3. Пройтись по всем вершинам:
• У каждой вершины взять длину цепочки, которая у неё сейчас (длину цепочки, которая оканчивается этой вершиной).
• Пройтись по соседям вершины. Каждому соседу проставить длину цепочки + 1, если у соседа длина его текущей цепочки (цепочки, которая оканчивается этим соседом) меньше чем длина цепочки взятой вершиы + 1

Кстати, наш алгоритм прохода немного похож на Алгоритм Дейкстры, только там вычисляется длина минимальной цепочки, а здесь максимальной.

Нужно ли строить реальный граф? Заводить класс для вершины, ссылку на соседей? Необязательно.
Можно воспользоваться одномерным массивом dp (dynamic programming)
dp[i] будет содержать длину цепочки, которая оканчивается парой i (в уже отсортированном массиве).
Итак, сортируем массив.
Создаем массив dp и заполняем его единицами (цепочки из одной вершины).
Проходим по исходному уже отсотированному массиву, идем от каждой пары правее и смотрим соседей. Сосед проверяетя if'ом pairs[j][0] > pairs[i][1].
Если вершина является соседом, то выставляем соседу текущую длину + 1, если текущая длина + 1 больше чем та длина, которая записана у соседа сейчас.
Попутно сразу считаем максимальную длину.

Полный код такой:

public class Solution {  
    public int FindLongestChain(int[][] pairs) {
        Array.Sort(pairs, (a, b) => a[0].CompareTo(b[0]));
        var dp = new int[pairs.Length];
        Array.Fill(dp, 1);
        var max = 1;
        for (var i = 0; i < dp.Length; i++)
        {
            for (var j = i + 1; j < dp.Length; j++)
            {
                if (pairs[j][0] > pairs[i][1])
                {
                    dp[j] = Math.Max(dp[j], dp[i] + 1);
                    max = Math.Max(max, dp[j]);
                }
            }
        }
        
        return max;
    }
}

Условие

Дан массив чисел nums который может содержать дубликаты, верни все возможные подмножества (the power set).

Результат не должен содержать повторяющихся подмножеств. Верните результат в любом порядке.

Пример 1:

Ввод: nums = [1,2,2]
Вывод: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Пример 2:

Ввод: nums = [0]
Вывод: [[],[0]]

Ограничения:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Решение

Мы видим из примера, что здесь не учитывается порядок, а учитваются сами элементы, если мы добавили [1,2], то мы не добавляем [2,1].

Возьмем массив [1, 2, 1].
Если мы добавим в результат первый и третий элемент ([1, 2]), а потом добавим второй и третий элемент ([2, 1]), то последний случай будет считаться как дубликат.

Чтобы узнать, является ли [2,1] дубликатом для [1,2], мы можем отсортировать, числа в этих массивах по возрастанию: [1,2] [1,2], и тогда нам будет легче сравнивать два массива.

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

Поэтому первым делом отсортируем исходный массив.
Array.Sort(nums);

Итак, мы формируем очередное подмножество ([], [1], [1, 2], и т.д.)
Проверяем, а было ли добавлено такое же ранее, если да, то не добавляем.
Если нет, то добавляем.

Как нам проверить, что подмножество было добавлено ранее?
Один из вариантов пробегать по текущему результату в поиске дубликата. Это сложность O(n).
Другой вариант - воспользоваться хэш-сетом.
Заведем переменную типа HashSet<string>. Назовем её added ("добавлено").
Текущее подмножество мы переводим в строку, соединяя числа через делиметр, (например, через запятую), чтобы избежать такого случая, когда у нас есть, например, массив [-1, 0, -10], и выборки [-1, 0] и [-10] преобразуются в одну и ту же строку "-10". Далее мы ищем эту строку в хэш-сете, если строка там есть, значит текущее подмножество не добавляем в результат. Если строки нет, то подмножество добавляем в результат, а её строковое представление добавляем в хэш-сет added. В этом случае будет сложность проверки дубликата за O(1). (если не считать преобразование в строку, но это быстро).

Другое решение воспользоваться HashSet<List<int>>, но указать, как вычислять хэш-функцию и как проводить сравнение элементов.

HashSet<List<int>> result = new HashSet<List<int>>(EqualityComparer<List<int>>.Create((a, b) => a.SequenceEqual(b), (a) =>
{
    var hashCode = 0;
    foreach (var item in a)
    {
        hashCode += item.GetHashCode();
    }
    return hashCode;
}));

Но этот вариант требует хорошей памяти документации C#, если решение писать не в IDE.

Сделаем рекурсивную функцию.
Она будет проходить по элементам массива. Как только она дошла до конца массива (это базовый случай рекурсии), у неё должно быть сформировано очередное подмножество ([], [1], [1,2] и т.д.), это подмножество преобразуется в строку путем конкатенации элементов через делиметр (запятую). Полученная строка ищется в хэш-сете, если она там есть, то просто выходим, если есть полученное множество добавляем в результат, а его строковое представление добавляем в хэш-сет.
Не в базовом случае функция будет добавлять элемент в подмножество, вызывать себя рекурсивно, потом будет удалять элемент из подмножества и снова вызывать себя рекурсивно. Таким образом, каждый элемент будет в одних множествах добавлен, в других - нет.

Итого, полный код такой:

public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums)
    {
        HashSet<string> added = new();
        IList<IList<int>> result = new List<IList<int>>();
        Array.Sort(nums);
        Solve(0, nums, [], result, added);
        return result.Select(v => (IList<int>)v).ToList();
    }

    public void Solve(int i, int[] nums, List<int> subset, IList<IList<int>> result, HashSet<string> added)
    {
        if (i == nums.Length)
        {
            var subsetString = string.Join(",", subset);
            if (added.Contains(subsetString))
            {
                return;
            }
            added.Add(subsetString);
            result.Add([.. subset]);
            return;
        }
        subset.Add(nums[i]);
        Solve(i + 1, nums, subset, result, added);
        subset.RemoveAt(subset.Count - 1);
        Solve(i + 1, nums, subset, result, added);
    }
}

Код работает. Решение на Литкоде проходит. Но можно ли ускорить?
Да.
Давайте посмотрим на такое множество:
1,1,1,1,2,2,2,2,3,3,3,3
мы увидим, что в ответе у нас должны быть комбинации
[], [3], [3,3], [3,3,3], [3,3,3,3], [2,3,3,3,3],[2,2,3,3,3,3], [2,2,2,3,3,3,3], [2,2,2,2,3,3,3,3],
[1,2,2,2,2,3,3,3,3]...[1,1,1,1,2,2,2,2,3,3,3,3], [1,3,3,3,3], [1,1,3,3,3,3],[1,1,1,3,3,3,3][1,1,1,13,3,3,3] и другие множества
Разобъем числа на группы одинаковых чисел.
Возьмем группу чисел 1,1,1,1.
Есть множества, где нет единицы.
Есть множества, где одна единица
Есть множества, где две единицы
Есть множества, где три единицы
Есть множества, где четыре единицы
Тоже самое с другими группами.

Поэтому перепишем функцию Solve таким образом.
Мы будем искать начало группы одинаковых чисел: [1,1,1,1], [2,2,2,2] и т.д.
Добавляем одно число из группы, вызываем функцию Solve рекурсивно.
Добавляем другое число из группы, вызываем функцию Solve рекурсивно.
и .т.д.
Потом удаляем группу и вызываем функцию Solve рекурсивно.
Нам уже не нужен HashSet.

Полный код такой:

public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        Array.Sort(nums);
        Solve(0, nums, [], result);
        return result;
    }
    public void Solve(int indexOfGroupStart, int[] nums, List<int> subset, IList<IList<int>> result)
    {
        if (indexOfGroupStart == nums.Length)
        {
            result.Add([..subset]);
            return;
        }
                
        var groupNumber = nums[indexOfGroupStart];//число группы
        var indexOfNextGroupStart = indexOfGroupStart + 1;//ищем начало следующей группы
        for (; indexOfNextGroupStart < nums.Length; indexOfNextGroupStart++)
        {
            if (nums[indexOfNextGroupStart] != groupNumber)
            {
                break;
            }
        }

        var groupSize = indexOfNextGroupStart - indexOfGroupStart;//количество элементов в группе
        Solve(indexOfNextGroupStart, nums, subset, result);//запускаем Solve с пустой группой.
        for (var i = 0; i < groupSize; i++)
        {
            subset.Add(groupNumber);//добавляем по одному
            Solve(indexOfNextGroupStart, nums, subset, result);//запускаем Solve рекурсивно
        }
        subset.RemoveRange(subset.Count - groupSize, groupSize);//удаляем группу
    }
}

Условие

Последовательность n-битного кода Грея — это последовательность из 2ⁿ целых чисел, в которой:

• Каждое числое в диапазоне [0, 2n - 1] включительно
• Первое число 0,
• Каждое целое число встречается в последовательности не более одного раза,
• Двоичное представление каждой пары соседних целых чисел отличается ровно на один бит, и
• Двоичное представление первого и последнего целых чисел отличается ровно на один бит.

Дано число n, верните любуюдопустимую последовательность n-битного кода Грея.

Пример 1:

Ввод: n = 2
Вывод: [0,1,3,2]
Объяснение:
Двоичное представление of [0,1,3,2] is [00,01,11,10].
- 00 and 01 отличается на один бит
- 01 and 11 отличается на один бит
- 11 and 10 отличается на один бит
- 10 and 00 отличается на один бит
[0,2,3,1] также валидная последовательность кода Грея, двоичное представление которой [00,10,11,01].
- 00 and 10 отличается на один бит
- 10 and 11 отличается на один бит
- 11 and 01 отличается на один бит
- 01 and 00 отличается на один бит

Пример 2:

Ввод: n = 1
Вывод: [0,1]

Ограничения:

• 1 <= n <= 16

Решение

Если n = 3, то у нас числа от 0 до 111 в двоичном представлении.

Подготовим переменную для результата
var result = new List<int>();

Подготовим переменную для 2^n:
var max = (1 << n);

Подготовим массив для определения, использовано ли число ранее:
var used = new bool[max];

Индексы этого массива числа от 0 до max - 1, т.е. от 0 до 2^n - 1. Если по индексу, например, 5 стоит false, то это значит число 5 ещё не было в последовательности, если true, то было, и мы должны его пропустить. По умолчанию все значения false.

Положим в результат число 0, и сделаем отметку, что оно заюзано.

used[0] = true;
result.Add(0);

Далее мы будем идти по оставшимся числам:
for (var j = 1; j < max; j++)

Как нам найти следующее число?
Мы должны изменить один бит в последнем числе, после этого мы получим потенциально новое число. Мы должны проверить по массиву used, оно использовано ранее или нет. Если да, то его пропускаем и меняем другой бит.

Положим последнее число в переменную num (сначала это 0).
var num = 0;

Проходим по всем битам этого числа
for (var i = 0; i < n; i++)

Делаем маску из одного бита на месте i и всех нулей, т.е. 001b, 010b, 100b и т.д.
(1 << i)

Битово умножаем на эту маску последнее число:
var bit = num & (1 << i);

Если полученный результат больше 0, то значит на i'м месте у нас 1, и надо поменять его на 0.

Если результат 0, то значит на i'м месте у нас 0, и надо поменять его на 1.
с помощью xor c 1 мы можем поменять 1 на 0.
1 ^ 1 = 0

С помощью битового or, мы меняем 0 на 1:

0 | 1 = 1

Пока код получается таким:

var num = 0;//последнее число
for (var j = 1; j < max; j++)
{
    for (var i = 0; i < n; i++)
    {
    var bit = (num & (1 << i));
    var nextNumber = num;
    
    if (bit > 0)
    {
        nextNumber ^= 1 << i; 
    }
    else
    {
        nextNumber |= 1 << i;
    }
}

Теперь надо проверить заюзано ли число:
Если нет, то надо добавить его в результат, а в num положить последнее число.

if (!used[nextNumber])
{
    result.Add(nextNumber);//добавляем в результат
    used[nextNumber] = true;//число заюзано, больше его не повторять
    num = nextNumber;//новое последнее число
    break;//больше не меняем биты
}

Итого, код такой:

public class Solution {
    public IList<int> GrayCode(int n) {
        var result = new List<int>();
        var max = (1 << n);
        var used = new bool[max];
        used[0] = true;
        result.Add(0);
        var num = 0;
        for (var j = 1; j < max; j++)
        {
          for (var i = 0; i < n; i++)
          {
            var bit = (num & (1 << i));
            var nextNumber = num;
            
            if (bit > 0)
            {
                nextNumber ^= 1 << i; 
            }
            else
            {
                nextNumber |= 1 << i;
            }
            
            if (!used[nextNumber])
            {
                result.Add(nextNumber);
                used[nextNumber] = true;
                num = nextNumber;
                break;
            }
          }
        }
        return result;
    }
}

Да, есть короткое решение, если знаешь особенности кода Грея.

public class Solution {
    public IList<int> GrayCode(int n) 
    {
        int count = 1 << n; // 2^n
        var result = new int[count];
        
        for (int i = 0; i < count; i++) 
        {
            result[i] = i ^ (i >> 1);
        }
        
        return result;
    }
}

Но о нём вряд ли догадаешься сам, если не знаешь. Особенно на собесе.

Условие

Последовательность трансформации от слова beginWord до слова endWord с использованием словаряwordList это последовательность слов beginWord -> s1 -> s2 -> ... -> sk такая что:

• Каждая соседняя пара слов отличается одной буквой.
• Каждый si для 1 <= i <= k есть в wordList. ЗаметьеbeginWord необязательно будет вwordList.
• sk == endWord

Дано два слова: beginWord иendWord, и словарь wordList, верните все самые короткие последовательности трансформации от beginWord доendWord, или пустой список если такая последовательность не существует. Каждая последовательность должна быть возвращена как лист слов [beginWord, s1, s2, ..., sk].

Пример 1:

Ввод: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Вывод: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Объяснение: Здесь 2 самых коротких последовательностей трансформации:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Пример 2:

Ввод: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Вывод: []
Объяснение: Слово "cog" не в wordList, поэтому здесь нет валидной последовательности трансформации.

Ограничения:

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 500
• wordList[i].length == beginWord.length
• beginWord, endWord, иwordList[i] состоят из маленьких английских букв.
• beginWord != endWord
• Все слова в wordList уникальны.
• Сумма все самых коротких последовательностей трансформации не превышает 10^5.

Решение

Код который, который нужно дополнить выглядит вот так:

public Solution
{
  public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) 
  {
  }
}

нам нужно вернуть IList<IList<string>> (лист листов)
beginWord может содержаться, а может и нет в wordList, поэтому подготовим список всех уникальных слов из wordList включая слово beginWord.

var set = new HashSet<string>(wordList);
set.Add(beginWord);

Проверим, что если конечное слово не содержится в общем списке, то мы сразу выходим.

if (!set.Contains(endWord))
{
	return [];
}

Чтобы найти кратчайший путь от слова А, до слова Б, построим граф, где узел будет слово. Нам надо найти кратчайший путь от А до Б, при этом помним, что по условию задачи соседние слова должны отличаться только на один символ.

Заведем узел для графа.

public class Node    
{        
   public string Word {get; set;} = null;        
   public List<Node> Neighbors {get; set;} = [];        
}

Word - это слово
List<Node> Neighbors - это список всех соседей узла.
Так как в последовательности трансформации два соседних слова должны отличаться только на один символ, то это значит, что слова соседей одного узла должны отличаться от слова этого узла только одним символом.

Создадим вспомогательную функцию, которая возвращает true, если слова отличаются только одним символом, иначе - false.

public bool IsDiffOnlyByOneChar(string word1, string word2)
{ 
    var countDiff = 0;
    for (var i = 0; i < word1.Length; i++)
    {
          if (word1[i] != word2[i])
          {
            countDiff++;
            if (countDiff > 1)
            {
              return false;
            }
       }
    }
    return countDiff == 1;
}

Построим граф, где соседними узлами какого-то узла будут узлы со словом, отличающимся только на один символ от слова этого узла.

Но один узел может быть соседом сразу нескольких узлов, поэтому будем запоминать уже созданные узлы в словаре map:
var map = new Dictionary<string, Node>();

где ключ слово, а value - узел, его содержащий. И так, построим граф:

var map = new Dictionary<string, Node>();        
foreach (var word in set)
{
    Node currentNode = null;
    if (!map.TryGetValue(word, out currentNode))
    {
        map[word] = new Node()
        {
            Word = word
        };
        currentNode = map[word];
    }

    foreach (var otherWord in set)
    {
        if (IsDiffOnlyByOneChar(word, otherWord))
        {
            Node neighborNode = null;
            if (!map.TryGetValue(otherWord, out neighborNode))
            {
                map[otherWord] = new Node
                {
                    Word = otherWord
                };
                neighborNode = map[otherWord];
            }
            currentNode.Neighbors.Add(neighborNode);
        }
    }
}

Теперь нам надо стартовать от узла со словом beginWord и идти до узла со словом endWord.

Проход будет таким

Каждая итерация отделена пунктирной линией.

Примерный код такой (он нерабочий):

var queue = new Queue<Node>();//очередь в которую будут класться соседи
queue.Enqueue(map[beginWord]);//кладем первый узел
while (queue.Count() > 0)
{
    var cnt = queue.Count();
    for (var i = 0; i < cnt; i++)
    {
        //вытаскиваем первый узел на первой итерации
        //на всех последующих итерациях вытаскиваем соседей
        var node = queue.Dequeue();
        if (node.Word == endWord)
        {         
            //дошли до конечного узла
        }
        
        //проходимся по соседям
        foreach (var neighbor in node.Neighbors)
        {                    
            queue.Enqueue(nextNode);
        }                
    }
}

Но нужно решить две проблемы. Первая - надо избежать зацикливания. Ведь если узел Б сосед А, то и наоборот узел А является соседом узла Б. А также зацикливание может быть через несколько узлов.

Введем в узел свойство int Cnt.
Для первого узла и первой итерации оно будет равно нулю.
Для соседей первого узла (т.е. при второй итерации), оно будет равно 1.
Для соседей соседей первого узла (третья итерация), оно будет равно 2.
и т.д.
Итак, если узел А имеет значение Cnt == N, то сосед узла Б должен иметь значение Cnt == N + 1. Если так окажется, что у узла Б будет сосед В, который будет иметь соседа А, то при переходе от узла В к соседнему узлу (узлу А), мы должны проверить, а не установлено ли у него Cnt. Если оно установлено и уже меньше или равно чем Cnt текущего узла, то значит, если мы зайдем в этот узел, мы зациклимся.

Итак, класс Node обрастает ещё одним свойством:

public class Node    
{        
   public string Word {get; set;} = null;        
   public List<Node> Neighbors {get; set;} = [];   
   public int Cnt {get;set;} = int.MaxValue;
}

По умолчанию Cnt = int.MaxValue, чтобы можно было таким if'ом проверить, стоить ли заходить в узел или нет:
if (neighbor.Cnt <= node.Cnt)

Если условие выполняется, то значит мы уже были в neighbor, и поэтому пропускаем этот узел. По условию задачи у нас не более 501 узла (500 слов wordList и одно слово beginWord), так что Cnt не может достигнуть int.MaxValue в процессе обхода.
Итого, код обхода получается таким:

var queue = new Queue<Node>();//очередь в которую будут класться соседи
map[beginWord].Cnt = 0;
queue.Enqueue(map[beginWord]);//кладем первый узел
while (queue.Count() > 0)
{
    var cnt = queue.Count();
    for (var i = 0; i < cnt; i++)
    {
        //вытаскиваем первый узел на первой итерации
        //на всех последующих итерациях вытаскиваем соседей
        var node = queue.Dequeue();
        if (node.Word == endWord)
        {         
            //дошли до конечного узла
        }
        
        //проходимся по соседям
        foreach (var neighbor in node.Neighbors)
        { 
            if (neighbor.Cnt <= node.Cnt)
            {
                continue;//пропускаем узел
            }
            neighbor.Cnt = node.Cnt + 1;                  
            queue.Enqueue(nextNode);
        }                
    }
}

Но есть вторая проблема, два разных узла могут ссылаться на один и тот же узел. Если ничего не сделать, то на следующей итерации мы можем достать этот узел дважды, и дважды добавить в очередь его соседей. Что в итоге может привести к багам, когда будем строить цепочки трансформации, они будут дублироваться (и приводит, я проверил :-)). Поэтому при обработке узлов в итерации всех соседей будем добавлять не сразу в очередь, а в HashSet, а потом из HashSet в очередь:

var nextNodes = new HashSet<Node>();
var queue = new Queue<Node>();//очередь в которую будут класться соседи
map[beginWord].Cnt = 0;
queue.Enqueue(map[beginWord]);//кладем первый узел
while (queue.Count() > 0)
{
    var cnt = queue.Count();
    nextNodes.Clear();//подготавливаем set для очередных соседей
    for (var i = 0; i < cnt; i++)
    {
        //вытаскиваем первый узел на первой итерации
        //на всех последующих итерациях вытаскиваем соседей
        var node = queue.Dequeue();
        if (node.Word == endWord)
        {         
            //дошли до конечного узла
        }
        
        //проходимся по соседям
        foreach (var neighbor in node.Neighbors)
        { 
            if (neighbor.Cnt <= node.Cnt)
            {
                continue;//пропускаем узел
            }
            neighbor.Cnt = node.Cnt + 1;                  
            nextNodes.Add(neighbor);
        }                
    }
    
    //кладем очередних соседей, исключая дубликаты
    foreach (var nextNode in nextNodes)
    {    
         queue.Enqueue(nextNode);
    }
}

Окей, зацикливание исключили, проход в один и тот же узел исключили. Дошли до конечного узла, а дальше-то что? Нам надо теперь раскрутить путь от endWord до beginWord обратно. Путей может быть несколько.
Как узнать путь обратно?
Введем новое поле List<Node> Back {get; set;}, которое будет указывать на узлы из которого можно прийти в этот узел.

public class Node
{
    public string Word {get; set;} = null;
    public List<Node> Back = [];
    public List<Node> Neighbors {get; set;} = [];
    public int Cnt {get; set;} = int.MaxValue;
}

Разница между Back и Neighbors в том, что Neighbors - это соседи вообще, а Back содержит только те узлы, которые попадут в трансформацию: beginWord -> s1 -> s2 -> ... -> endWord

Итак, теперь обход такой:

var nextNodes = new HashSet<Node>();
var queue = new Queue<Node>();
map[beginWord].Cnt = 0;
queue.Enqueue(map[beginWord]);
while (queue.Count() > 0)
{
    var cnt = queue.Count();
    nextNodes.Clear();
    for (var i = 0; i < cnt; i++)
    {
        var node = queue.Dequeue();
        if (node.Word == endWord)
        {         
            //дошли до конца
        }
        
        foreach (var neighbor in node.Neighbors)
        {                    
            if (neighbor.Cnt <= node.Cnt)
            {
                continue;
            }
            neighbor.Back.Add(node);//записываем путь назад
            neighbor.Cnt = node.Cnt + 1;
            nextNodes.Add(neighbor);
        }                
    }
    foreach (var nextNode in nextNodes)
    {
        queue.Enqueue(nextNode);
    }
}

Итак, мы подходим к концовке.
У нас есть узел node c Word == endWord, у этого узла есть Back со списком узлов, которые отличаются на одну букву и которые участвуют в трансформации, и у этих узлов тоже есть свои свойства Back.

Нужно идти перебором по всем узлам списка Back, для каждого узла из этого списка идти перебором по всем узлам его списка Back, и т.д.

Заведем переменную для результата:

var result = new List<IList<string>>();

Заведем вспомогательную функцию Solve, которая собирается все пути от endWord до beginWord, переворачивает их и добавляет в результат:

//Node текущий узел (endWord -> sk -> s2 -> s1 -> beginWord)
//result результат
//текущий путь в словах List<string> path = endWord, sk, s2, s1, beginWord
public void Solve(Node node, IList<IList<string>> result, List<string> path, 
string beginWord)
{
    //дошли до конечного узла, рекурсия здесь останавливается
    if (node.Word == beginWord)
    {
        //добавили слово
        path.Add(beginWord);
        //сделаю копию. Копия нужна, так как path может быть задействован
        //где-то ещё.
        List<string> copyPath = [..path];
        //перевернули путь
        copyPath.Reverse();
        //добавили в результат
        result.Add(copyPath);
        //удалили последнее слово из результата
        //нужно для возврата назад на несколько слов
        //некоторые пути могут частично совпадать
        //endWord -> a -> b -> d
        //endword -> c -> b -> d
        path.RemoveAt(path.Count - 1);
        return;
    }
    
    //добавили очередное слово в путь
    path.Add(node.Word);
    //перебор всех последующих слов в nodeBak
    foreach (var backNode in node.Back)
    {
        Solve(backNode, result, path, beginWord);
    }
    //сделали возврат.
    path.RemoveAt(path.Count - 1);
}

Это "перебор с возвратами", по-английски - "BackTracking".

Так вот, полное решение такое:

public class Solution 
{
    public class Node
    {
        public string Word {get; set;} = null;
        public List<Node> Back = [];
        public List<Node> Neighbors {get; set;} = [];
        public int Cnt {get; set;} = int.MaxValue;
    }

    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
        var set = new HashSet<string>(wordList);
        set.Add(beginWord);
        
        if (!set.Contains(endWord))
        {
            return [];
        }

        //строим граф
        var map = new Dictionary<string, Node>();        
        foreach (var word in set)
        {
            Node currentNode = null;
            if (!map.TryGetValue(word, out currentNode))
            {
                map[word] = new Node()
                {
                    Word = word
                };
                currentNode = map[word];
            }

            foreach (var otherWord in set)
            {
                //сосед? добавляем
                if (IsDiffOnlyByOneChar(word, otherWord))
                {
                    Node neighborNode = null;
                    if (!map.TryGetValue(otherWord, out neighborNode))
                    {
                        map[otherWord] = new Node
                        {
                            Word = otherWord
                        };
                        neighborNode = map[otherWord];
                    }
                    currentNode.Neighbors.Add(neighborNode);
                }
            }
        }
        
        //обход графа в ширину
        //чтобы не обходить соседа дважды, если он сосед двух узлво
        var nextNodes = new HashSet<Node>();
        var queue = new Queue<Node>();
        //у первого узла Cnt = 0
        map[beginWord].Cnt = 0;
        queue.Enqueue(map[beginWord]);
        var result = new List<IList<string>>();
        while (queue.Count() > 0)
        {
            //подготавливаем соседей текущих узлов для следующей итерации
            nextNodes.Clear();
            while (queue.Count() > 0)
            {
                var node = queue.Dequeue();
                //дошли до конечного узла?
                if (node.Word == endWord)
                {
                    //раскручиваем пути назад         
                    Solve(node, result, [], beginWord);
                    return result;
                }
                
                foreach (var neighbor in node.Neighbors)
                {              
                    //уже проходили этот узел?      
                    if (neighbor.Cnt <= node.Cnt)
                    {
                        continue;
                    }
                    //Путь назад
                    neighbor.Back.Add(node);
                    //Метка, чтобы не зациклиться
                    neighbor.Cnt = node.Cnt + 1;
                    nextNodes.Add(neighbor);
                }                
            }
            //подготавливаем новые узлы для следующей итерации
            foreach (var nextNode in nextNodes)
            {
                queue.Enqueue(nextNode);
            }
        }
        return [];
    }
    
    //Перебор с возвратами
    public void Solve(Node node, IList<IList<string>> result, List<string> path, string beginWord)
    {
        if (node.Word == beginWord)
        {
            path.Add(beginWord);
            List<string> copyPath = [..path];
            copyPath.Reverse();
            result.Add(copyPath);
            path.RemoveAt(path.Count - 1);
            return;
        }

        path.Add(node.Word);
        foreach (var backNode in node.Back)
        {
            Solve(backNode, result, path, beginWord);
        }
        path.RemoveAt(path.Count - 1);
    }

    public bool IsDiffOnlyByOneChar(string word1, string word2)
    {
        var countDiff = 0;
        for (var i = 0; i < word1.Length; i++)
        {
            if (word1[i] != word2[i])
            {
                countDiff++;
                if (countDiff > 1)
                {
                    return false;
                }
            }
        }
        return countDiff == 1;
    }
}

Условие

Дано число n, вернитеtrue Если оно степень тройки. Иначе, верните false.

Число n степень тройки, если есть число x такое, что n == 3^x.

Пример 1:

Ввод: n = 27
Вывод: true
Explanation: 27 = 3^3

Пример 2:

Ввод: n = 0
Вывод: false
Объяснение: Нет x, чтобы 3^x = 0.

Пример 3:

Ввод: n = -1
Вывод: false
Объяснение: Нет x, чтобы 3^x = -1.

Ограничения:

• -231 <= n <= 231 - 1

Дополнительно: Можешь ли ты это решить без циклов/рекурсии?

Решение

Обычное решение такое:

public class Solution {
    public bool IsPowerOfThree(int n) {
        while (n > 1)
        {
            if (n % 3 != 0)
            {
                return false;
            }
            n /= 3;
        }
        return n == 1;
    }
}

А есть ли необычное решение? Да, есть.

3 - это простое число (делится только на себя и на единицу).

Если представим, некую степень тройки, как:

3 * 3 * 3 * 3 * 3 * 3 * 3...

то увидим, что оно тоже делится только на степень 3. На 3, или на 3 * 3 (9), или на 3 * 3 * 3 (27), и т.д.

Диапазон значений у нас от int.MinValue до int.MaxValue. Понятно, что отрицательные числа и 0 нам не нужны. Итого, остается диапазон от единицы до int.MaxValue. Если мы найдем такую максимальную степень тройки (пусть будет называться она max), что входит в этот дипазон, то мы можем определить, является ли n степеню 3-ки так:

max % n == 0

Если n не будет степень 3, то max не будет делиться на неё.

Как найти этот max?

Узнаем степень 3, чтобы получить int.MaxValue:

var power = Math.Log(int.MaxValue, 3);

Мы узнали, такое x, что 3^x = int.MaxValue
Понятно, что это какое-то дробное число.
Отбросим дробную часть:

var power = Math.Truncate(Math.Log(int.MaxValue, 3))

Теперь возведем 3 в эту степень.

var max = Math.Pow(3, power);

Одно из решение такое:

public class Solution {
    public bool IsPowerOfThree(int n) {
        if (n <= 0)
        {
            return false;
        }
        var power = Math.Truncate(Math.Log(int.MaxValue, 3));
        var max = Math.Pow(3, power);
        return max % n == 0;
    }
}

Если кто не знал, то на Литкоде можно выводить в консоль. выведем max:

Console.WriteLine(max);

Получим 1162261467, если выведем power, то получим 19. Итак, максимальная степень тройки в диапазоне от 1 до int.MaxValue - это 3^19.

Итого, решение может быть в одну строчку.

public class Solution {
    private const int MaxPowerOf3 = 1162261467;
    public bool IsPowerOfThree(int n) {
        return n > 0 && MaxPowerOf3 % n == 0;
    }
}

Условие

Дано число n, верни true, если оно степень двойки, Иначе - false.

Число n степень двойки, если есть число x такое, что n == 2^x.

Пример 1:

Ввод: n = 1
Вывод: true
Объяснение: 2^0 = 1

Пример 2:

Ввод: n = 16
Вывод: true
Объяснение: 2^4 = 16

Пример 3:

Ввод: n = 3
Вывод: false

Ограничения:

• -2^31 <= n <= 2^31 - 1

Дополнительно: Можете ли вы решить это без циклов и рекурсии?

Решение

Можно решить просто делением на 2, и не забывая проверять остаток отделения на 2.

public class Solution {
    public bool IsPowerOfTwo(int n) {
        while (n > 1)
        {
            if (n % 2 != 0)
            {
                return false;
            }
            n /= 2;
        }
        return n == 1;
    }
}

Сложность O(logN). Если точнее, то логарифм от N по основанию 2. Мы можем опускать основание логарифма, если оно константа.

Можно ли это решить за O(1)? Да, можно.
Рассмотрим n в двоичном виде.
Если n - степень двойки, то в двоичном виде это будет 1 и какое-то количество нулей. Например, 8 = 1000b, 16 = 10000b, 64 = 1000000b и т.д.
Как узнать, что единица у нас только одна?
Рассмотрим число n - 1.
Если n = 8, то n - 1 = 7 = 111b, если n = 16, то n - 1 = 15 = 1111b.
Итак, получается, что если n - степень двойки, то n - 1, это такое число, где в двоичном виде стоит 0, где в n стоит единица, и где стоят единицы, где в n были нули. n - 1 получается инверсией числа n (если n - степень двойки).

Таким образом, для определения является ли число степенью двойки можно было бы использовать n & (n - 1) == 0
Однако, есть такое число:
1000 0000 0000 0000 0000 0000 0000 0000
Это int, и это -2147483648 или по-другому int.MinValue
И его не надо учитывать.
Если у нас знаковый int, то старший бит используется для знака, поэтому в итоге будет решение такое:

public class Solution {
    public bool IsPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

Ещё одно решение такое:

public class Solution {
    public bool IsPowerOfTwo(int n) {
       return n > 0 && int.PopCount(n) == 1;
    }
}

PopCount - это метод для подсчета числа единиц в битовом представлении.

Давайте разберемся почему.

Сначала вспомним, как происходит алгоритм быстрой сортировки.

Он разделяется на три этапа:

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

Например, алгоритм быстрой сортировки может быть реализован так (так делать не надо, ниже будет понятно почему):

class QuickSort
{
    static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));
        QuickSortAlgorithm(arr, 0, arr.Length - 1);
        Console.WriteLine("Отсортированный массив: " + string.Join(", ", arr));
    }

    static void QuickSortAlgorithm(int[] arr, int low, int high)
    {
        if (low < high)
        {
            // Находим правильную позицию опорного элемента
            int pi = Partition(arr, low, high);

            // Рекурсивно сортируем элементы до и после опорного
            QuickSortAlgorithm(arr, low, pi - 1);
            QuickSortAlgorithm(arr, pi + 1, high);
        }
    }

    static int Partition(int[] arr, int low, int high)
    {
        // Выбираем последний элемент как опорный
        int pivot = arr[high];
        int i = low - 1; // Индекс для меньших элементов

        for (int j = low; j < high; j++)
        {
            // Если текущий элемент меньше или равен опорному
            if (arr[j] <= pivot)
            {
                i++;
                // Меняем местами arr[i] и arr[j]
                if (i != j)
                {
                    (arr[i], arr[j]) = (arr[j], arr[i]);
                }
            }
        }

        // Ставим опорный элемент на его законное место
        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        return i + 1;//возвращаем новый индекс опорного элемента.
    }
}

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

Алгоритм выше легко довести до O(n^2), если на вход дать массив уже отсортированный, при том неважно в каком порядке (по возрастанию или убыванию).

Здесь в качестве опорного элемента выбирается последний.

Допустим мы подали полностью отсортированный (по возрастанию) массив от 1 до 10 включительно.
Метод Partition поделит массив на 2 части вернет индекс 9 и поделит массив на две части: [1, 2, 3, 4, 5, 6, 7, 8, 9] и пустой массив []
Потом метод Partition для первой части вернет индекс 8 и поделит первый массив, на две части [1, 2, 3, 4, 5, 6, 7, 8] и пустой массив.
Каждый раз он алгоритм будет проходить по n, потом по n-1, потом по n - 2 элементам и т.д.

Общее количество операций:
n + (n-1) + (n-2) + ... + 2 + 1 = n(n+1)/2 ≈ n²/2 = O(n²)

Но есть несколько способов, чтобы не допустить O(n^2).
Один из них – это выбрать опорный элемент случайным образом.

Код теперь выглядит так:

static void QuickSort(int[] arr, int low, int high)
{
     if (low < high)
     {
         // ГЛАВНОЕ ОТЛИЧИЕ: случайный выбор опорного элемента
         int pivotIndex = RandomPartition(arr, low, high);

         // Рекурсивно сортируем левую и правую части
         QuickSort(arr, low, pivotIndex - 1);
         QuickSort(arr, pivotIndex + 1, high);
     }
}

static int RandomPartition(int[] arr, int low, int high)
{
     // Выбираем случайный индекс в диапазоне [low, high]
     int randomIndex = rand.Next(low, high + 1);
     // Меняем случайный элемент с последним
     (arr[randomIndex], arr[high]) = (arr[high], arr[randomIndex]);
     // Теперь используем стандартную partition с последним элементом
     return Partition(arr, low, high);
}

static int Partition(int[] arr, int low, int high)
{
     int pivot = arr[high]; // опорный элемент (теперь случайный)
     int i = low - 1;
     for (int j = low; j < high; j++)
     {
         if (arr[j] <= pivot)
         {
             i++;
             (arr[i], arr[j]) = (arr[j], arr[i]);
         }
     }
     (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
     return i + 1;
}  

а есть и другой способ – выбрать медианный элемент из первого, среднего и последнего элементов.

static void QuickSort(int[] arr, int low, int high) 
{ 
    if (low < high) 
    { 
        int pi = MedianOfThreePartition(arr, low, high); 
        QuickSort(arr, low, pi - 1); 
        QuickSort(arr, pi + 1, high); 
    } 
} 
 
static int MedianOfThreePartition(int[] arr, int low, int high) 
{ 
    int mid = low + (high - low) / 2; 
 
    // Сортируем три элемента: arr[low], arr[mid], arr[high] 
    // чтобы arr[low] <= arr[mid] <= arr[high] 
    if (arr[low] > arr[mid]) (arr[low], arr[mid]) = (arr[mid], arr[low]); 
    if (arr[low] > arr[high]) (arr[low], arr[high]) = (arr[high], arr[low]); 
    if (arr[mid] > arr[high]) (arr[high], arr[mid]) = (arr[mid], arr[high]); 
 
    // Теперь arr[mid] — медиана из трёх 
    (arr[mid], arr[high]) = (arr[high], arr[mid]); 
 
    return Partition(arr, low, high); 
} 
 
static int Partition(int[] arr, int low, int high) 
{ 
    int pivot = arr[high]; 
    int i = low - 1; 
 
    for (int j = low; j <= high; j++) 
    { 
        if (arr[j] <= pivot) 
        { 
            i++; 
            (arr[i], arr[j]) = (arr[j], arr[i]); 
        } 
    } 
    return i; 
}

На примере, почему меньше операций.

Массив из 16 элементов, pivot = медиана

Уровень 1: [16 элементов] → разделение на [8] и [8]Работа: 16 операций (проход по всем элементам)

Уровень 2: [8] [8] → разделение на [4] [4] [4] [4]Работа: 8 + 8 = 16 операций

Уровень 3: [4] [4] [4] [4] → разделение на [2] × 8Работа: 4×4 = 16 операций

Уровень 4: [2] × 8 → разделение на [1] × 16Работа: 2×8 = 16 операций

и т.д.

Итого: 4 уровня × 16 операций = 64 операции

Массив из 16 элементов, pivot = максимум

Уровень 1: [16 элементов] → разделение на [15] и []Работа: 16 операций

Уровень 2: [15 элементов] → разделение на [14] и []Работа: 15 операций

Уровень 3: [14 элементов] → разделение на [13] и []Работа: 14 операций

Уровень 4: [13 элементов] → разделение на [12] и []Работа: 13 операций

и т.д.

Итого: 16 + 15 + 14 + ... + 2 + 1 = 136 операций

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

На моем компьютере получились такие данные:

Отсортированный массив (время в мс).

Количество элементов 1000 5000 10000 15000 Опорный элемент последний 1,3481 49,9192 126,8646 282,8915 Опорный элемент случайный 0,0633 0,4826 0,8018 1,2721 Опорный элемент медианный 0,0430 0,2728 0,5773 0,8535

Отсортированный массив в порядке убывания (время в мс).

Количество элементов 1000 5000 10000 15000 Опорный элемент последний 1,1011 30,0971 111,3659 248,0829 Опорный элемент случайный 0,0698 0,3894 0,8156 1,2952 Опорный элемент медианный 0,0705 0,4464 0,9652 1,5092

Перемешанный случайно массив (время в мс).

Количество элементов 1000 5000 10000 15000 Опорный элемент последний 0,0911 0,5372 1,2565 1,8101 Опорный элемент случайный 0,0943 0,5634 1,2180 1,8907 Опорный элемент медианный 0,0890 0,5598 1,1798 1,8461

Почти отсортированный массив (перемешено 5% массива) (время в мс).

Количество элементов 1000 5000 10000 15000 Опорный элемент последний 0,1012 0,8644 1,5544 2,8059 Опорный элемент случайный 0,0704 0,4432 0,9017 1,3402 Опорный элемент медианный 0,0707 0,4196 1,0123 1,4061

Как видим, на практике легко избежать O(n^2).

LIS - Longest Increasing Subsequence. Наибольшая возрастающая последовательность.

Дан массив чисел nums. Верните длину наиболее длинной строго возрастающей подпоследовательности.

Подпоследовательность - это последовательность элементов полученная из другой последовательности путем удаления нескольких (возможно нуля) элементов с сохранением порядка.например, последовательность [1, 2, 3, 4, 5]:подпоследовательности: 1, 2, 3, 4, 5 (удалили 0 элементов)1,3,5 - (удалили 2 и 4)

Пример 1:

Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: Наибольшая строговозрастающая последовательность [2,3,7,101], 
таким образом длина 4.

Пример 2:

Ввод: nums = [0,1,0,3,2,3]
Вывод: 4

Пример 3:

Ввод: nums = [7,7,7,7,7,7,7]
Вывод: 1

Решение

Заведем массив dp (dynamic programming).
Определим, что мы будем в нём хранить.
Договоримся, что мы будем хранить в dp[i] длину максимальной строговозрастающей подпоследовательности, если бы у нас было только i элементов, тогда ответ будет dp[dp.Length - 1] (или более кратко dp[^1]).
Например:
nums = [5, 6, 7, 1, 2]
dp = [1, 2, 3, 3, 3]

nums = [5, 6, 1, 2, 3]
dp = [1, 2, 2, 2, 3]

Мы могли бы договориться, хранить в dp[i] длину максимальной 
строговозрастающей подпоследовательности, которая оканчивается элементом 
nums[i] и тогда было бы так
nums = [5, 6, 7, 1, 2]
dp = [1, 2, 3, 1, 2]

nums = [5, 6, 1, 2, 3]
dp = [1, 2, 1, 2, 3]
Тогда ответ был бы в dp.Max();

Определим базовый случай:
dp[0] = 1 - если бы у нас был только один элемент он бы и составлял максимальную подпоследовательность размера 1.

Теперь определимся, как вычислять dp[i].
В нашем случае может показаться, что если nums[i] > nums[i - 1],
то dp[i] = dp[i - 1] + 1, но это не так.

возьмем последовательность 5, 6, 7, 1, 2
здесь 2 больше 1, а dp[3] == 3 (у нас в dp[3] должна храниться максимальная длина, как если бы у нас было бы только числа [5, 6, 7, 1], т.е. 3).

то есть, чтобы вычислить dp[i] нам нужно найти длины всех последовательностей, оканчивающейся элементом меньше чем nums[i], и из них выбрать максимальную.

Заведем второй массив dp2. В dp2[i] будем хранить максимальную длину строговозрастающей последовательности, которая оканчивается элементом nums[i].

Пока код такой:

public class Solution {
    public int LengthOfLIS(int[] nums) {
        //dp[i] - длина максимальной строговозрастающей последовательности,
        //если бы у нас было i элементов.
        var dp = new int[nums.Length];
        //dp2[i] - длина максимальной строговозрастающей последовательности,
        //оканчивающийся элементом nums[i].
        var dp2 = new int[nums.Length];
        dp[0] = 1;
        dp2[0] = 1;
        for (var i = 1; i < dp.Length; i++)
        {
            var maxSeq = 1;
            //идём назад и ищем элемент меньше текущего.
            for (var j = i - 1; j >= 0; j--)
            {
                if (nums[j] < nums[i])
                {
                    //нашли. тогда длина строговозврастающей
                    //последовательности - это длина которая оканчивается
                    //элементом nums[j] (то есть значение dp2[j]) плюс 1.
                    maxSeq = Math.Max(maxSeq, dp2[j] + 1);
                }
            }
            dp2[i] = maxSeq;
            dp[i] = Math.Max(dp[i - 1], maxSeq);//максимальная длина
            //оканчивающиейся элементом nums[i], необязательно максимальная
            //длина вообще
            //nums =[5,6,7, 1, 2]
            //dp2 =[1, 2, 3, 1, 2]
            //dp = [1, 2, 3, 3, 3]
        }
        return dp[^1];
    }
}

Если мы посмотрим, то увидим, что из массива dp в итерациях нужен только последний элемент (dp[i] и предыдущий dp[i - 1]).
мы можем заменить его на одну переменную. Назовем её макс, а массив dp2
переименовать в массив dp.

public class Solution {
    public int LengthOfLIS(int[] nums) {
        var max = 1;//вместо массива dp
        var dp = new int[nums.Length];//бывший массив dp2
        dp[0] = 1;
        for (var i = 1; i < dp.Length; i++)
        {
            var maxSeq = 1;
            for (var j = i - 1; j >= 0; j--)
            {
                if (nums[j] < nums[i])
                {
                    maxSeq = Math.Max(maxSeq, dp[j] + 1);
                }
            }
            dp[i] = maxSeq;
            max = Math.Max(max, maxSeq);
        }
        return max;
    }
}

Если бы мы сразу договорились хранить в dp[i] длину максимальной строговозрастающей последовательности, оканчивающейся элементом nums[i],
мы бы могли сразу перейти к такому решению.

Определяет скелет алгоритма, позволяющий изменять определенные шаги.

Определяется абстрактный класс, в нём определяется метод, который вызывает последовательность других виртуальны или абстрактных методов методов.

Определяется класс наследник (concrete) от абстрактного, который переопределяет некоторые шаги.

Например, классы, который выкачивает данные, обрабатывает и сохраняет.

public abstract class DataProcessor
{
     public void Process()
     {
         DownloadDAta();
         ParseData();
         SaveData();
         
         if (ShouldSendNotification())
         {
            SendNotification();
         }
     }
     
     //обязательные шаги
     protected abstract void DownloadData();
     protected abstract void ParseData();
     
     //шаг с дефолтной реализацией
     protected virtual void SaveData()
     {
     }
     
     //Хук
     protected virtual bool ShouldSendNotification() => true;
     
     //неопределяемый
     private void SendNotification()
     {
     }
}

Классы-реализации:

public class JsonDataProcessor : DataProcessor
{
      protected override void DownloadData()
      {
          //загрузка из json
      }
      
      protected override void ParseData()
      {
          //парсинг json
      }
}

Использование

DataProcessor processor = new JsonDataProcessor()
processor.Process();

Паттерн используют для создания библиотек, позволяющей пользователю определять какие-то шаги.

Примеры из стандартных библиотек .NET:

BackgroundService - класс для создания долгосрочных задач.
Определяет метод StartAsync с дефолтной реализацией, также определяет чистый виртуальный метод ExecuteAsync, который надо переопределить.

IO.Stream - базовый класс для всех потоков. В нём методы WriteAsync, ReadAsync и т.д. содержат базовую логику проверки параметров, создания асинхронных контекстов и вызова внутренних абстрактных виртуальных методов, которые должны перопределиться в конкретных реализациях FileStream, NetworkStream, MemoryStream и т.д.