Задача: 209. Minimum Size Subarray Sum
Сложность: medium

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

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

1⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

func minSubArrayLen(target int, nums []int) int {
    left, sumOfCurrentWindow, res := 0, 0, int(^uint(0) >> 1)

    for right := 0; right < len(nums); right++ {
        sumOfCurrentWindow += nums[right]

        for sumOfCurrentWindow >= target {
            if res > right - left + 1 {
                res = right - left + 1
            }
            sumOfCurrentWindow -= nums[left]
            left++
        }
    }

    if res == int(^uint(0) >> 1) {
        return 0
    }
    return res
}

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

Задача: 135. Candy
Сложность: hard

В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings.

Вы раздаете конфеты этим детям с соблюдением следующих требований:

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

Пример:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

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

1⃣Инициализация и первичное заполнение массивов:
Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете.

2⃣Обход и обновление значений в массивах:
Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа.
Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа.

3⃣Расчет минимального количества конфет:
Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет.
Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил.

😎 Решение:

func candy(ratings []int) int {
    sum := 0
    n := len(ratings)
    left2right := make([]int, n)
    right2left := make([]int, n)
    for i := range left2right {
        left2right[i] = 1
    }
    for i := range right2left {
        right2left[i] = 1
    }
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            left2right[i] = left2right[i-1] + 1
        }
    }
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            right2left[i] = right2left[i+1] + 1
        }
    }
    for i := 0; i < n; i++ {
        sum += max(left2right[i], right2left[i])
    }
    return sum
}

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

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

Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

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

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

func numBusesToDestination(routes [][]int, source int, target int) int {
    if source == target {
        return 0
    }

    adjList := make(map[int][]int)
    for route, stops := range routes {
        for _, stop := range stops {
            adjList[stop] = append(adjList[stop], route)
        }
    }

    q := []int{}
    vis := make(map[int]bool)
    for _, route := range adjList[source] {
        q = append(q, route)
        vis[route] = true
    }

    busCount := 1
    for len(q) > 0 {
        size := len(q)
        for i := 0; i < size; i++ {
            route := q[0]
            q = q[1:]
            for _, stop := range routes[route] {
                if stop == target {
                    return busCount
                }
                for _, nextRoute := range adjList[stop] {
                    if !vis[nextRoute] {
                        vis[nextRoute] = true
                        q = append(q, nextRoute)
                    }
                }
            }
        }
        busCount++
    }
    return -1
}

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

Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

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

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

func numKLenSubstrNoRepeats(s string, k int) int {
    if k > 26 {
        return 0
    }
    
    n := len(s)
    answer := 0
    
    for i := 0; i <= n - k; i++ {
        freq := make([]int, 26)
        isUnique := true
        
        for j := i; j < i + k; j++ {
            freq[s[j] - 'a']++
            
            if freq[s[j] - 'a'] > 1 {
                isUnique = false
                break
            }
        }
        
        if isUnique {
            answer++
        }
    }
    
    return answer
}

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

Задача: 1274. Number of Ships in a Rectangle
Сложность: hard

(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:
Input:
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

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

1⃣Разделите текущий прямоугольник на четыре меньших прямоугольника

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

3⃣Суммируйте количество кораблей в подпрямоугольниках для получения общего количества кораблей в текущем прямоугольнике.

😎 Решение:

func countShips(sea Sea, topRight, bottomLeft Point) int {
    if !sea.HasShips(topRight, bottomLeft) {
        return 0
    }
    if topRight.x == bottomLeft.x && topRight.y == bottomLeft.y {
        return 1
    }
    midX := (topRight.x + bottomLeft.x) / 2
    midY := (topRight.y + bottomLeft.y) / 2
    return countShips(sea, Point{midX, midY}, bottomLeft) +
           countShips(sea, topRight, Point{midX + 1, midY + 1}) +
           countShips(sea, Point{midX, topRight.y}, Point{bottomLeft.x, midY + 1}) +
           countShips(sea, Point{topRight.x, midY}, Point{midX + 1, bottomLeft.y})
}

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

Задача: 247. Strobogrammatic Number II
Сложность: medium

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

Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: n = 2
Output: ["11","69","88","96"]

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

1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.

2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.

3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.

😎 Решение:

package main

func findStrobogrammatic(n int) []string {
  reversiblePairs := [][]string{
    {"0", "0"}, {"1", "1"},
    {"6", "9"}, {"8", "8"}, {"9", "6"},
  }

  var generateStroboNumbers func(int, int) []string
  generateStroboNumbers = func(n int, finalLength int) []string {
    if n == 0 {
      return []string{""}
    }

    if n == 1 {
      return []string{"0", "1", "8"}
    }

    prevStroboNums := generateStroboNumbers(n-2, finalLength)
    var currStroboNums []string

    for _, prevStroboNum := range prevStroboNums {
      for _, pair := range reversiblePairs {
        if pair[0] != "0" || n != finalLength {
          currStroboNums = append(currStroboNums, pair[0]+prevStroboNum+pair[1])
        }
      }
    }

    return currStroboNums
  }

  return generateStroboNumbers(n, n)
}

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

Задача: 767. Reorganize String
Сложность: medium

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

Пример:

Input: s = "aab"
Output: "aba"

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

1⃣Подсчитать количество каждого символа и сохранить пары (count, char) в приоритетной очереди, упорядоченной по убыванию count.

2⃣На каждом шаге извлекаем символ с максимальным count. Если он не равен последнему добавленному в ответ — добавляем в результат.

3⃣Иначе достаём второй по приоритету символ. Добавляем его, уменьшаем count, возвращаем первый символ обратно в кучу.

😎 Решение:

import (
    "container/heap"
)

type Element struct {
    count int
    char  byte
}

type PriorityQueue []*Element

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].count > pq[j].count }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Element)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

func reorganizeString(s string) string {
    charCounts := make([]int, 26)
    for _, c := range s {
        charCounts[c-'a']++
    }

    pq := &PriorityQueue{}
    heap.Init(pq)
    for i := 0; i < 26; i++ {
        if charCounts[i] > 0 {
            heap.Push(pq, &Element{charCounts[i], byte(i + 'a')})
        }
    }

    result := []byte{}
    for pq.Len() > 0 {
        first := heap.Pop(pq).(*Element)
        if len(result) == 0 || first.char != result[len(result)-1] {
            result = append(result, first.char)
            if first.count > 1 {
                first.count--
                heap.Push(pq, first)
            }
        } else {
            if pq.Len() == 0 {
                return ""
            }
            second := heap.Pop(pq).(*Element)
            result = append(result, second.char)
            if second.count > 1 {
                second.count--
                heap.Push(pq, second)
            }
            heap.Push(pq, first)
        }
    }

    return string(result)
}

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

Задача: 424. Longest Repeating Character Replacement
Сложность: medium

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

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

Пример:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo.

😎 Решение:

package main

func characterReplacement(s string, k int) int {
    lo, hi := 1, len(s)+1

    for lo + 1 < hi {
        mid := lo + (hi - lo) / 2
        if canMakeValidSubstring(s, mid, k) {
            lo = mid
        } else {
            hi = mid
        }
    }
    return lo
}

func canMakeValidSubstring(s string, substringLength, k int) bool {
    freqMap := make([]int, 26)
    maxFrequency := 0
    start := 0

    for end := 0; end < len(s); end++ {
        freqMap[s[end] - 'A']++

        if end + 1 - start > substringLength {
            freqMap[s[start] - 'A']--
            start++
        }

        if freqMap[s[end] - 'A'] > maxFrequency {
            maxFrequency = freqMap[s[end] - 'A']
        }
        if substringLength - maxFrequency <= k {
            return true
        }
    }
    return false
}

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

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

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

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

Пример:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

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

1⃣Инициализация и начальный вызов:
Преобразуйте массив wordDict в множество wordSet для эффективного поиска.
Инициализируйте пустой массив results для хранения допустимых предложений.
Инициализируйте пустую строку currentSentence для отслеживания конструируемого предложения.
Вызовите функцию backtrack с исходной строкой s, множеством wordSet, текущим предложением currentSentence, массивом результатов results и начальным индексом, установленным в 0 — начало входной строки.
Верните results после завершения работы backtrack.

2⃣Функция backtrack:
Базовый случай: Если startIndex равен длине строки, добавьте currentSentence в results и вернитесь, так как это означает, что currentSentence представляет собой допустимое предложение.
Итерация по возможным значениям endIndex от startIndex + 1 до конца строки.

3⃣Обработка и рекурсия:
Извлеките подстроку word от startIndex до endIndex - 1.
Если word найдено в wordSet:
Сохраните текущее значение currentSentence в originalSentence.
Добавьте word к currentSentence (с пробелом, если это необходимо).
Рекурсивно вызовите backtrack с обновленным currentSentence и endIndex.
Сбросьте currentSentence к его исходному значению (originalSentence) для отката и попробуйте следующий endIndex.
Вернитесь из функции backtrack.

😎 Решение:

package main

import (
  "strings"
)

func wordBreak(s string, wordDict []string) []string {
  wordSet := make(map[string]struct{})
  for _, word := range wordDict {
    wordSet[word] = struct{}{}
  }
  var results []string
  backtrack(s, wordSet, "", &results, 0)
  return results
}

func backtrack(s string, wordSet map[string]struct{}, currentSentence string, results *[]string, startIndex int) {
  if startIndex == len(s) {
    *results = append(*results, currentSentence)
    return
  }

  for endIndex := startIndex + 1; endIndex <= len(s); endIndex++ {
    word := s[startIndex:endIndex]
    if _, exists := wordSet[word]; exists {
      originalSentence := currentSentence
      if len(currentSentence) > 0 {
        currentSentence += " "
      }
      currentSentence += word
      backtrack(s, wordSet, currentSentence, results, endIndex)
      currentSentence = originalSentence
    }
  }
}

func main() {
  s := "leetcode"
  wordDict := []string{"leet", "code"}
  results := wordBreak(s, wordDict)
  for _, result := range results {
    println(result)
  }
}

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

Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium

Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.

Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.

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

Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.

Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

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

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

2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.

3⃣Повторять процесс, пока все позиции не будут заполнены.

😎 Решение:

func getSmallestString(n int, k int) string {
    result := make([]byte, n)
    for i := 0; i < n; i++ {
        result[i] = 'a'
    }
    
    for position := 0; position < n; position++ {
        positionsLeft := (n - position - 1)
        if k > positionsLeft * 26 {
            add := k - (positionsLeft * 26)
            result[position] = byte('a' + add - 1)
            k -= add
        } else {
            k -= 1
        }
    }
    
    return string(result)
}

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

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

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