Задача: 771. Jewels and Stones
Сложность: medium

У вас есть строка jewels, содержащая типы драгоценных камней, и строка stones, содержащая ваши камни.
Нужно вернуть количество камней, которые являются драгоценностями.
Регистр важен: "a" и "A" — разные типы.

Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

1⃣Преобразуем строку jewels во множество (map[rune]bool), чтобы быстро проверять, является ли символ драгоценностью.

2⃣Проходим по строке stones и для каждого символа проверяем его наличие в множестве.

3⃣Если символ найден в множестве, увеличиваем счетчик.

😎 Решение:

func numJewelsInStones(jewels string, stones string) int {
    jewelSet := make(map[rune]bool)
    for _, ch := range jewels {
        jewelSet[ch] = true
    }

    count := 0
    for _, ch := range stones {
        if jewelSet[ch] {
            count++
        }
    }

    return count
}

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

Задача: 316. Remove Duplicate Letters
Сложность: medium

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

Пример:

Input: s = "bcabc"
Output: "abc"

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

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

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

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

😎 Решение:

func removeDuplicateLetters(s string) string {
    stack := []rune{}
    seen := make(map[rune]bool)
    lastOccurrence := make(map[rune]int)
    for i, c := range s {
        lastOccurrence[c] = i
    }

    for i, c := range s {
        if !seen[c] {
            for len(stack) > 0 && c < stack[len(stack)-1] && i < lastOccurrence[stack[len(stack)-1]] {
                seen[stack[len(stack)-1]] = false
                stack = stack[:len(stack)-1]
            }
            seen[c] = true
            stack = append(stack, c)
        }
    }
    return string(stack)
}

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

Задача: 820. Short Encoding of Words
Сложность: medium

Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:

words.length == indices.length
Опорная строка s заканчивается символом '#'.
Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].
Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.

Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

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

1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.

2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.

3⃣В конце вернем длину полученной опорной строки.

😎 Решение:

func minimumLengthEncoding(words []string) int {
    good := make(map[string]struct{})
    for _, word := range words {
        good[word] = struct{}{}
    }
    for _, word := range words {
        for k := 1; k < len(word); k++ {
            delete(good, word[k:])
        }
    }
    length := 0
    for word := range good {
        length += len(word) + 1
    }
    return length
}

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

Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.

Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.

Пример:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

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

1⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.

2⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.

3⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.

😎 Решение:

package main

type TrieNode struct {
    links [26]*TrieNode
    isEnd bool
}

func (node *TrieNode) containsKey(ch byte) bool {
    return node.links[ch-'a'] != nil
}

func (node *TrieNode) get(ch byte) *TrieNode {
    return node.links[ch-'a']
}

func (node *TrieNode) put(ch byte, newNode *TrieNode) {
    node.links[ch-'a'] = newNode
}

func (node *TrieNode) setEnd() {
    node.isEnd = true
}

func (node *TrieNode) isEndNode() bool {
    return node.isEnd
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{root: &TrieNode{}}
}

func (this *Trie) Insert(word string) {
    node := this.root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if !node.containsKey(ch) {
            node.put(ch, &TrieNode{})
        }
        node = node.get(ch)
    }
    node.setEnd()
}

func (this *Trie) searchPrefix(word string) *TrieNode {
    node := this.root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if node.containsKey(ch) {
            node = node.get(ch)
        } else {
            return nil
        }
    }
    return node
}

func (this *Trie) Search(word string) bool {
    node := this.searchPrefix(word)
    return node != nil && node.isEndNode()
}

func (this *Trie) StartsWith(prefix string) bool {
    return this.searchPrefix(prefix) != nil
}

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

Задача: 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
}

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

"Ты че, дурак?" – базовая реакция сеньора на тех, кто покупает IT курсы

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

Трушные ребята учатся на жизненных каналах для айтишников. Вот топ-5 от тимлида из Сбера:

⚙️ Технолоджия – для тех, кто хочет быть в курсе новостей в айти

🧠 Ai-чница – способы превратить нейросети в заработок $$$

💻 ИИ тебя заменит! – тенденции айти рынка в связке с нейросетями

4️⃣ Войти в IT – тонны бесплатного обучения для прогеров

😄 IT индус – сборник айти мемов

Задача: 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, "")
    }
}

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