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

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