#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
}

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

#medium
Задача: 435. Non-overlapping Intervals

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

1⃣Отсортируйте интервалы по времени окончания.

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

import (
    "sort"
    "math"
)

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    ans := 0
    k := math.MinInt32
    
    for _, interval := range intervals {
        x := interval[0]
        y := interval[1]
        if x >= k {
            k = y
        } else {
            ans++
        }
    }
    
    return ans
}

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

#hard
Задача: 358. Rearrange String k Distance Apart

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

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

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

1⃣Создайте словарь частот для символов строки и определите максимальную частоту.

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

3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎 Решение:

import (
    "strings"
)

func rearrangeString(s string, k int) string {
    freqs := make(map[byte]int)
    maxFreq := 0
    
    for i := 0; i < len(s); i++ {
        freqs[s[i]]++
        if freqs[s[i]] > maxFreq {
            maxFreq = freqs[s[i]]
        }
    }
    
    mostChars := make(map[byte]bool)
    secondChars := make(map[byte]bool)
    
    for c, freq := range freqs {
        if freq == maxFreq {
            mostChars[c] = true
        } else if freq == maxFreq-1 {
            secondChars[c] = true
        }
    }
    
    segments := make([]strings.Builder, maxFreq)
    
    for i := 0; i < maxFreq; i++ {
        for c := range mostChars {
            segments[i].WriteByte(c)
        }
        if i < maxFreq-1 {
            for c := range secondChars {
                segments[i].WriteByte(c)
            }
        }
    }
    
    segmentId := 0
    
    for c, freq := range freqs {
        if mostChars[c] || secondChars[c] {
            continue
        }
        
        for freq > 0 {
            segments[segmentId].WriteByte(c)
            segmentId = (segmentId + 1) % (maxFreq - 1)
            freq--
        }
    }
    
    for i := 0; i < maxFreq-1; i++ {
        if segments[i].Len() < k {
            return ""
        }
    }
    
    var result strings.Builder
    for i := 0; i < maxFreq; i++ {
        result.WriteString(segments[i].String())
    }
    
    return result.String()
}

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

#easy
Задача: 559. Maximum Depth of N-ary Tree

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

Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.

Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры).

Пример:

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

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

1⃣Интуитивный подход заключается в решении задачи с помощью рекурсии.

2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search).

3⃣Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину.

😎 Решение:

type Node struct {
    Val      int
    Children []*Node
}

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    } else if len(root.Children) == 0 {
        return 1
    } else {
        heights := []int{}
        for _, child := range root.Children {
            heights = append(heights, maxDepth(child))
        }
        max := 0
        for _, h := range heights {
            if h > max {
                max = h
            }
        }
        return max + 1
    }
}

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

Задача: 560. Subarray Sum Equals K

Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.

Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

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

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k.

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

😎 Решение:

func subarraySum(nums []int, k int) int {
    count := 0
    for start := 0; start < len(nums); start++ {
        for end := start + 1; end <= len(nums); end++ {
            sum := 0
            for i := start; i < end; i++ {
                sum += nums[i]
            }
            if sum == k {
                count++
            }
        }
    }
    return count
}

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

#easy
Задача: 561. Array Partition

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

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

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

import "sort"

func arrayPairSum(nums []int) int {
    sort.Ints(nums)
    sum := 0
    for i := 0; i < len(nums); i += 2 {
        sum += nums[i]
    }
    return sum
}

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

#medium
Задача: 562. Longest Line of Consecutive One in Matrix

Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.

Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.

Пример:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

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

1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.

2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.

3⃣Верните максимальную длину.

😎 Решение:

func longestLine(mat [][]int) int {
    if len(mat) == 0 || len(mat[0]) == 0 {
        return 0
    }
    
    m, n := len(mat), len(mat[0])
    maxLength := 0
    
    horizontal := make([][]int, m)
    vertical := make([][]int, m)
    diagonal := make([][]int, m)
    antiDiagonal := make([][]int, m)
    
    for i := range mat {
        horizontal[i] = make([]int, n)
        vertical[i] = make([]int, n)
        diagonal[i] = make([]int, n)
        antiDiagonal[i] = make([]int, n)
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] == 1 {
                horizontal[i][j] = 1 + if j > 0 { horizontal[i][j-1] } else { 0 }
                vertical[i][j] = 1 + if i > 0 { vertical[i-1][j] } else { 0 }
                diagonal[i][j] = 1 + if i > 0 && j > 0 { diagonal[i-1][j-1] } else { 0 }
                antiDiagonal[i][j] = 1 + if i > 0 && j < n-1 { antiDiagonal[i-1][j+1] } else { 0 }
                
                maxLength = max(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j])
            }
        }
    }
    
    return maxLength
}

func max(vals ...int) int {
    maxVal := vals[0]
    for _, val := range vals {
        if val > maxVal {
            maxVal = val
        }
    }
    return maxVal
}

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

#easy
Задача: 563. Binary Tree Tilt

Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.

Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.

Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

1⃣Определите рекурсивную функцию, которая вычисляет сумму значений узлов поддерева и наклон текущего узла.

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

3⃣Верните общую сумму наклонов всех узлов.

😎 Решение:

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

func findTilt(root *TreeNode) int {
    totalTilt := 0
    
    var sumAndTilt func(node *TreeNode) int
    sumAndTilt = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftSum := sumAndTilt(node.Left)
        rightSum := sumAndTilt(node.Right)
        nodeTilt := abs(leftSum - rightSum)
        totalTilt += nodeTilt
        return node.Val + leftSum + rightSum
    }
    
    sumAndTilt(root)
    return totalTilt
}

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

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

📊 Реклама в сети телеграм каналов easyoffer
✈️ Для заказа пишите @easyoffer_adv

easyoffer
Backend

Python | Вопросы
Python | Удалёнка
Python | LeetCode
Python | Тесты

Frontend | Вопросы
Frontend | Удалёнка
JavaScript | LeetCode
Frontend | Тесты

Java | Вопросы
Java | Удалёнка
Java | LeetCode
Java | Тесты

Тестировщик | Вопросы
Тестировщик | Удалёнка
Тестировщик | Тесты

Data Science | Вопросы
Data Science | Удалёнка
Data Science | Тесты

C# | Вопросы
C# | Удалёнка
C# | LeetCode
C# | Тесты

C/C++ | Вопросы
C/C++ | Удалёнка
C/C++ | LeetCode
C/C++ | Тесты

Golang | Вопросы
Golang | Удалёнка
Golang | LeetCode
Golang | Тесты

DevOps | Вопросы
DevOps | Удалёнка
DevOps | Тесты

PHP | Вопросы
PHP | Удалёнка
PHP | LeetCode
PHP | Тесты

Kotlin | Вопросы
Kotlin | Удалёнка
Kotlin | LeetCode
Kotlin | Тесты

Swift | Вопросы
Swift | Удалёнка
Swift | LeetCode
Swift | Тесты

📊 Реклама в сети телеграм каналов easyoffer
✈️ Для заказа пишите @easyoffer_adv

#medium
Задача: 565. Array Nesting

Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1].

Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:

Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.
Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.
Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.

Верните длину самого длинного множества s[k].

Пример:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

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

1⃣Создайте массив для отслеживания посещенных элементов.

2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.

3⃣Обновите максимальную длину найденного множества.

😎 Решение:

func arrayNesting(nums []int) int {
    visited := make([]bool, len(nums))
    maxLength := 0
    
    for i := 0; i < len(nums); i++ {
        if !visited[i] {
            start := i
            count := 0
            for !visited[start] {
                visited[start] = true
                start = nums[start]
                count++
            }
            if count > maxLength {
                maxLength = count
            }
        }
    }
    
    return maxLength
}

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