#medium
Задача: 524. Longest Word in Dictionary through Deleting


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

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

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

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

func isSubsequence(x, y string) bool {
    j := 0
    for i := 0; i < len(y) && j < len(x); i++ {
        if x[j] == y[i] {
            j++
        }
    }
    return j == len(x)
}

func findLongestWord(s string, d []string) string {
    maxStr := ""
    for _, str := range d {
        if isSubsequence(str, s) {
            if len(str) > len(maxStr) || (len(str) == len(maxStr) && str < maxStr) {
                maxStr = str
            }
        }
    }
    return maxStr
}

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

#Easy
Задача: 605. Can Place Flowers

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

Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

func canPlaceFlowers(flowerbed []int, n int) bool {
    count := 0
    for i := 0; i < len(flowerbed); i++ {
        if flowerbed[i] == 0 {
            emptyLeft := i == 0 || flowerbed[i-1] == 0
            emptyRight := i == len(flowerbed)-1 || flowerbed[i+1] == 0
            if emptyLeft && emptyRight {
                flowerbed[i] = 1
                count++
            }
        }
    }
    return count >= n
}

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

#Medium
Задача: 606. Construct String from Binary Tree

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

Представление узлов: Каждый узел в дереве должен быть представлен его целочисленным значением.

Скобки для дочерних узлов: Если у узла есть хотя бы один дочерний узел (левый или правый), его дочерние узлы должны быть представлены в скобках. Конкретно:

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

Пропуск пустых скобок: Любые пустые пары скобок (т.е. ()) должны быть опущены в окончательном строковом представлении дерева, за одним исключением: когда у узла есть правый дочерний узел, но нет левого дочернего узла. В таких случаях вы должны включить пустую пару скобок, чтобы указать на отсутствие левого дочернего узла. Это гарантирует, что однозначное соответствие между строковым представлением и исходной структурой бинарного дерева сохраняется.

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

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

3⃣Объединение результатов
Собираем результаты для каждого узла, учитывая все упомянутые случаи, чтобы получить строковое представление дерева.

😎 Решение:

import (
    "strconv"
)

func tree2str(t *TreeNode) string {
    var res string
    dfs(t, &res)
    return res
}

func dfs(t *TreeNode, res *string) {
    if t == nil {
        return
    }
    *res += strconv.Itoa(t.Val)
    if t.Left == nil && t.Right == nil {
        return
    }
    *res += "("
    dfs(t.Left, res)
    *res += ")"
    if t.Right != nil {
        *res += "("
        dfs(t.Right, res)
        *res += ")"
    }
}

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

#medium
Задача: 525. Contiguous Array


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

Пример:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

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

1⃣Инициализируйте переменную count для отслеживания разности между количеством 1 и 0, и переменную max_length для хранения максимальной длины подмассива. Создайте хеш-таблицу map для хранения первых встреч каждого значения count. Добавьте начальное значение (0, -1) в хеш-таблицу.

2⃣Итеративно пройдите по массиву nums. На каждой итерации обновляйте значение count (увеличивайте на 1 для 1 и уменьшайте на 1 для 0). Если текущее значение count уже существует в хеш-таблице, вычислите длину подмассива между текущим индексом и индексом из хеш-таблицы. Обновите max_length, если текущий подмассив длиннее.

3⃣Если текущее значение count не существует в хеш-таблице, добавьте его с текущим индексом. После завершения итерации верните max_length.

😎 Решение:

func findMaxLength(nums []int) int {
    countMap := map[int]int{0: -1}
    count, maxLength := 0, 0
    
    for i, num := range nums {
        if num == 1 {
            count++
        } else {
            count--
        }
        
        if prevIndex, exists := countMap[count]; exists {
            maxLength = max(maxLength, i - prevIndex)
        } else {
            countMap[count] = i
        }
    }
    
    return maxLength
}

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

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

#medium
Задача: 353. Design Snake Game

Разработайте игру "Змейка", которая играется на устройстве с экраном размером height x width. Поиграйте в игру онлайн, если вы не знакомы с ней.

Змейка изначально находится в верхнем левом углу (0, 0) с длиной в 1 единицу.
Вам дан массив food, где food[i] = (ri, ci) представляет собой строку и столбец позиции пищи, которую змейка может съесть. Когда змейка съедает кусочек пищи, ее длина и очки игры увеличиваются на 1.
Каждый кусочек пищи появляется по очереди на экране, то есть второй кусочек пищи не появится, пока змейка не съест первый кусочек пищи.
Когда кусочек пищи появляется на экране, гарантируется, что он не появится на блоке, занятом змейкой.
Игра заканчивается, если змейка выходит за пределы экрана (врезается в стену) или если ее голова занимает пространство, которое занимает ее тело после движения (например, змейка длиной 4 не может врезаться в себя).

Реализуйте класс SnakeGame:
SnakeGame(int width, int height, int[][] food) Инициализирует объект с экраном размером height x width и позициями пищи.
int move(String direction) Возвращает счет игры после применения одного движения змейки в направлении. Если игра окончена, верните -1.

Пример:

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

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

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

2⃣Реализуйте функцию для вычисления нового положения головы змейки на основе направления движения.

3⃣Обновите положение змейки и проверьте условия завершения игры. Верните текущий счет или -1, если игра закончена.

😎 Решение:

package main

type SnakeGame struct {
    width, height, score, foodIndex int
    food                            [][]int
    snake                           []pair
    snakeSet                        map[pair]bool
}

type pair struct {
    x, y int
}

func Constructor(width int, height int, food [][]int) SnakeGame {
    return SnakeGame{
        width:    width,
        height:   height,
        food:     food,
        score:    0,
        foodIndex: 0,
        snake:    []pair{{0, 0}},
        snakeSet: map[pair]bool{{0, 0}: true},
    }
}

func (this *SnakeGame) Move(direction string) int {
    head := this.snake[0]
    newHead := head

    switch direction {
    case "U":
        newHead.x--
    case "D":
        newHead.x++
    case "L":
        newHead.y--
    case "R":
        newHead.y++
    }

    if newHead.x < 0 || newHead.x >= this.height || newHead.y < 0 || newHead.y >= this.width {
        return -1
    }

    if this.snakeSet[newHead] && (newHead != this.snake[len(this.snake)-1]) {
        return -1
    }

    if this.foodIndex < len(this.food) && newHead.x == this.food[this.foodIndex][0] && newHead.y == this.food[this.foodIndex][1] {
        this.foodIndex++
    } else {
        tail := this.snake[len(this.snake)-1]
        this.snake = this.snake[:len(this.snake)-1]
        delete(this.snakeSet, tail)
    }

    this.snake = append([]pair{newHead}, this.snake...)
    this.snakeSet[newHead] = true

    return len(this.snake) - 1
}

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

#medium
Задача: 609. Find Duplicate File in System

Получив список paths информации о каталоге, включающий путь к каталогу и все файлы с содержимым в этом каталоге, верните все дубликаты файлов в файловой системе по их путям. Вы можете вернуть ответ в любом порядке. Группа дубликатов состоит как минимум из двух файлов с одинаковым содержимым. Одна строка информации о каталоге во входном списке имеет следующий формат: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" Это означает, что в каталоге "root/d1/d2/.../dm" имеется n файлов (f1.txt, f2.txt ... fn.txt) с содержимым (f1_content, f2_content ... fn_content) соответственно. Обратите внимание, что n >= 1 и m >= 0. Если m = 0, это означает, что каталог является только корневым. На выходе получается список групп дублирующихся путей к файлам. Для каждой группы он содержит все пути к файлам, которые имеют одинаковое содержимое. Путь к файлу - это строка, имеющая следующий формат: "каталог_путь/имя_файла.txt".

Пример:

Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

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

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

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

3⃣Пройдите по словарю и соберите группы дубликатов, содержащие как минимум два пути.

😎 Решение:

package main

import (
    "strings"
)

func findDuplicate(paths []string) [][]string {
    contentToFilePaths := make(map[string][]string)
    
    for _, path := range paths {
        parts := strings.Split(path, " ")
        root := parts[0]
        
        for i := 1; i < len(parts); i++ {
            fileParts := strings.Split(parts[i], "(")
            fileName := fileParts[0]
            content := fileParts[1][:len(fileParts[1])-1]
            
            filePath := root + "/" + fileName
            contentToFilePaths[content] = append(contentToFilePaths[content], filePath)
        }
    }
    
    var result [][]string
    for _, filePaths := range contentToFilePaths {
        if len(filePaths) > 1 {
            result = append(result, filePaths)
        }
    }
    
    return result
}

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

#medium
Задача: 611. Valid Triangle Number

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

Пример:

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

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

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

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

3⃣Увеличивайте счетчик на количество подходящих пар для каждого третьего элемента.

😎 Решение:

package main

import (
    "sort"
)

func triangleNumber(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    count := 0
    
    for k := n - 1; k >= 2; k-- {
        i := 0
        j := k - 1
        for i < j {
            if nums[i] + nums[j] > nums[k] {
                count += j - i
                j--
            } else {
                i++
            }
        }
    }
    
    return count
}

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

#medium
Задача: 616. Add Bold Tag in String

Вам дана строка s и массив строк words. Вы должны добавить закрытую пару полужирных тегов <b> и </b>, чтобы обернуть подстроки в s, которые существуют в words. Если две такие подстроки пересекаются, вы должны обернуть их вместе только одной парой закрытых полужирных тегов. Если две подстроки, обернутые полужирными тегами, идут подряд, вы должны объединить их. Верните s после добавления полужирных тегов.

Пример:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"

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

1⃣Найдите все позиции вхождений подстрок из words в строку s и пометьте эти позиции для выделения тегами <b> и </b>.

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

3⃣Постройте новую строку s, добавляя теги <b> и </b> в определенные позиции.

😎 Решение:

package main

import (
    "strings"
)

func addBoldTag(s string, words []string) string {
    n := len(s)
    bold := make([]bool, n)
    
    for _, word := range words {
        start := strings.Index(s, word)
        for start != -1 {
            for i := start; i < start+len(word); i++ {
                bold[i] = true
            }
            start = strings.Index(s, word, start+1)
        }
    }
    
    var result strings.Builder
    i := 0
    for i < n {
        if bold[i] {
            result.WriteString("<b>")
            for i < n && bold[i] {
                result.WriteByte(s[i])
                i++
            }
            result.WriteString("</b>")
        } else {
            result.WriteByte(s[i])
            i++
        }
    }
    
    return result.String()
}

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

#medium
Задача: 617. Merge Two Binary Trees

Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев.

Пример:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

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

1⃣Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null.

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

3⃣Возвращаем новый узел, который является корнем объединенного дерева.

😎 Решение:

package main

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

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    
    mergedNode := &TreeNode{Val: root1.Val + root2.Val}
    mergedNode.Left = mergeTrees(root1.Left, root2.Left)
    mergedNode.Right = mergeTrees(root1.Right, root2.Right)
    
    return mergedNode
}

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

#medium
Задача: 621. Task Scheduler

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

Пример:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

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

1⃣Подсчитайте количество каждой задачи и найдите максимальное количество вхождений (maxFreq).

2⃣Вычислите количество интервалов, необходимых для задач с maxFreq: (maxFreq - 1) * (n + 1) + countMaxFreq, где countMaxFreq - количество задач, имеющих maxFreq.

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

😎 Решение:

package main

import (
    "fmt"
    "math"
)

func leastInterval(tasks []byte, n int) int {
    taskCounts := make(map[byte]int)
    for _, task := range tasks {
        taskCounts[task]++
    }
    
    maxFreq := 0
    for _, count := range taskCounts {
        if count > maxFreq {
            maxFreq = count
        }
    }
    
    countMaxFreq := 0
    for _, count := range taskCounts {
        if count == maxFreq {
            countMaxFreq++
        }
    }
    
    return int(math.Max(float64(len(tasks)), float64((maxFreq-1)*(n+1)+countMaxFreq)))
}

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

#medium
Задача: 622. Design Circular Queue

Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.

Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

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

1⃣Используйте массив фиксированного размера для хранения элементов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди.

2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу.

3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди.

😎 Решение:

package main

type MyCircularQueue struct {
    queue    []int
    front    int
    rear     int
    size     int
    capacity int
}

func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{
        queue:    make([]int, k),
        front:    0,
        rear:     -1,
        size:     0,
        capacity: k,
    }
}

func (this *MyCircularQueue) enQueue(value int) bool {
    if this.isFull() {
        return false
    }
    this.rear = (this.rear + 1) % this.capacity
    this.queue[this.rear] = value
    this.size++
    return true
}

func (this *MyCircularQueue) deQueue() bool {
    if this.isEmpty() {
        return false
    }
    this.front = (this.front + 1) % this.capacity
    this.size--
    return true
}

func (this *MyCircularQueue) Front() int {
    if this.isEmpty() {
        return -1
    }
    return this.queue[this.front]
}

func (this *MyCircularQueue) Rear() int {
    if this.isEmpty() {
        return -1
    }
    return this.queue[this.rear]
}

func (this *MyCircularQueue) isEmpty() bool {
    return this.size == 0
}

func (this *MyCircularQueue) isFull() bool {
    return this.size == this.capacity
}

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

#medium
Задача: 623. Add One Row to Tree

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

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

😎 Решение:

package main

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

func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
    if depth == 1 {
        return &TreeNode{Val: val, Left: root}
    }
    
    queue := []*TreeNode{root}
    currentDepth := 1
    
    for len(queue) > 0 {
        if currentDepth == depth-1 {
            for _, node := range queue {
                node.Left = &TreeNode{Val: val, Left: node.Left}
                node.Right = &TreeNode{Val: val, Right: node.Right}
            }
            break
        }
        currentDepth++
        nextQueue := []*TreeNode{}
        for _, node := range queue {
            if node.Left != nil {
                nextQueue = append(nextQueue, node.Left)
            }
            if node.Right != nil {
                nextQueue = append(nextQueue, node.Right)
            }
        }
        queue = nextQueue
    }
    
    return root
}

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

#medium
Задача: 624. Maximum Distance in Arrays

Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.

Пример:

Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4

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

1⃣Найдите минимальный элемент из всех первых элементов массивов и максимальный элемент из всех последних элементов массивов.

2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами.

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

😎 Решение:

package main

import (
    "math"
)

func maxDistance(arrays [][]int) int {
    minVal := arrays[0][0]
    maxVal := arrays[0][len(arrays[0])-1]
    maxDistance := 0
    
    for i := 1; i < len(arrays); i++ {
        maxDistance = int(math.Max(float64(maxDistance), math.Max(float64(abs(arrays[i][len(arrays[i])-1]-minVal)), float64(abs(arrays[i][0]-maxVal)))))
        minVal = int(math.Min(float64(minVal), float64(arrays[i][0])))
        maxVal = int(math.Max(float64(maxVal), float64(arrays[i][len(arrays[i])-1])))
    }
    
    return maxDistance
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

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

#medium
Задача: 625. Minimum Factorization

Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.

Пример:

Input: num = 48
Output: 68

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

1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.

2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.

3⃣Постройте результат, собирая найденные множители в обратном порядке. Если результат больше 32-битного целого числа, верните 0.

😎 Решение:

package main

import "math"

func smallestFactorization(num int) int {
    if num == 1 {
        return 1
    }
    
    factors := []int{}
    
    for i := 9; i >= 2; i-- {
        for num % i == 0 {
            factors = append(factors, i)
            num /= i
        }
    }
    
    if num > 1 {
        return 0
    }
    
    result := 0
    for i := len(factors) - 1; i >= 0; i-- {
        result = result * 10 + factors[i]
        if result > math.MaxInt32 {
            return 0
        }
    }
    
    return result
}

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

#easy
Задача: 628. Maximum Product of Three Numbers

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

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

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

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

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

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

😎 Решение:

package main

import (
    "sort"
)

func maximumProduct(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    max1 := nums[n-1] * nums[n-2] * nums[n-3]
    max2 := nums[0] * nums[1] * nums[n-1]
    if max1 > max2 {
        return max1
    }
    return max2
}

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

#hard
Задача: 629. K Inverse Pairs Array

Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3, k = 0
Output: 1

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

1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

3⃣Возвращение результата
Результатом будет значение dp[n][k].

😎 Решение:

package main

const MOD = 1000000007

func kInversePairs(n int, k int) int {
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
    }
    dp[0][0] = 1

    for i := 1; i <= n; i++ {
        dp[i][0] = 1
        for j := 1; j <= k; j++ {
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD
            if j >= i {
                dp[i][j] = (dp[i][j] - dp[i-1][j-i] + MOD) % MOD
            }
        }
    }

    return dp[n][k]
}

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

#easy
Задача: 434. Number of Segments in a String

Дана строка s, верните количество сегментов в строке.

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

Пример:

Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

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

1⃣Инициализируйте счетчик сегментов segment_count равным 0.

2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count.

3⃣Верните segment_count.

😎 Решение:

func countSegments(s string) int {
    segmentCount := 0

    for i := 0; i < len(s); i++ {
        if (i == 0 || s[i-1] == ' ') && s[i] != ' ' {
            segmentCount++
        }
    }

    return segmentCount
}

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

#hard
Задача: 630. Course Schedule III

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3

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

1⃣Сортировка курсов
Отсортируйте курсы по их конечным датам (lastDay). Это позволяет проходить курсы как можно ближе к их крайним срокам.

2⃣Проход по курсам
Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов.

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

😎 Решение:

import (
    "container/heap"
    "sort"
)

func scheduleCourse(courses [][]int) int {
    sort.Slice(courses, func(i, j int) bool {
        return courses[i][1] < courses[j][1]
    })

    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    totalTime := 0

    for _, course := range courses {
        duration := course[0]
        lastDay := course[1]
        heap.Push(maxHeap, duration)
        totalTime += duration

        if totalTime > lastDay {
            totalTime -= heap.Pop(maxHeap).(int)
        }
    }

    return maxHeap.Len()
}

type MaxHeap []int

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

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

#hard
Задача: 354. Russian Doll Envelopes

Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.

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

Примечание: Вы не можете поворачивать конверт.

Пример:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

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

1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).

2⃣Извлеките вторую размерность (высоты) отсортированного массива.

3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.

😎 Решение:

import (
    "sort"
)

func lengthOfLIS(nums []int) int {
    dp := []int{}
    for _, num := range nums {
        i := sort.Search(len(dp), func(i int) bool { return dp[i] >= num })
        if i < len(dp) {
            dp[i] = num
        } else {
            dp = append(dp, num)
        }
    }
    return len(dp)
}

func maxEnvelopes(envelopes [][]int) int {
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] > envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    secondDim := make([]int, len(envelopes))
    for i, envelope := range envelopes {
        secondDim[i] = envelope[1]
    }
    return lengthOfLIS(secondDim)
}

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

#hard
Задача: 631. Design Excel Sum Formula

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

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

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

2⃣Метод установки значений
Реализуйте метод set, который будет изменять значение ячейки в матрице.

3⃣Метод вычисления суммы
Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек.

😎 Решение:

package main

import (
    "fmt"
    "strconv"
)

type Excel struct {
    mat      [][]int
    formulas map[string][]string
}

func Constructor(height int, width byte) Excel {
    mat := make([][]int, height)
    for i := range mat {
        mat[i] = make([]int, width-'A'+1)
    }
    return Excel{mat: mat, formulas: make(map[string][]string)}
}

func (this *Excel) Set(row int, column byte, val int) {
    this.mat[row-1][column-'A'] = val
    key := strconv.Itoa(row) + string(column)
    delete(this.formulas, key)
}

func (this *Excel) Get(row int, column byte) int {
    key := strconv.Itoa(row) + string(column)
    if numbers, exists := this.formulas[key]; exists {
        return this.evaluateFormula(numbers)
    }
    return this.mat[row-1][column-'A']
}

func (this *Excel) Sum(row int, column byte, numbers []string) int {
    key := strconv.Itoa(row) + string(column)
    this.formulas[key] = numbers
    return this.evaluateFormula(numbers)
}

func (this *Excel) evaluateFormula(numbers []string) int {
    total := 0
    for _, number := range numbers {
        if idx := strings.Index(number, ":"); idx != -1 {
            start, end := number[:idx], number[idx+1:]
            startRow, _ := strconv.Atoi(start[1:])
            startCol := start[0]
            endRow, _ := strconv.Atoi(end[1:])
            endCol := end[0]
            for r := startRow; r <= endRow; r++ {
                for c := startCol; c <= endCol; c++ {
                    total += this.Get(r, c)
                }
            }
        } else {
            r, _ := strconv.Atoi(number[1:])
            c := number[0]
            total += this.Get(r, c)
        }
    }
    return total
}

func main() {
    obj := Constructor(3, 'C')
    obj.Set(1, 'A', 5)
    fmt.Println(obj.Get(1, 'A')) // 5
    fmt.Println(obj.Sum(1, 'B', []string{"A1", "A1"})) // 10
    obj.Set(1, 'A', 10)
    fmt.Println(obj.Get(1, 'B')) // 10
}

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