#medium
Задача: 250. Count Univalue Subtrees

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

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

Пример:

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

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

1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.

2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, верните true.
Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false.

3️⃣Верните count.

😎 Решение:

package main

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

type Solution struct {
    count int
}

func (s *Solution) dfs(node *TreeNode) bool {
    if node == nil {
        return true
    }

    isLeftUniValue := s.dfs(node.Left)
    isRightUniValue := s.dfs(node.Right)

    if isLeftUniValue && isRightUniValue {
        if node.Left != nil && node.Left.Val != node.Val {
            return false
        }
        if node.Right != nil && node.Right.Val != node.Val {
            return false
        }
        s.count++
        return true
    }
    return false
}

func (s *Solution) CountUnivalSubtrees(root *TreeNode) int {
    s.dfs(root)
    return s.count
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 267. Palindrome Permutation II

Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.

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

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

1️⃣Проверка на возможность палиндромной перестановки:
Создаем хеш-таблицу, которая хранит количество вхождений каждого символа строки s.
Если количество символов с нечетным количеством вхождений превышает 1, то палиндромная перестановка
невозможна, и мы возвращаем пустой список.

2️⃣Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.

3️⃣Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.

😎 Решение:

package main

import (
  "fmt"
  "strings"
)

type Solution struct {
  set map[string]struct{}
}

func NewSolution() *Solution {
  return &Solution{set: make(map[string]struct{})}
}

func (sol *Solution) generatePalindromes(s string) []string {
  mapChars := make([]int, 128)
  st := make([]rune, len(s)/2)
  if !sol.canPermutePalindrome(s, mapChars) {
    return []string{}
  }

  var ch rune
  k := 0
  for i := 0; i < len(mapChars); i++ {
    if mapChars[i]%2 == 1 {
      ch = rune(i)
    }
    for j := 0; j < mapChars[i]/2; j++ {
      st[k] = rune(i)
      k++
    }
  }
  sol.permute(st, 0, ch)
  result := []string{}
  for key := range sol.set {
    result = append(result, key)
  }
  return result
}

func (sol *Solution) canPermutePalindrome(s string, mapChars []int) bool {
  count := 0
  for _, char := range s {
    index := int(char)
    mapChars[index]++
    if mapChars[index]%2 == 0 {
      count--
    } else {
      count++
    }
  }
  return count <= 1
}

func (sol *Solution) swap(s []rune, i, j int) {
  s[i], s[j] = s[j], s[i]
}

func (sol *Solution) permute(s []rune, l int, ch rune) {
  if l == len(s) {
    var sb strings.Builder
    sb.WriteString(string(s))
    if ch != 0 {
      sb.WriteRune(ch)
    }
    for i := len(s) - 1; i >= 0; i-- {
      sb.WriteRune(s[i])
    }
    sol.set[sb.String()] = struct{}{}
  } else {
    for i := l; i < len(s); i++ {
      if s[l] != s[i] || l == i {
        sol.swap(s, l, i)
        sol.permute(s, l+1, ch)
        sol.swap(s, l, i)
      }
    }
  }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 251. Flatten 2D Vector

Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.

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

Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.

Пример:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

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

1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента.

2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.

3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().

😎 Решение:

type Vector2D struct {
    nums    []int
    position int
}

func Constructor(v [][]int) Vector2D {
    nums := make([]int, 0)
    for _, innerList := range v {
        nums = append(nums, innerList...)
    }
    return Vector2D{nums, -1}
}

func (this *Vector2D) Next() int {
    this.position++
    return this.nums[this.position]
}

func (this *Vector2D) HasNext() bool {
    return this.position + 1 < len(this.nums)
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 268. Missing Number

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1️⃣Сначала отсортируйте массив nums.

2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число.

😎 Решение:

func missingNumber(nums []int) int {
    sort.Ints(nums)
    if nums[len(nums)-1] != len(nums) {
        return len(nums)
    } else if nums[0] != 0 {
        return 0
    }
    for i := 1; i < len(nums); i++ {
        expectedNum := nums[i-1] + 1
        if nums[i] != expectedNum {
            return expectedNum
        }
    }
    return -1
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 269. Alien Dictionary

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

import (
    "container/list"
    "strings"
)

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

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

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

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

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

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

    return output.String()
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 270. Closest Binary Search Tree Value

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

Пример:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

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

1️⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2️⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

3️⃣Выбрать наименьший из ближайших элементов:
Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них.

😎 Решение:

package main

import "math"

func closestValue(root *TreeNode, target float64) int {
    closest := root.Val
    for root != nil {
        if math.Abs(float64(root.Val)-target) < math.Abs(float64(closest)-target) {
            closest = root.Val
        } else if math.Abs(float64(root.Val)-target) == math.Abs(float64(closest)-target) {
            if root.Val < closest {
                closest = root.Val
            }
        }
        if target < float64(root.Val) {
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return closest
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 213. House Robber II

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

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

Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

1️⃣ Обработка базовых случаев:
Если массив nums пуст, возвращаем 0.
Если в массиве nums только один дом, возвращаем значение этого дома.

2️⃣ Разделение задачи на две подзадачи:
Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию robSimple с параметрами 0 и len(nums)-2.
Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию robSimple с параметрами 1 и len(nums)-1.

3️⃣ Сравнение результатов и возврат максимального значения:
Вернуть максимальное значение из двух полученных результатов.

😎 Решение:

package main

import (
    "fmt"
    "math"
)

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }

    max1 := robSimple(nums, 0, len(nums)-2)
    max2 := robSimple(nums, 1, len(nums)-1)

    return int(math.Max(float64(max1), float64(max2)))
}

func robSimple(nums []int, start, end int) int {
    t1, t2 := 0, 0

    for i := start; i <= end; i++ {
        temp := t1
        current := nums[i]
        t1 = int(math.Max(float64(current+t2), float64(t1)))
        t2 = temp
    }

    return t1
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 272. Closest Binary Search Tree Value II

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

Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.

Пример:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

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

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

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

3️⃣Вернуть первые k значений из отсортированного массива:
Извлечь первые k элементов из отсортированного массива и вернуть их.

😎 Решение:

import (
    "math"
    "sort"
)

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

func closestKValues(root *TreeNode, target float64, k int) []int {
    var arr []int
    dfs(root, &arr)
    sort.Slice(arr, func(i, j int) bool {
        return math.Abs(float64(arr[i])-target) < math.Abs(float64(arr[j])-target)
    })
    return arr[:k]
}

func dfs(node *TreeNode, arr *[]int) {
    if node == nil {
        return
    }
    *arr = append(*arr, node.Val)
    dfs(node.Left, arr)
    dfs(node.Right, arr)
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 214. Shortest Palindrome

Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.

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

Пример:

Input: s = "aacecaaa"
Output: "aaacecaaa"

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

1️⃣ Создание обратной строки:
Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения.

2️⃣ Итерация для поиска наибольшего палиндрома:
Перебирайте индекс i от 0 до size(s) - 1.
Для каждой итерации проверяйте, равна ли подстрока s от начала до n - i подстроке rev от i до конца строки.
Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом, так как rev является обратной строкой s.

3️⃣ Возврат результата:
Как только найден наибольший палиндром, возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s.

😎 Решение:

package main

import (
  "fmt"
  "strings"
)

func shortestPalindrome(s string) string {
  n := len(s)
  rev := reverseString(s)
  for i := 0; i < n; i++ {
    if s[:n-i] == rev[i:] {
      return rev[:i] + s
    }
  }
  return ""
}

func reverseString(s string) string {
  runes := []rune(s)
  for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
    runes[i], runes[j] = runes[j], runes[i]
  }
  return string(runes)
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 273. Integer to English Words

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

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

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

1️⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

2️⃣Обработка сотен, тысяч, миллионов и миллиардов:
Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды).
Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999.

3️⃣Формирование окончательного результата:
Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды).
Соединить все части в одну строку, удалив лишние пробелы.

😎 Решение:

package main

import (
    "strings"
    "strconv"
)

func numberToWords(num int) string {
    if num == 0 {
        return "Zero"
    }

    belowTwenty := []string{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}
    tens := []string{"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}
    thousands := []string{"", "Thousand", "Million", "Billion"}

    var result string
    i := 0

    for num > 0 {
        if num%1000 != 0 {
            result = helper(num%1000, belowTwenty, tens) + thousands[i] + " " + result
        }
        num /= 1000
        i++
    }
    return strings.TrimSpace(result)
}

func helper(num int, belowTwenty, tens []string) string {
    if num == 0 {
        return ""
    } else if num < 20 {
        return belowTwenty[num] + " "
    } else if num < 100 {
        return tens[num/10] + " " + helper(num%10, belowTwenty, tens)
    } else {
        return belowTwenty[num/100] + " Hundred " + helper(num%100, belowTwenty, tens)
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 215. Kth Largest Element in an Array

Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.

Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.

Пример:

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

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

1️⃣ Отсортируйте массив в порядке убывания:
Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее.

2️⃣ Найдите k-й по величине элемент:
После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0).

3️⃣ Верните результат:
Возвратите найденное значение как результат.

😎 Решение:

package main

import (
  "strings"
)

func shortestPalindrome(s string) string {
  n := len(s)
  rev := reverseString(s)
  for i := 0; i < n; i++ {
    if s[:n-i] == rev[i:] {
      return rev[:i] + s
    }
  }
  return ""
}

func reverseString(s string) string {
  runes := []rune(s)
  for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
    runes[i], runes[j] = runes[j], runes[i]
  }
  return string(runes)
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 274. H-Index

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.

Пример:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1️⃣Отсортировать массив цитирований по убыванию:
Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива.

2️⃣Найти наибольшее значение i, для которого citations[i] > i:
Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i.
Это значение будет индексом, при котором количество цитирований статьи больше индекса.

3️⃣Рассчитать h-индекс:
h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге.

😎 Решение:

func hIndex(citations []int) int {
    n := len(citations)
    papers := make([]int, n+1)
    for _, c := range citations {
        if c >= n {
            papers[n]++
        } else {
            papers[c]++
        }
    }
    k := n
    s := papers[n]
    for k > s {
        k--
        s += papers[k]
    }
    return k
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 216. Combination Sum III

Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:

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

Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

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

1️⃣ Инициализация и запуск рекурсивной функции:
Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов.
Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов.
Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов.

2️⃣ Рекурсивная обработка:
В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов.
Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки.
Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата.

3️⃣ Возвращение результатов:
По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций.

😎 Решение:

package main

func backtrack(remain int, k int, comb []int, nextStart int, results *[][]int) {
    if remain == 0 && len(comb) == k {
        temp := make([]int, len(comb))
        copy(temp, comb)
        *results = append(*results, temp)
        return
    } else if remain < 0 || len(comb) == k {
        return
    }

    for i := nextStart; i < 9; i++ {
        comb = append(comb, i+1)
        backtrack(remain-i-1, k, comb, i+1, results)
        comb = comb[:len(comb)-1]
    }
}

func combinationSum3(k int, n int) [][]int {
    var results [][]int
    var comb []int
    backtrack(n, k, comb, 0, &results)
    return results
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 275. H-Index II

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.

Пример:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1️⃣Найти середину массива:
Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n].

2️⃣Сравнить количество статей с цитированиями больше или равными citations[mid]:
Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.
Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].
Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3️⃣Возвращение результата:
Продолжать процесс, пока не будет найден h-индекс.
Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎 Решение:

func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n - 1
    
    for left <= right {
        mid := left + (right - left) / 2
        if citations[mid] == n - mid {
            return n - mid
        } else if citations[mid] < n - mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return n - left
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 217. Contains Duplicate

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

Пример:

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

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

1️⃣ Отсортируйте массив nums по возрастанию.

2️⃣ Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим.

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

😎 Решение:

import "sort"

func containsDuplicate(nums []int) bool {
    sort.Ints(nums)
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] == nums[i+1] {
            return true
        }
    }
    return false
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 218. The Skyline Problem

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

Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:

lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.

Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

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

1️⃣ Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights.

2️⃣ Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex).

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

😎 Решение:

func getSkyline(buildings [][]int) [][]int {
    edgeSet := make(map[int]struct{})
    for _, building := range buildings {
        edgeSet[building[0]] = struct{}{}
        edgeSet[building[1]] = struct{}{}
    }
    edges := make([]int, 0, len(edgeSet))
    for edge := range edgeSet {
        edges = append(edges, edge)
    }
    sort.Ints(edges)
    edgeIndexMap := make(map[int]int)
    for i, edge := range edges {
        edgeIndexMap[edge] = i
    }
    heights := make([]int, len(edges))
    for _, building := range buildings {
        left, right, height := building[0], building[1], building[2]
        leftIndex, rightIndex := edgeIndexMap[left], edgeIndexMap[right]
        for idx := leftIndex; idx < rightIndex; idx++ {
            if heights[idx] < height {
                heights[idx] = height
            }
        }
    }
    var answer [][]int
    for i, currHeight := range heights {
        currPos := edges[i]
        if len(answer) == 0 || answer[len(answer)-1][1] != currHeight {
            answer = append(answer, []int{currPos, currHeight})
        }
    }
    return answer
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 276. Paint Fence

Вы красите забор из n столбцов, используя k различных цветов. Вы должны красить столбы, следуя этим правилам:
Каждый столб должен быть окрашен в один цвет.
Не может быть трех или более подряд идущих столбцов одного цвета.
Учитывая два целых числа n и k, верните количество способов покрасить забор.

Пример:

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

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

1️⃣Инициализация и определение вспомогательной функции:
Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов.
Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов.

2️⃣Реализация базы и проверка кэша:
В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2.
Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i].

3️⃣Расчет с использованием рекуррентного соотношения:
В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его.
Вызвать и вернуть totalWays(n).

😎 Решение:

func numWays(n int, k int) int {
    if n == 1 {
        return k
    }
    
    twoPostsBack := k
    onePostBack := k * k
    
    for i := 3; i <= n; i++ {
        curr := (k - 1) * (onePostBack + twoPostsBack)
        twoPostsBack = onePostBack
        onePostBack = curr
    }
    
    return onePostBack
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 219. Contains Duplicate II

Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k.

Пример:

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

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

1️⃣ Создайте пустое множество set.

2️⃣ Пройдитесь по массиву nums:
Если текущий элемент уже есть в множестве, верните true.
Добавьте текущий элемент в множество.
Если размер множества больше k, удалите элемент, который был добавлен k шагов назад.

3️⃣ Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false.

😎 Решение:

func containsNearbyDuplicate(nums []int, k int) bool {
    set := make(map[int]struct{})
    for i, num := range nums {
        if _, exists := set[num]; exists {
            return true
        }
        set[num] = struct{}{}
        if len(set) > k {
            delete(set, nums[i-k])
        }
    }
    return false
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 314. Binary Tree Vertical Order Traversal

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

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

Пример:

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

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

1️⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2️⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

3️⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам.

😎 Решение:

package main

import (
    "sort"
    "container/list"
)

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

func verticalOrder(root *TreeNode) [][]int {
    var output [][]int
    if root == nil {
        return output
    }

    columnTable := map[int][]int{}
    queue := list.New()
    queue.PushBack([2]interface{}{root, 0})

    for queue.Len() > 0 {
        element := queue.Front()
        queue.Remove(element)
        pair := element.Value.([2]interface{})
        node := pair[0].(*TreeNode)
        column := pair[1].(int)

        if node != nil {
            columnTable[column] = append(columnTable[column], node.Val)

            if node.Left != nil {
                queue.PushBack([2]interface{}{node.Left, column - 1})
            }
            if node.Right != nil {
                queue.PushBack([2]interface{}{node.Right, column + 1})
            }
        }
    }

    var sortedKeys []int
    for key := range columnTable {
        sortedKeys = append(sortedKeys, key)
    }
    sort.Ints(sortedKeys)

    for _, key := range sortedKeys {
        output = append(output, columnTable[key])
    }

    return output
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых