Задача: 1061. Lexicographically Smallest Equivalent String
Сложность: medium

Даны две строки одинаковой длины s1 и s2, а также строка baseStr.

Мы говорим, что символы s1[i] и s2[i] эквивалентны.

Например, если s1 = "abc" и s2 = "cde", то 'a' == 'c', 'b' == 'd' и 'c' == 'e'. Эквивалентные символы следуют правилам рефлексивности, симметрии и транзитивности.

Верните лексикографически наименьшую эквивалентную строку baseStr, используя информацию об эквивалентности из s1 и s2.

Пример:

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

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

1⃣Создайте матрицу смежности adjMatrix размером 26x26 для хранения рёбер и массив visited для отслеживания посещённых символов.

2⃣Итеративно обрабатывайте каждый символ от 0 до 25:

Если символ ещё не посещён, выполните DFS, начиная с этого символа, и сохраните все пройденные символы в векторе component, а минимальный из этих символов в переменной minChar.
Обновите все символы из component до minChar в векторе mappingChar, который хранит окончательное сопоставление символов baseStr.

3⃣Пройдите по baseStr и создайте итоговую строку ans, используя символы из mappingChar.

😎 Решение:

package main

func DFS(src int, adjMatrix *[26][26]int, visited *[26]int, component *[]int, minChar *int) {
    visited[src] = 1
    *component = append(*component, src)
    if src < *minChar {
        *minChar = src
    }
    for i := 0; i < 26; i++ {
        if adjMatrix[src][i] != 0 && visited[i] == 0 {
            DFS(i, adjMatrix, visited, component, minChar)
        }
    }
}

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
    var adjMatrix [26][26]int
    for i := 0; i < len(s1); i++ {
        adjMatrix[s1[i]-'a'][s2[i]-'a'] = 1
        adjMatrix[s2[i]-'a'][s1[i]-'a'] = 1
    }
    mappingChar := [26]int{}
    for i := 0; i < 26; i++ {
        mappingChar[i] = i
    }
    visited := [26]int{}
    for c := 0; c < 26; c++ {
        if visited[c] == 0 {
            component := []int{}
            minChar := 27
            DFS(c, &adjMatrix, &visited, &component, &minChar)
            for _, vertex := range component {
                mappingChar[vertex] = minChar
            }
        }
    }
    ans := make([]byte, len(baseStr))
    for i := range baseStr {
        ans[i] = byte(mappingChar[baseStr[i]-'a'] + 'a')
    }
    return string(ans)
}

func main() {
    // Example usage
    s1 := "leetcode"
    s2 := "programs"
    baseStr := "sourcecode"
    result := smallestEquivalentString(s1, s2, baseStr)
    println(result)
}

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

Задача: 912. Sort an Array
Сложность: medium

Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью.

Пример:

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

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

1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

2⃣Разделить массив на две половины.
Рекурсивно отсортировать каждую половину.

3⃣Слить две отсортированные половины.

😎 Решение:

package main

import (
    "fmt"
)

func mergeSort(nums []int) {
    if len(nums) > 1 {
        mid := len(nums) / 2
        left_half := make([]int, mid)
        right_half := make([]int, len(nums)-mid)

        copy(left_half, nums[:mid])
        copy(right_half, nums[mid:])

        mergeSort(left_half)
        mergeSort(right_half)

        i, j, k := 0, 0, 0
        for i < len(left_half) && j < len(right_half) {
            if left_half[i] < right_half[j] {
                nums[k] = left_half[i]
                i++
            } else {
                nums[k] = right_half[j]
                j++
            }
            k++
        }

        for i < len(left_half) {
            nums[k] = left_half[i]
            i++
            k++
        }

        for j < len(right_half) {
            nums[k] = right_half[j]
            j++
            k++
        }
    }
}

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

Задача: 811. Subdomain Visit Count
Сложность: medium

Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com".

Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен.

Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз.
Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке.

Пример:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

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

1⃣Следуем указаниям из условия задачи.

2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y.

3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split.

😎 Решение:

package main

import (
    "strconv"
    "strings"
)

func subdomainVisits(cpdomains []string) []string {
    ans := make(map[string]int)
    for _, domain := range cpdomains {
        parts := strings.Split(domain, " ")
        count, _ := strconv.Atoi(parts[0])
        frags := strings.Split(parts[1], ".")
        for i := range frags {
            subdomain := strings.Join(frags[i:], ".")
            ans[subdomain] += count
        }
    }
    res := make([]string, 0, len(ans))
    for dom, ct := range ans {
        res = append(res, strconv.Itoa(ct)+" "+dom)
    }
    return res
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 1427. Perform String Shifts
Сложность: easy

Вам дана строка s, содержащая строчные английские буквы, и матрица shift, где shift[i] = [directioni, amounti]:
directioni может быть 0 (для сдвига влево) или 1 (для сдвига вправо).
amounti - это количество, на которое строка s должна быть сдвинута.
Сдвиг влево на 1 означает удаление первого символа строки s и добавление его в конец.
Аналогично, сдвиг вправо на 1 означает удаление последнего символа строки s и добавление его в начало.
Верните итоговую строку после всех операций.

Пример:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

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

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

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

3⃣Выполните сдвиг строки на основе вычисленного значения и верните итоговую строку.

😎 Решение:

func stringShift(s string, shift [][]int) string {
    leftShifts, rightShifts := 0, 0
    for _, move := range shift {
        if move[0] == 0 {
            leftShifts += move[1]
        } else {
            rightShifts += move[1]
        }
    }
    
    netShifts := (rightShifts - leftShifts) % len(s)
    if netShifts < 0 {
        netShifts += len(s)
    }
    
    if netShifts == 0 {
        return s
    }
    
    return s[len(s)-netShifts:] + s[:len(s)-netShifts]
}

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

Задача: 96. Unique Binary Search Trees
Сложность: medium

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

Пример:

Input: n = 3  
Output: 5  

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

1⃣Определим G(n):
- G(n) — количество уникальных BST с n узлами.
- Базовые случаи: G(0) = 1, G(1) = 1.

2⃣Рекурсия через выбор корня:
- Пусть i — корень дерева. Тогда:
- Левое поддерево: G(i-1) узлов.
- Правое поддерево: G(n-i) узлов.
- Всего деревьев при корне i: G(i-1) * G(n-i).

3⃣Результат:
- G(n) = ∑ G(i-1) * G(n-i) для всех i от 1 до n.
- Используем динамическое программирование для подсчета.

😎 Решение:

func numTrees(n int) int {
    G := make([]int, n+1)
    G[0] = 1
    G[1] = 1

    for i := 2; i <= n; i++ {
        for j := 1; j <= i; j++ {
            G[i] += G[j-1] * G[i-j]
        }
    }

    return G[n]
}

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

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

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