Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

func countBits(num int) []int {
    ans := make([]int, num + 1)
    for x := 1; x <= num; x++ {
        ans[x] = ans[x & (x - 1)] + 1
    }
    return ans
}

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

Задача: 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⃣Верните найденное максимальное расстояние.

😎 Решение:

func binaryGap(N int) int {
    A, t := make([]int, 0, 32), 0
    for i := 0; i < 32; i++ {
        if (N>>i)&1 != 0 {
            A = append(A, i)
            t++
        }
    }
    ans := 0
    for i := 0; i < t-1; i++ {
        if A[i+1]-A[i] > ans {
            ans = A[i+1] - A[i]
        }
    }
    return ans
}

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

Задача: 269. Alien Dictionary
Сложность: hard

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

Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.

Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".

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

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

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

1⃣Извлечение отношений порядка и создание списков смежности:
Извлечь отношения порядка между буквами из слов.
Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого.

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

package main

import (
    "container/list"
    "strings"
)

func alienOrder(words []string) string {
    adjList := make(map[byte]map[byte]struct{})
    inDegree := make(map[byte]int)

    for _, word := range words {
        for i := 0; i < len(word); i++ {
            inDegree[word[i]] = 0
        }
    }

    for i := 0; i < len(words)-1; i++ {
        firstWord := words[i]
        secondWord := words[i+1]
        for j := 0; j < len(firstWord) && j < len(secondWord); j++ {
            c := firstWord[j]
            d := secondWord[j]
            if c != d {
                if _, exists := adjList[c]; !exists {
                    adjList[c] = make(map[byte]struct{})
                }
                if _, exists := adjList[c][d]; !exists {
                    adjList[c][d] = struct{}{}
                    inDegree[d]++
                }
                break
            }
        }
        if len(secondWord) < len(firstWord) && strings.HasPrefix(firstWord, secondWord) {
            return ""
        }
    }

    queue := list.New()
    for char, degree := range inDegree {
        if degree == 0 {
            queue.PushBack(char)
        }
    }

    var output strings.Builder
    for queue.Len() > 0 {
        elem := queue.Front()
        c := elem.Value.(byte)
        queue.Remove(elem)
        output.WriteByte(c)
        if neighbors, exists := adjList[c]; exists {
            for d := range neighbors {
                inDegree[d]--
                if inDegree[d] == 0 {
                    queue.PushBack(d)
                }
            }
        }
    }

    if output.Len() < len(inDegree) {
        return ""
    }

    return output.String()
}

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

Задача: 239. Sliding Window Maximum
Сложность: hard

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

Верните максимальные значения скользящего окна.

Пример:

Input: nums = [1], k = 1
Output: [1]

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

1⃣Инициализация и заполнение первой части окна:
Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов.
Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента:
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]].

2⃣Сканирование оставшейся части массива:
Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента:
Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна.
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]].

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

😎 Решение:

func maxSlidingWindow(nums []int, k int) []int {
    dq := make([]int, 0)
    res := make([]int, 0)
    
    for i := 0; i < k; i++ {
        for len(dq) > 0 && nums[i] >= nums[dq[len(dq)-1]] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
    }
    res = append(res, nums[dq[0]])
    
    for i := k; i < len(nums); i++ {
        if dq[0] == i - k {
            dq = dq[1:]
        }
        for len(dq) > 0 && nums[i] >= nums[dq[len(dq)-1]] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
        res = append(res, nums[dq[0]])
    }
    
    return res
}

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

Задача: 290. Word Pattern
Сложность: easy

Дан шаблон и строка s, необходимо определить, следует ли строка s этому шаблону.

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

Пример:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

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

1⃣Разделение строки на слова:
Разделите строку s на отдельные слова.
Если количество слов не равно длине шаблона, возвращаем false.

2⃣Создание отображений:
Создайте два словаря: один для отображения букв шаблона на слова, другой для слов на буквы шаблона.

3⃣Проверка биекции:
Пройдите по каждому символу шаблона и соответствующему слову.
Если символ уже в словаре и не соответствует текущему слову или слово уже в словаре и не соответствует текущему символу, возвращаем false.
Иначе добавляем символ и слово в словари и продолжаем проверку. Если все проверки пройдены, возвращаем true.

😎 Решение:

package main

import (
    "strings"
)

func wordPattern(pattern string, s string) bool {
    mapChar := make(map[rune]string)
    mapWord := make(map[string]rune)
    words := strings.Split(s, " ")

    if len(words) != len(pattern) {
        return false
    }

    for i, c := range pattern {
        w := words[i]
        if _, ok := mapChar[c]; !ok {
            if _, ok := mapWord[w]; ok {
                return false
            } else {
                mapChar[c] = w
                mapWord[w] = c
            }
        } else {
            if mapChar[c] != w {
                return false
            }
        }
    }

    return true
}

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

Задача: 105. Construct Binary Tree from Preorder and Inorder Traversal
Сложность: easy

Даны два массива целых чисел: preorder и inorder, где preorder — это результат преордер обхода бинарного дерева, а inorder — результат инордер обхода того же дерева. Постройте и верните бинарное дерево.

Пример:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

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

1⃣Создайте хеш-таблицу для записи соотношения значений и их индексов в массиве inorder, чтобы можно было быстро найти позицию корня.

2⃣Инициализируйте переменную целочисленного типа preorderIndex для отслеживания элемента, который будет использоваться для создания корня. Реализуйте рекурсивную функцию arrayToTree, которая принимает диапазон массива inorder и возвращает построенное бинарное дерево:
Если диапазон пуст, возвращается null;
Инициализируйте корень элементом preorder[preorderIndex], затем увеличьте preorderIndex;
Рекурсивно используйте левую и правую части массива inorder для построения левого и правого поддеревьев.

3⃣Просто вызовите функцию рекурсии с полным диапазоном массива inorder.

😎 Решение:

func buildTree(preorder []int, inorder []int) *TreeNode {
    preorderIndex := 0
    inorderIndexMap := make(map[int]int)
    for i := 0; i < len(inorder); i++ {
        inorderIndexMap[inorder[i]] = i
    }
    var arrayToTree func(left int, right int) *TreeNode
    arrayToTree = func(left int, right int) *TreeNode {
        if left > right {
            return nil
        }
        rootValue := preorder[preorderIndex]
        preorderIndex++
        root := &TreeNode{Val: rootValue}
        root.Left = arrayToTree(left, inorderIndexMap[rootValue]-1)
        root.Right = arrayToTree(inorderIndexMap[rootValue]+1, right)
        return root
    }
    return arrayToTree(0, len(preorder)-1)
}

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

Задача: 865. Smallest Subtree with all the Deepest Nodes
Сложность: medium

Дан корень бинарного дерева, глубина каждого узла — это кратчайшее расстояние до корня.

Верните наименьшее поддерево, которое содержит все самые глубокие узлы в исходном дереве.

Узел называется самым глубоким, если у него наибольшая возможная глубина среди всех узлов в дереве.

Поддерево узла — это дерево, состоящее из этого узла и всех его потомков.

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

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

1⃣В первой фазе используем поиск в глубину (DFS), чтобы аннотировать узлы. Каждый узел будет хранить информацию о своей глубине и о самой большой глубине среди его потомков.

2⃣Во второй фазе также используем DFS для функции answer(node), которая возвращает наименьшее поддерево, содержащее все самые глубокие узлы. Функция сравнивает глубины левых и правых поддеревьев узла для определения наименьшего поддерева.

3⃣Функция answer(node) возвращает поддерево, которое содержит все самые глубокие узлы всего дерева, а не только рассматриваемого поддерева.

😎 Решение:

func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
    depth := map[*TreeNode]int{nil: -1}
    var dfs func(node, parent *TreeNode)
    dfs = func(node, parent *TreeNode) {
        if node != nil {
            depth[node] = depth[parent] + 1
            dfs(node.Left, node)
            dfs(node.Right, node)
        }
    }
    dfs(root, nil)
    maxDepth := -1
    for _, d := range depth {
        if d > maxDepth {
            maxDepth = d
        }
    }
    var answer func(node *TreeNode) *TreeNode
    answer = func(node *TreeNode) *TreeNode {
        if node == nil || depth[node] == maxDepth {
            return node
        }
        L := answer(node.Left)
        R := answer(node.Right)
        if L != nil && R != nil {
            return node
        }
        if L != nil {
            return L
        }
        return R
    }
    return answer(root)
}

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

Задача: 687. Longest Univalue Path
Сложность: medium

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

Длина пути между двумя узлами представлена количеством рёбер между ними.

Пример:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

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

1⃣Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла.

2⃣Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0.

3⃣Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans..

😎 Решение:

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type Solution struct {
    ans int
}

func (s *Solution) solve(root *TreeNode, parent int) int {
    if root == nil {
        return 0
    }

    left := s.solve(root.Left, root.Val)
    right := s.solve(root.Right, root.Val)
    
    if s.ans < left+right {
        s.ans = left + right
    }
    
    if root.Val == parent {
        if left > right {
            return left + 1
        } else {
            return right + 1
        }
    }
    return 0
}

func (s *Solution) LongestUnivaluePath(root *TreeNode) int {
    s.solve(root, -1)
    return s.ans
}

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

Задача: 235. Lowest Common Ancestor of a Binary Search Tree
Сложность: medium

Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

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

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла.

2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1.

3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат.

😎 Решение:

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    parentVal := root.Val
    pVal := p.Val
    qVal := q.Val

    if pVal > parentVal && qVal > parentVal {
        return lowestCommonAncestor(root.Right, p, q)
    } else if pVal < parentVal && qVal < parentVal {
        return lowestCommonAncestor(root.Left, p, q)
    } else {
        return root
    }
}

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

Задача: 1416. Restore The Array
Сложность: hard

Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей.

Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

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

1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x).

2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе:
Если s[start] == 0, вернуть 0.
Если start = m, вернуть 1.
Инициализировать count = 0, чтобы считать количество возможных массивов.
Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1).
Обновить dp[start] значением dfs(start).

3⃣Вернуть dfs(0).

😎 Решение:

func dfs(dp []int, start int, s string, k int) int {
    if dp[start] != 0 {
        return dp[start]
    }
    if start == len(s) {
        return 1
    }
    if s[start] == '0' {
        return 0
    }

    mod := 1_000_000_007
    count := 0
    for end := start; end < len(s); end++ {
        currNumber, _ := strconv.Atoi(s[start : end+1])
        if currNumber > k {
            break
        }
        count = (count + dfs(dp, end+1, s, k)) % mod
    }

    dp[start] = count
    return count
}

func numberOfArrays(s string, k int) int {
    dp := make([]int, len(s)+1)
    return dfs(dp, 0, s, k)
}

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

Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

Input: nums = [1,3,1], k = 1
Output: 0

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

1⃣Отсортируйте массив nums.

2⃣Определите минимальное и максимальное возможные расстояния.

3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.

😎 Решение:

package main

import (
    "sort"
)

func countPairs(nums []int, mid int) int {
    count := 0
    j := 0
    for i := 0; i < len(nums); i++ {
        for j < len(nums) && nums[j] - nums[i] <= mid {
            j++
        }
        count += j - i - 1
    }
    return count
}

func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    left, right := 0, nums[len(nums) - 1] - nums[0]
    for left < right {
        mid := (left + right) / 2
        if countPairs(nums, mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

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

Задача: 750. Number Of Corner Rectangles
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

1⃣Пройдите по строкам матрицы. Для каждой пары строк, найдите все столбцы, где оба значения равны 1.

2⃣Подсчитайте количество таких столбцов. Если их больше одного, то они образуют прямоугольники.

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

😎 Решение:

package main

func countCornerRectangles(grid [][]int) int {
    count := 0
    for i := 0; i < len(grid); i++ {
        for j := i + 1; j < len(grid); j++ {
            numPairs := 0
            for k := 0; k < len(grid[0]); k++ {
                if grid[i][k] == 1 && grid[j][k] == 1 {
                    numPairs++
                }
            }
            if numPairs > 1 {
                count += numPairs * (numPairs - 1) / 2
            }
        }
    }
    return count
}

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

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.

Напоминаю, что в честь релиза запускаем акцию.

Первые 500 покупателей получат:

🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал

🔔 Подпишитесь на этот канал: https://t.iss.one/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Сложность: easy

Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.

Дерево cloned является копией оригинального дерева.

Верните ссылку на тот же узел в дереве cloned.

Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned.

Пример:
Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

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

1⃣Добавьте корень в очередь.

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

3⃣Верните ссылку на найденный целевой узел.

😎 Решение:

func getTargetCopy(original *TreeNode, cloned *TreeNode, target *TreeNode) *TreeNode {
    queue_o := []*TreeNode{original}
    queue_c := []*TreeNode{cloned}
    
    for len(queue_o) > 0 {
        node_o := queue_o[0]
        queue_o = queue_o[1:]
        node_c := queue_c[0]
        queue_c = queue_c[1:]
        
        if node_o == target {
            return node_c
        }
        
        if node_o.Left != nil {
            queue_o = append(queue_o, node_o.Left)
            queue_c = append(queue_c, node_c.Left)
        }
        if node_o.Right != nil {
            queue_o = append(queue_o, node_o.Right)
            queue_c = append(queue_c, node_c.Right)
        }
    }
    return nil
}

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

Задача: №31. Next Permutation
Сложность: medium

Перестановка массива целых чисел — это упорядочивание его элементов в последовательность или линейный порядок.

Например, для arr = [1,2,3] следующие являются всеми перестановками arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его чисел. Более формально, если все перестановки массива отсортированы в одном контейнере по лексикографическому порядку, то следующая перестановка этого массива — это перестановка, следующая за ней в отсортированном контейнере. Если такое упорядочивание невозможно, массив должен быть переупорядочен в наименьший возможный порядок (то есть отсортирован по возрастанию).

Например, следующая перестановка arr = [1,2,3] — это [1,3,2].
Аналогично, следующая перестановка arr = [2,3,1] — это [3,1,2].
В то время как следующая перестановка arr = [3,2,1] — это [1,2,3], потому что [3,2,1] не имеет лексикографически большего переупорядочивания.

Для данного массива целых чисел nums найдите следующую перестановку nums.

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

Пример:

Input: nums = [1,2,3]
Output: [1,3,2]

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

1⃣Мы меняем местами числа a[i−1] и a[j]. Теперь у нас есть правильное число на индексе i−1. Однако текущая перестановка ещё не является той перестановкой, которую мы ищем. Нам нужна наименьшая перестановка, которая может быть сформирована с использованием чисел только справа от a[i−1]. Следовательно, нам нужно расположить эти числа в порядке возрастания, чтобы получить их наименьшую перестановку.

2⃣Однако, вспомните, что, сканируя числа справа налево, мы просто уменьшали индекс, пока не нашли пару a[i] и a[i−1], где a[i] > a[i−1]. Таким образом, все числа справа от a[i−1] уже были отсортированы в порядке убывания. Более того, обмен местами a[i−1] и a[j] не изменил этот порядок.

3⃣Поэтому нам просто нужно перевернуть числа, следующие за a[i−1], чтобы получить следующую наименьшую лексикографическую перестановку.

😎 Решение:

func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i+1] <= nums[i] {
        i--
    }
    if i >= 0 {
        j := len(nums) - 1
        for nums[j] <= nums[i] {
            j--
        }
        swap(nums, i, j)
    }
    reverse(nums, i+1)
}

func reverse(nums []int, start int) {
    i, j := start, len(nums)-1
    for i < j {
        swap(nums, i, j)
        i++
        j--
    }
}

func swap(nums []int, i int, j int) {
    temp := nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

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

Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium

Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

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

😎 Решение:

func lengthOfLongestSubstringKDistinct(s string, k int) int {
    left, right := 0, 0
    charCount := make(map[byte]int)
    maxLength := 0
    
    for right < len(s) {
        charCount[s[right]]++
        for len(charCount) > k {
            charCount[s[left]]--
            if charCount[s[left]] == 0 {
                delete(charCount, s[left])
            }
            left++
        }
        if right-left+1 > maxLength {
            maxLength = right - left + 1
        }
        right++
    }
    
    return maxLength
}

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

Задача: 904. Fruit Into Baskets
Сложность: medium

Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.

Пример:

Input: fruits = [1,2,1]
Output: 3

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

1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов.

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

3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге.

😎 Решение:

package main

func totalFruit(fruits []int) int {
    basket := make(map[int]int)
    left, maxFruits := 0, 0

    for right := 0; right < len(fruits); right++ {
        basket[fruits[right]]++
        for len(basket) > 2 {
            basket[fruits[left]]--
            if basket[fruits[left]] == 0 {
                delete(basket, fruits[left])
            }
            left++
        }
        if right - left + 1 > maxFruits {
            maxFruits = right - left + 1
        }
    }

    return maxFruits
}

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

Задача: 445. Add Two Numbers II
Сложность: medium

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

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

Пример:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

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

1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.

2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.

3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.

😎 Решение:

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    var temp *ListNode
    for head != nil {
        temp = head.Next
        head.Next = prev
        prev = head
        head = temp
    }
    return prev
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    r1 := reverseList(l1)
    r2 := reverseList(l2)

    totalSum := 0
    carry := 0
    ans := &ListNode{}
    for r1 != nil || r2 != nil {
        if r1 != nil {
            totalSum += r1.Val
            r1 = r1.Next
        }
        if r2 != nil {
            totalSum += r2.Val
            r2 = r2.Next
        }

        ans.Val = totalSum % 10
        carry = totalSum / 10
        head := &ListNode{Val: carry}
        head.Next = ans
        ans = head
        totalSum = carry
    }

    if carry == 0 {
        return ans.Next
    }
    return ans
}

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

Задача: 1099. Two Sum Less Than K
Сложность: easy

Дан массив целых чисел nums и целое число k. Верните максимальную сумму, такую что существуют i < j, при которых nums[i] + nums[j] = sum и sum < k. Если не существует таких i и j, удовлетворяющих этому условию, верните -1.

Пример:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

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

1⃣Отсортируйте массив.

2⃣Установите указатели: левый на начало массива, правый на конец.

3⃣Пока левый указатель меньше правого:
Если сумма элементов по указателям меньше k, обновите максимальную сумму и сдвиньте левый указатель вправо.
Иначе сдвиньте правый указатель влево.
Верните максимальную сумму.

😎 Решение:

func twoSumLessThanK(nums []int, k int) int {
    answer := -1
    count := make([]int, 1001)
    for _, num := range nums {
        count[num]++
    }
    lo, hi := 1, 1000
    for lo <= hi {
        if lo + hi >= k || count[hi] == 0 {
            hi--
        } else {
            if count[lo] > 0 {
                if lo == hi && count[lo] < 2 {
                    lo++
                    continue
                }
                answer = max(answer, lo + hi)
            }
            lo++
        }
    }
    return answer
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

Задача: 938. Range Sum of BST
Сложность: easy

Учитывая корневой узел двоичного дерева поиска и два целых числа low и high, верните сумму значений всех узлов со значением в диапазоне [low, high].

Пример:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

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

1⃣Если дерево пустое, вернуть 0.

2⃣Если значение текущего узла меньше low, рекурсивно искать в правом поддереве.
Если значение текущего узла больше high, рекурсивно искать в левом поддереве.

3⃣Если значение текущего узла в диапазоне [low, high], включить значение узла в сумму и рекурсивно искать в обоих поддеревьях.

😎 Решение:

package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func rangeSumBST(root *TreeNode, low int, high int) int {
    if root == nil {
        return 0
    }
    if root.Val < low {
        return rangeSumBST(root.Right, low, high)
    }
    if root.Val > high {
        return rangeSumBST(root.Left, low, high)
    }
    return root.Val + rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high)
}

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