Задача: 1134. Armstrong Number
Сложность: easy

Дано целое число n, верните true, если и только если оно является числом Армстронга.

k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.

Пример:

Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.

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

1⃣Получите количество цифр в n, преобразовав его в строку и найдя длину.

2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n.
Инициализируйте переменную result для хранения результата.
Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру.

3⃣Верните true, если результат равен исходному числу n.

😎 Решение:

import "math"

func getSumOfKthPowerOfDigits(n, k int) int {
    result := 0
    for n != 0 {
        digit := n % 10
        result += int(math.Pow(float64(digit), float64(k)))
        n /= 10
    }
    return result
}

func isArmstrong(n int) bool {
    length := len(strconv.Itoa(n))
    return getSumOfKthPowerOfDigits(n, length) == n
}

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

Задача: 142. Linked List Cycle II
Сложность: medium

Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.

Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.

Не модифицируйте связный список.

Пример:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

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

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

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

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

😎 Решение:

type ListNode struct {
    Val  int
    Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
    nodesSeen := make(map[*ListNode]bool)
    node := head
    for node != nil {
        if _, ok := nodesSeen[node]; ok {
            return node
        } else {
            nodesSeen[node] = true
            node = node.Next
        }
    }
    return nil
}

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

Задача: 1325. Delete Leaves With a Given Value
Сложность: medium

Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target.

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

Пример:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

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

1⃣Базовый случай: Если root равен null, верните null, чтобы обработать условия пустого дерева или прохождения за пределы листовых узлов.

2⃣Рекурсивный обход: Выполните обход в постфиксном порядке, чтобы гарантировать обработку всех потомков перед текущим узлом (root):
— Рекурсивно вызовите removeLeafNodes для левого дочернего узла root и обновите левый дочерний узел возвращаемым значением.
— Аналогично, рекурсивно вызовите removeLeafNodes для правого дочернего узла root и обновите правый дочерний узел возвращаемым значением.

3⃣Оценка узла:
— Проверьте, является ли текущий узел root листовым узлом и совпадает ли его значение с target. Если оба условия выполнены, верните null, чтобы эффективно удалить узел, не присоединяя его к родителю.
— Если узел не является листом или не совпадает с target, верните сам root.

😎 Решение

func removeLeafNodes(root *TreeNode, target int) *TreeNode {
    if root == nil {
        return nil
    }

    root.Left = removeLeafNodes(root.Left, target)
    root.Right = removeLeafNodes(root.Right, target)

    if root.Left == nil && root.Right == nil && root.Val == target {
        return nil
    }
    return root
}

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

Задача: 126. Word Ladder II
Сложность: hard

Дано beginWord, endWord и wordList. Нужно найти все кратчайшие последовательности преобразования beginWord -> s1 -> s2 -> ... -> sk, где:

- Каждое слово отличается от предыдущего ровно одной буквой.
- Каждое слово есть в wordList.
- Последнее слово sk совпадает с endWord.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]  
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]  

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

1⃣Добавляем wordList в wordSet для быстрого поиска.

2⃣Запускаем BFS, строим adjList — список смежности, где храним связи между словами.

3⃣Используем backtracking, чтобы восстановить пути от endWord к beginWord.

😎 Решение:

func findLadders(beginWord, endWord string, wordList []string) [][]string {
    adjList := make(map[string][]string)
    wordSet := make(map[string]bool)
    for _, word := range wordList {
        wordSet[word] = true
    }

    bfs(beginWord, wordSet, adjList)
    var currPath []string
    var shortestPaths [][]string
    currPath = append(currPath, endWord)
    backtrack(endWord, beginWord, &currPath, &shortestPaths, adjList)
    return shortestPaths
}

func findNeighbors(word string, wordSet map[string]bool) []string {
    var neighbors []string
    charList := []rune(word)
    for i := range charList {
        oldChar := charList[i]
        for c := 'a'; c <= 'z'; c++ {
            if c != oldChar {
                charList[i] = c
                newWord := string(charList)
                if wordSet[newWord] {
                    neighbors = append(neighbors, newWord)
                }
            }
        }
        charList[i] = oldChar
    }
    return neighbors
}

func backtrack(source, destination string, currPath *[]string, shortestPaths *[][]string, adjList map[string][]string) {
    if source == destination {
        pathCopy := make([]string, len(*currPath))
        copy(pathCopy, *currPath)
        reverse(pathCopy)
        *shortestPaths = append(*shortestPaths, pathCopy)
        return
    }
    for _, neighbor := range adjList[source] {
        *currPath = append(*currPath, neighbor)
        backtrack(neighbor, destination, currPath, shortestPaths, adjList)
        *currPath = (*currPath)[:len(*currPath)-1]
    }
}

func bfs(beginWord string, wordSet map[string]bool, adjList map[string][]string) {
    queue := []string{beginWord}
    visited := make(map[string]bool)
    visited[beginWord] = true

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        neighbors := findNeighbors(current, wordSet)
        for _, neighbor := range neighbors {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
                adjList[neighbor] = append(adjList[neighbor], current)
            }
        }
    }
}

func reverse(slice []string) {
    for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
        slice[i], slice[j] = slice[j], slice[i]
    }
}

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

Задача: 98. Validate Binary Search Tree
Сложность: medium

Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST).

Допустимое BST определяется следующим образом:

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

Пример:

Input: root = [2,1,3]
Output: true

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

1⃣Давайте воспользуемся порядком узлов при симметричном обходе (inorder traversal):
Левый -> Узел -> Правый.
Постордер:
Здесь узлы перечисляются в порядке их посещения, и вы можете следовать последовательности 1-2-3-4-5 для сравнения различных стратегий.
Порядок "Левый -> Узел -> Правый" при симметричном обходе означает, что для BST каждый элемент должен быть меньше следующего.

2⃣Следовательно, алгоритм с временной сложностью O(N) и пространственной сложностью O(N) может быть простым:
Вычислить список симметричного обхода inorder.
Проверить, меньше ли каждый элемент в списке inorder следующего за ним.

3⃣Нужно ли сохранять весь список симметричного обхода?
На самом деле, нет. Достаточно последнего добавленного элемента inorder, чтобы на каждом шаге убедиться, что дерево является BST (или нет). Следовательно, можно объединить оба шага в один и уменьшить используемое пространство.

😎 Решение:

var prev *TreeNode

func inorder(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if !inorder(root.Left) {
        return false
    }
    if prev != nil && root.Val <= prev.Val {
        return false
    }
    prev = root
    return inorder(root.Right)
}

func isValidBST(root *TreeNode) bool {
    prev = nil
    return inorder(root)
}

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

Задача: 899. Orderly Queue
Сложность: hard

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

Пример:

Input: s = "cba", k = 1
Output: "acb"

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

1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта.

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

3⃣Вернуть результат.

😎 Решение:

package main

import (
    "sort"
    "strings"
)

func orderlyQueue(s string, k int) string {
    if k == 1 {
        minString := s
        for i := 1; i < len(s); i++ {
            rotated := s[i:] + s[:i]
            if rotated < minString {
                minString = rotated
            }
        }
        return minString
    } else {
        sArr := strings.Split(s, "")
        sort.Strings(sArr)
        return strings.Join(sArr, "")
    }
}

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

Задача: 169. Majority Element
Сложность: easy

Дан массив nums размера n, верните элемент большинства.

Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.

Пример:

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

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

1⃣Использование HashMap для подсчета:
Создайте HashMap для отслеживания количества каждого элемента в массиве.

2⃣Подсчет вхождений элементов:
Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.

3⃣Поиск элемента большинства:
Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋.

😎 Решение:

func majorityElement(nums []int) int {
    counts := make(map[int]int)
    for _, num := range nums {
        if _, ok := counts[num]; ok {
            counts[num]++
        } else {
            counts[num] = 1
        }
    }
    for num, count := range counts {
        if count > len(nums)/2 {
            return num
        }
    }
    return 0
}

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

Задача: 1312. Minimum Insertion Steps to Make a String Palindrome
Сложность: hard

Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки.

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

Палиндром — это строка, которая читается одинаково как вперед, так и назад.

Пример:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

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

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s.

2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1.

3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее:

Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0.
Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n].
Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo).
В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)).

😎 Решение

func lcs(s1, s2 string, m, n int, memo [][]int) int {
    if m == 0 || n == 0 {
        return 0
    }
    if memo[m][n] != -1 {
        return memo[m][n]
    }
    if s1[m-1] == s2[n-1] {
        memo[m][n] = 1 + lcs(s1, s2, m-1, n-1, memo)
    } else {
        memo[m][n] = max(lcs(s1, s2, m-1, n, memo), lcs(s1, s2, m, n-1, memo))
    }
    return memo[m][n]
}

func minInsertions(s string) int {
    n := len(s)
    sReverse := reverseString(s)
    memo := make([][]int, n+1)
    for i := range memo {
        memo[i] = make([]int, n+1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    return n - lcs(s, sReverse, n, n, memo)
}

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

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

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

📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 652. Find Duplicate Subtrees
Сложность: medium

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

Пример:

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

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

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

2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.

3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.

😎 Решение:

package main

import (
    "fmt"
    "strconv"
    "strings"
)

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

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    count := make(map[string]int)
    result := []*TreeNode{}
    serialize(root, count, &result)
    return result
}

func serialize(node *TreeNode, count map[string]int, result *[]*TreeNode) string {
    if node == nil {
        return "#"
    }
    serial := strconv.Itoa(node.Val) + "," + serialize(node.Left, count, result) + "," + serialize(node.Right, count, result)
    count[serial]++
    if count[serial] == 2 {
        *result = append(*result, node)
    }
    return serial
}

func main() {
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}}, Right: &TreeNode{Val: 3, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}}, Right: &TreeNode{Val: 4}}}
    result := findDuplicateSubtrees(root)
    for _, node := range result {
        fmt.Println(node.Val)
    }
}

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

Задача: 617. Merge Two Binary Trees
Сложность: medium

Вам даны два бинарных дерева 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
}

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

Зарплата 207.000р у Middle-разработчика в Яндекс

«В день уходит несколько часов на созвоны, в остальное время закрываю задачки из спринта, редко перерабатываю. У компании топовый офис, но с коллективом как-то не заладилось. Радуюсь классному ДМС и стабильной зарплате» - middle разработчик из Яндекса.

Бигтех по-русски - канал с реальными зарплатами и историями IT-специалистов российского БигТеха. Там уже опубликованы рассказы программистов Альфа-банка, Сбера и Тинькофф 🤯

Читайте: @bigtech_russia

Задача: 186. Reverse Words in a String II
Сложность: medium

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

Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом.

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

Пример:

Input: s = ["a"]
Output: ["a"]

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

1⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца.

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

3⃣Окончательная корректировка: проверить, чтобы между словами оставался только один пробел, и удалить лишние пробелы в начале и конце строки, если это необходимо.

😎 Решение:

func reverseWords(s []byte) {
    reverse := func(s []byte) {
        for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
            s[i], s[j] = s[j], s[i]
        }
    }

    reverse(s)
    start, n := 0, len(s)
    for start < n {
        end := start
        for end < n && s[end] != ' ' {
            end++
        }
        reverse(s[start:end])
        start = end + 1
    }
}

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