#medium
Задача: 515. Find Largest Value in Each Tree Row

Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).

Пример:

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

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

1⃣Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS).

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

3⃣Добавьте currMax в ans. Верните ans.

😎 Решение:

func largestValues(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    
    ans := []int{}
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        currentLength := len(queue)
        currMax := math.MinInt64
        
        for i := 0; i < currentLength; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Val > currMax {
                currMax = node.Val
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        
        ans = append(ans, currMax)
    }
    
    return ans
}

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

#medium
Задача: 516. Longest Palindromic Subsequence

Дана строка s, найдите длину самой длинной палиндромной подпоследовательности в s.

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

Пример:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

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

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте двумерный массив memo размером n на n, где memo[i][j] содержит длину самой длинной палиндромной подпоследовательности подстроки, сформированной от индекса i до j в s.

2⃣Верните lps(s, 0, n - 1, memo), где lps — это рекурсивный метод с четырьмя параметрами: s, начальный индекс подстроки как i, конечный индекс подстроки как j и memo. Если memo[i][j] != 0, это означает, что мы уже решили эту подзадачу, поэтому возвращаем memo[i][j]. Если i > j, строка пуста, возвращаем 0. Если i == j, это подстрока, содержащая один символ, возвращаем 1.

3⃣Если первый и последний символы совпадают, т.е. s[i] == s[j], включаем эти два символа в палиндромную подпоследовательность и добавляем её к самой длинной палиндромной подпоследовательности, сформированной с использованием подстроки от индекса i + 1 до j - 1. Выполняем memo[i][j] = lps(s, i + 1, j - 1, memo) + 2. Если первый и последний символы не совпадают, рекурсивно ищем самую длинную палиндромную подпоследовательность в обеих подстроках, сформированных после игнорирования первого и последнего символов. Выбираем максимум из этих двух и выполняем memo[i][j] = max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo)). Возвращаем memo[i][j].

😎 Решение:

func longestPalindromeSubseq(s string) int {
    n := len(s)
    memo := make(map[[2]int]int)
    
    var lps func(int, int) int
    lps = func(l, r int) int {
        if val, ok := memo[[2]int{l, r}]; ok {
            return val
        }
        if l > r {
            return 0
        }
        if l == r {
            return 1
        }
        
        if s[l] == s[r] {
            memo[[2]int{l, r}] = lps(l + 1, r - 1) + 2
        } else {
            memo[[2]int{l, r}] = max(lps(l, r - 1), lps(l + 1, r))
        }
        return memo[[2]int{l, r}]
    }
    
    return lps(0, n - 1)
}

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

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

#hard
Задача: 517. Super Washing Machines

У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.

За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.

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

Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

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

1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎 Решение:

func findMinMoves(machines []int) int {
    n := len(machines)
    dressTotal := 0
    for _, m := range machines {
        dressTotal += m
    }
    if dressTotal % n != 0 {
        return -1
    }

    dressPerMachine := dressTotal / n
    for i := range machines {
        machines[i] -= dressPerMachine
    }

    currSum, maxSum, res := 0, 0, 0
    for _, m := range machines {
        currSum += m
        maxSum = max(maxSum, abs(currSum))
        res = max(res, max(maxSum, m))
    }
    return res
}

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

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

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

#medium
Задача: 518. Coin Change II

Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0.

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

Ответ гарантированно вписывается в знаковое 32-битное целое число.

Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

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

1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты.

2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его.

3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу.

😎 Решение:

func change(amount int, coins []int) int {
    memo := make([][]int, len(coins))
    for i := range coins {
        memo[i] = make([]int, amount + 1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var numberOfWays func(i, amount int) int
    numberOfWays = func(i, amount int) int {
        if amount == 0 {
            return 1
        }
        if i == len(coins) {
            return 0
        }
        if memo[i][amount] != -1 {
            return memo[i][amount]
        }

        if coins[i] > amount {
            memo[i][amount] = numberOfWays(i + 1, amount)
        } else {
            memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
        }
        return memo[i][amount]
    }

    return numberOfWays(0, amount)
}

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

#easy
Задача: 520. Detect Capital

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

import (
    "regexp"
)

func detectCapitalUse(word string) bool {
    pattern := "^[A-Z]*$|^[a-z]*$|^[A-Z][a-z]*$"
    match, _ := regexp.MatchString(pattern, word)
    return match
}

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

#hard
Задача: 632. Smallest Range Covering Elements from K Lists

У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c.

Пример:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

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

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

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

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

😎 Решение:

package main

import (
  "container/heap"
  "fmt"
  "math"
)

type Element struct {
  value int
  row   int
  col   int
}

type MinHeap []Element

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].value < h[j].value }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
  *h = append(*h, x.(Element))
}

func (h *MinHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func smallestRange(nums [][]int) []int {
  minHeap := &MinHeap{}
  heap.Init(minHeap)
  maxValue := math.MinInt64

  for i := 0; i < len(nums); i++ {
    heap.Push(minHeap, Element{value: nums[i][0], row: i, col: 0})
    if nums[i][0] > maxValue {
      maxValue = nums[i][0]
    }
  }

  rangeStart, rangeEnd := 0, math.MaxInt64

  for minHeap.Len() == len(nums) {
    minElement := heap.Pop(minHeap).(Element)
    if maxValue-minElement.value < rangeEnd-rangeStart {
      rangeStart, rangeEnd = minElement.value, maxValue
    }

    if minElement.col+1 < len(nums[minElement.row]) {
      newValue := nums[minElement.row][minElement.col+1]
      heap.Push(minHeap, Element{value: newValue, row: minElement.row, col: minElement.col + 1})
      if newValue > maxValue {
        maxValue = newValue
      }
    }
  }

  return []int{rangeStart, rangeEnd}
}

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

#easy
Задача: 521. Longest Uncommon Subsequence I

Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1.

Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них.

Пример:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

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

1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности.

2⃣В противном случае: Вычислите длины строк a и b. Верните длину более длинной строки.

😎 Решение:

func findLUSlength(a string, b string) int {
    if a == b {
        return -1
    } else {
        if len(a) > len(b) {
            return len(a)
        } else {
            return len(b)
        }
    }
}

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

#medium
Задача: 523. Continuous Subarray Sum

Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае.

Хороший подмассив — это подмассив, который:

имеет длину не менее двух, и
сумма элементов подмассива является кратной k.
Учтите:

Подмассив — это непрерывная часть массива.
Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k.

Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

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

1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

2⃣Итеративно пройдите по всем элементам массива nums.

3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false.

😎 Решение:

func checkSubarraySum(nums []int, k int) bool {
    prefixMod := 0
    modSeen := map[int]int{0: -1}
    
    for i, num := range nums {
        prefixMod = (prefixMod + num) % k
        
        if prevIndex, exists := modSeen[prefixMod]; exists {
            if i - prevIndex > 1 {
                return true
            }
        } else {
            modSeen[prefixMod] = i
        }
    }
    
    return false
}

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

#Easy
Задача: 604. Design Compressed String Iterator

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

Реализуйте класс StringIterator:

- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.

Пример:

Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]

Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

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

1⃣Предварительная обработка
Мы заранее создаем несжатую строку. Для этого проходим по данному сжатому строковому представлению и добавляем несжатые буквы для каждой сжатой буквы в результирующий строковый строитель res. Чтобы найти количество несжатых букв, мы проходим по данному сжатому строковому представлению. Когда находим букву, определяем следующее за ней число, используя десятичную арифметику. Таким образом, получаем два элемента (букву и количество), необходимые для формирования текущего фрагмента несжатой строки.

2⃣Операция next()
Начинаем с проверки, есть ли еще несжатые буквы в строке. Если нет, hasNext() возвращает False, а next() возвращает пробел (' '). В противном случае возвращаем букву, на которую указывает ptr, указывающий на следующую букву для возврата. Перед возвратом буквы также обновляем ptr, чтобы указывать на следующую букву в res.

3⃣Операция hasNext()
Если указатель ptr выходит за пределы массива res, это указывает на то, что больше несжатых букв нет. В этом случае возвращаем False. В противном случае возвращаем True.

😎 Решение:

package main

type StringIterator struct {
    res []rune
    ptr int
}

func Constructor(s string) StringIterator {
    res := []rune{}
    i := 0
    for i < len(s) {
        ch := rune(s[i])
        i++
        num := 0
        for i < len(s) && s[i] >= '0' && s[i] <= '9' {
            num = num*10 + int(s[i]-'0')
            i++
        }
        for j := 0; j < num; j++ {
            res = append(res, ch)
        }
    }
    return StringIterator{res: res, ptr: 0}
}

func (this *StringIterator) Next() rune {
    if !this.HasNext() {
        return ' '
    }
    ch := this.res[this.ptr]
    this.ptr++
    return ch
}

func (this *StringIterator) HasNext() bool {
    return this.ptr < len(this.res)
}

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

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

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