Задача: 102. Binary Tree Level Order Traversal
Сложность: medium

Дан корень бинарного дерева. Верните обход узлов дерева по уровням (то есть слева направо, уровень за уровнем).

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

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

1⃣Самый простой способ решения задачи — использование рекурсии. Сначала убедимся, что дерево не пустое, а затем рекурсивно вызовем функцию helper(node, level), которая принимает текущий узел и его уровень в качестве аргументов.

2⃣Эта функция выполняет следующее:
Выходной список здесь называется levels, и, таким образом, текущий уровень — это просто длина этого списка len(levels). Сравниваем номер текущего уровня len(levels) с уровнем узла level. Если вы все еще на предыдущем уровне, добавьте новый, добавив новый список в levels.

3⃣Добавьте значение узла в последний список в levels.
Рекурсивно обработайте дочерние узлы, если они не равны None: helper(node.left / node.right, level + 1).

😎 Решение:

func levelOrder(root *TreeNode) [][]int {
    levels := [][]int{}
    var helper func(*TreeNode, int)
    helper = func(node *TreeNode, level int) {
        if len(levels) == level {
            levels = append(levels, []int{})
        }
        levels[level] = append(levels[level], node.Val)
        if node.Left != nil {
            helper(node.Left, level+1)
        }
        if node.Right != nil {
            helper(node.Right, level+1)
        }
    }
    if root != nil {
        helper(root, 0)
    }
    return levels
}

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

Задача: 520. Detect Capital
Сложность: easy

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

import (
    "regexp"
)

func detectCapitalUse(word string) bool {
    pattern := "^[A-Z]*$|^[a-z]*$|^[A-Z][a-z]*$"
    match, _ := regexp.MatchString(pattern, word)
    return match
}

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

Задача: 1197. Minimum Knight Moves
Сложность: medium

На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0].
У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении.

Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует.

Пример:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

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

1⃣Инициализация структур данных:
Инициализируйте две очереди для хранения координат и расстояний: одну для движения от начальной точки, другую — от конечной точки.
Инициализируйте две карты для хранения посещенных координат и расстояний: одну для движения от начальной точки, другую — от конечной точки.

2⃣Реализация двунаправленного поиска в ширину (BFS):
Выполняйте шаги из очередей, расширяя круги поиска как от начальной, так и от конечной точки.
Если круги пересекаются, возвращайте сумму расстояний до точки пересечения.

3⃣Расширение кругов поиска:
Для каждой текущей точки из очередей расширяйте круг поиска по всем возможным ходам коня.
Обновляйте расстояния и добавляйте новые точки в очереди, если они еще не были посещены.
Увеличивайте units на значение, извлеченное из кучи.

😎 Решение:

package main

import (
    "container/list"
    "fmt"
)

func minKnightMoves(x int, y int) int {
    offsets := [][]int{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}
    
    originQueue := list.New()
    originQueue.PushBack([]int{0, 0, 0})
    originDistance := map[string]int{"0,0": 0}
    
    targetQueue := list.New()
    targetQueue.PushBack([]int{x, y, 0})
    targetDistance := map[string]int{fmt.Sprintf("%d,%d", x, y): 0}
    
    for {
        origin := originQueue.Remove(originQueue.Front()).([]int)
        originKey := fmt.Sprintf("%d,%d", origin[0], origin[1])
        if targetDistance[originKey] != 0 || originKey == fmt.Sprintf("%d,%d", x, y) {
            return origin[2] + targetDistance[originKey]
        }
        
        target := targetQueue.Remove(targetQueue.Front()).([]int)
        targetKey := fmt.Sprintf("%d,%d", target[0], target[1])
        if originDistance[targetKey] != 0 || targetKey == "0,0" {
            return target[2] + originDistance[targetKey]
        }
        
        for _, offset := range offsets {
            nextOrigin := []int{origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1}
            nextOriginKey := fmt.Sprintf("%d,%d", nextOrigin[0], nextOrigin[1])
            if _, ok := originDistance[nextOriginKey]; !ok {
                originQueue.PushBack(nextOrigin)
                originDistance[nextOriginKey] = nextOrigin[2]
            }
            
            nextTarget := []int{target[0] + offset[0], target[1] + offset[1], target[2] + 1}
            nextTargetKey := fmt.Sprintf("%d,%d", nextTarget[0], nextTarget[1])
            if _, ok := targetDistance[nextTargetKey]; !ok {
                targetQueue.PushBack(nextTarget)
                targetDistance[nextTargetKey] = nextTarget[2]
            }
        }
    }
}

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

func shiftAndCount(xShift, yShift int, M, R [][]int) int {
    leftShiftCount, rightShiftCount := 0, 0
    rRow := 0
    for mRow := yShift; mRow < len(M); mRow++ {
        rCol := 0
        for mCol := xShift; mCol < len(M); mCol++ {
            if M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol] {
                leftShiftCount++
            }
            if M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol] {
                rightShiftCount++
            }
            rCol++
        }
        rRow++
    }
    return max(leftShiftCount, rightShiftCount)
}

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

func largestOverlap(A [][]int, B [][]int) int {
    maxOverlaps := 0
    for yShift := 0; yShift < len(A); yShift++ {
        for xShift := 0; xShift < len(A); xShift++ {
            maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B))
            maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A))
        }
    }
    return maxOverlaps
}

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

Задача: 141. Linked List Cycle
Сложность: easy

Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.

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

Верните true, если в связном списке есть цикл. В противном случае верните false.

Пример:

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

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

1⃣Инициализация структуры данных:
Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы.

2⃣Обход списка:
Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди.

3⃣Проверка на цикл:
Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false.
Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true.
Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка.

😎 Решение:

func hasCycle(head *ListNode) bool {
    nodesSeen := make(map[*ListNode]bool)
    current := head
    for current != nil {
        if nodesSeen[current] {
            return true
        }
        nodesSeen[current] = true
        current = current.Next
    }
    return false
}

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

Задача: 470. Implement Rand10() Using Rand7()
Сложность: medium

Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7].
Нужно реализовать функцию rand10(), которая генерирует случайное число в диапазоне [1, 10].
Вы можете использовать только rand7(), другие источники случайности использовать нельзя.

Пример:

Input: n = 1 
Output: [2]

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

1⃣rand7() генерирует 7 возможных значений. Скомбинируем два вызова rand7() как 7×7 = 49 вариантов, что достаточно для генерации чисел от 1 до 10.

2⃣Представим это как таблицу 7×7: row = rand7(), col = rand7(). Индекс = (row-1)*7 + col даёт значение от 1 до 49.

3⃣Используем только первые 40 значений (1..40) — они равномерно делятся на 10.
Если idx > 40, делаем повторный вызов, чтобы не портить равномерность.

😎 Решение:

func rand10() int {
    var row, col, idx int
    for {
        row = rand7()
        col = rand7()
        idx = col + (row-1) * 7
        if idx <= 40 {
            break
        }
    }
    return 1 + (idx-1) % 10
}

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

Задача: 211. Design Add and Search Words Data Structure
Сложность: medium

Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову.

Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

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

2⃣Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3⃣Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

package main

type TrieNode struct {
    children map[rune]*TrieNode
    isWord   bool
}

type WordDictionary struct {
    root *TrieNode
}

func Constructor() WordDictionary {
    return WordDictionary{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

func (this *WordDictionary) AddWord(word string) {
    node := this.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isWord = true
}

func (this *WordDictionary) searchInNode(word string, node *TrieNode) bool {
    for i, ch := range word {
        if nextNode, ok := node.children[ch]; ok {
            node = nextNode
        } else {
            if ch == '.' {
                for _, child := range node.children {
                    if this.searchInNode(word[i+1:], child) {
                        return true
                    }
                }
            }
            return false
        }
    }
    return node.isWord
}

func (this *WordDictionary) Search(word string) bool {
    return this.searchInNode(word, this.root)
}

func main() {
    wordDictionary := Constructor()
    wordDictionary.AddWord("bad")
    wordDictionary.AddWord("dad")
    wordDictionary.AddWord("mad")
    println(wordDictionary.Search("pad")) // Output: false
    println(wordDictionary.Search("bad")) // Output: true
    println(wordDictionary.Search(".ad")) // Output: true
    println(wordDictionary.Search("b..")) // Output: true
}

х

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

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

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