Golang | LeetCode

🔍Тестовое собеседование с Go Senior из Uzum в этот четверг 11 июня(в четверг!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Go-разработчика. Как это будет: 📂 Маруф Караев, Senior из Uzum, ex-Яндекс, ex-EPAM будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Маруф будет комментировать каждый ответ респондента, чтобы дать понять, чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Маруфу Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Go-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_go_bot Реклама. О рекламодателе.

Задача: 1219. Path with Maximum Gold Сложность: medium В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста. Верните максимальное количество золота, которое вы можете собрать при следующих условиях: - Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки. - Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз. - Вы не можете посещать одну и ту же ячейку более одного раза. - Никогда не посещайте ячейку с 0 золотом. - Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото. Пример:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте константный массив DIRECTIONS для направления перемещений. Определите количество строк и столбцов в сетке. Инициализируйте переменную maxGold для хранения максимального количества собранного золота. 2⃣Функция DFS и обратный трек: Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека. Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота. Пометьте текущую ячейку как посещённую и сохраните её значение. Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь. Сбросьте текущую ячейку до её исходного значения для дальнейших исследований. 3⃣Поиск максимального золота: Используйте вложенные циклы для каждой ячейки в сетке, чтобы найти максимальное количество золота, начиная с этой ячейки, с помощью функции dfsBacktrack. Обновите maxGold при нахождении лучшего пути. Верните maxGold. 😎 Решение:

type Solution struct{}

func (s *Solution) getMaximumGold(grid [][]int) int {
    directions := []int{0, 1, 0, -1, 0}
    rows, cols := len(grid), len(grid[0])
    maxGold := 0

    var dfsBacktrack func(grid [][]int, rows, cols, row, col int) int
    dfsBacktrack = func(grid [][]int, rows, cols, row, col int) int {
        if row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0 {
            return 0
        }
        originalVal := grid[row][col]
        grid[row][col] = 0
        maxGold := 0

        for i := 0; i < 4; i++ {
            maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row+directions[i], col+directions[i+1]))
        }

        grid[row][col] = originalVal
        return maxGold + originalVal
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row, col))
        }
    }

    return maxGold
}

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

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

Задача: 398. Random Pick Index Сложность: medium Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата. Пример:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

👨‍💻 Алгоритм: 1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования. 2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным. 3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса. 😎 Решение:

import (
    "math/rand"
    "time"
)

type Solution struct {
    nums []int
}

func Constructor(nums []int) Solution {
    rand.Seed(time.Now().UnixNano())
    return Solution{nums: nums}
}

func (this *Solution) Pick(target int) int {
    count := 0
    result := -1
    for i, num := range this.nums {
        if num == target {
            count++
            if rand.Intn(count) == count-1 {
                result = i
            }
        }
    }
    return result
}

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

Задача: №24. Swap Nodes in Pairs Сложность: medium Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы). Пример:

Input: head = [1,2,3,4]  
Output: [2,1,4,3]  

👨‍💻 Алгоритм: 1⃣Создать фиктивный (dummy) узел перед head для удобства обработки начала списка. 2⃣Использовать указатели prev, first и second для перестановки пары узлов. 3⃣Переставлять узлы, обновляя связи между ними, и двигаться дальше по списку. 😎 Решение:

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy

    for head != nil && head.Next != nil {
        first, second := head, head.Next

        prev.Next = second
        first.Next = second.Next
        second.Next = first

        prev = first
        head = first.Next
    }

    return dummy.Next
}

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

Задача: 652. Find Duplicate Subtrees Сложность: medium Если задан корень бинарного дерева, верните все дублирующие поддеревья. Для каждого вида дублирующих поддеревьев достаточно вернуть корневой узел любого из них. Два дерева являются дублирующими, если они имеют одинаковую структуру с одинаковыми значениями узлов. Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

👨‍💻 Алгоритм: 1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева. 2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления. 3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев. 😎 Решение:

package main

import (
    "fmt"
    "strconv"
    "strings"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    count := make(map[string]int)
    result := []*TreeNode{}
    serialize(root, count, &result)
    return result
}

func serialize(node *TreeNode, count map[string]int, result *[]*TreeNode) string {
    if node == nil {
        return "#"
    }
    serial := strconv.Itoa(node.Val) + "," + serialize(node.Left, count, result) + "," + serialize(node.Right, count, result)
    count[serial]++
    if count[serial] == 2 {
        *result = append(*result, node)
    }
    return serial
}

func main() {
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}}, Right: &TreeNode{Val: 3, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}}, Right: &TreeNode{Val: 4}}}
    result := findDuplicateSubtrees(root)
    for _, node := range result {
        fmt.Println(node.Val)
    }
}

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

Задача: 641. Design Circular Deque Сложность: medium Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае. Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

👨‍💻 Алгоритм: 1⃣Инициализация и проверка состояний Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:

package main

type MyCircularDeque struct {
    deque    []int
    front    int
    rear     int
    size     int
    capacity int
}

func Constructor(k int) MyCircularDeque {
    return MyCircularDeque{
        deque:    make([]int, k),
        front:    0,
        rear:     0,
        size:     0,
        capacity: k,
    }
}

func (this *MyCircularDeque) InsertFront(value int) bool {
    if this.IsFull() {
        return false
    }
    this.front = (this.front - 1 + this.capacity) % this.capacity
    this.deque[this.front] = value
    this.size++
    return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
    if this.IsFull() {
        return false
    }
    this.deque[this.rear] = value
    this.rear = (this.rear + 1) % this.capacity
    this.size++
    return true
}

func (this *MyCircularDeque) DeleteFront() bool {
    if this.IsEmpty() {
        return false
    }
    this.front = (this.front + 1) % this.capacity
    this.size--
    return true
}

func (this *MyCircularDeque) DeleteLast() bool {
    if this.IsEmpty() {
        return false
    }
    this.rear = (this.rear - 1 + this.capacity) % this.capacity
    this.size--
    return true
}

func (this *MyCircularDeque) GetFront() int {
    if this.IsEmpty() {
        return -1
    }
    return this.deque[this.front]
}

func (this *MyCircularDeque) GetRear() int {
    if this.IsEmpty() {
        return -1
    }
    return this.deque[(this.rear-1+this.capacity)%this.capacity]
}

func (this *MyCircularDeque) IsEmpty() bool {
    return this.size == 0
}

func (this *MyCircularDeque) IsFull() bool {
    return this.size == this.capacity
}

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

Задача: 318. Maximum Product of Word Lengths Сложность: medium Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0. Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:

func maxProduct(words []string) int {
    n := len(words)
    masks := make([]int, n)
    lens := make([]int, n)
    
    for i := 0; i < n; i++ {
        bitmask := 0
        for _, ch := range words[i] {
            bitmask |= 1 << (ch - 'a')
        }
        masks[i] = bitmask
        lens[i] = len(words[i])
    }
    
    maxVal := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if masks[i] & masks[j] == 0 {
                maxVal = max(maxVal, lens[i] * lens[j])
            }
        }
    }
    return maxVal
}

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

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

Задача: 132. Palindrome Partitioning II Сложность: hard Дана строка s. Разделите строку так, чтобы каждая подстрока была палиндромом. Верните минимальное количество разрезов, необходимых для такого разделения. Пример:

Input: s = "aab"  
Output: 1  
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.  

👨‍💻 Алгоритм: 1⃣Используем динамическое программирование. dp[i] — минимальное количество разрезов для подстроки s[0:i]. 2⃣Создаем вспомогательную таблицу isPalindrome[i][j], которая хранит true, если s[i:j] — палиндром. 3⃣Заполняем dp[i], проверяя все возможные разрезы и выбирая минимум. 😎 Решение:

func minCut(s string) int {
    n := len(s)
    dp := make([]int, n)
    isPalindrome := make([][]bool, n)
    
    for i := range isPalindrome {
        isPalindrome[i] = make([]bool, n)
    }
    
    for end := 0; end < n; end++ {
        minCuts := end
        for start := 0; start <= end; start++ {
            if s[start] == s[end] && (end-start <= 1 || isPalindrome[start+1][end-1]) {
                isPalindrome[start][end] = true
                if start == 0 {
                    minCuts = 0
                } else {
                    minCuts = min(minCuts, dp[start-1]+1)
                }
            }
        }
        dp[end] = minCuts
    }
    
    return dp[n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

⚙️ Лучшие практики в Go: разбираем на Podlodka Go Crew Пишете на Go и хотите узнать, как закладывать надёжную основу для своих проектов? С 1 по 5 июня Podlodka Go Crew вместе с 2ГИС проведут сезон «Лучшие практики в Go». Организаторы собрали сильную программу с акцентом на живой опыт и прикладные кейсы. Вот несколько сессий, на которые советуем обратить внимание: 🚀 «Практика Go оптимизаций: растем вместе с нагрузкой», Алексей Акулович — про то, как сервис растёт до миллионов RPS, оптимизацию CPU, grpc и protobuf, а также про собственный GC поверх гошного. 🏗 «Эволюция структуры Go-проекта: как 30 человек пушат в один репозиторий», Кирилл Возжеников — как развивается продуктовый монорепозиторий и строятся хорошие архитектурные практики. 🧩 «Как и зачем писать свой CDC на Go», Юра Саргсян — когда приходится выходить за стандартные решения: Postgres, Kafka, гарантии доставки и подводные камни логической репликации. В конце сезона участников ждёт «Битва кейсов: 50 оттенков межсервисного взаимодействия» — разбор архитектурных задач с метриками, схемами и поиском решений в реальном времени. 🎟 И это ещё не всё — смотрите полную программу на сайте и забирайте билет!

🔍Тестовое собеседование с Go ТехЛидом из Wildberries & Russ в этот четверг 21 мая(в четверг!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Go-разработчика. Как это будет: 📂 Рамиль Мясоутов, ТехЛид из WildBerries, ex-Купер будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Рамиль будет комментировать каждый ответ респондента, чтобы дать понять, чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Рамилю Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Go-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_go_bot Реклама. О рекламодателе.

Главный навык на ближайшие годы — ВАЙБ-КОДИНГ ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную. Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы. Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg

Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix Сложность: hard Дана бинарная матрица mat размером m x n. За один шаг вы можете выбрать одну ячейку и перевернуть её и всех её четырех соседей, если они существуют (Перевернуть означает изменить 1 на 0 и 0 на 1). Пара ячеек называется соседями, если они имеют общую границу. Верните минимальное количество шагов, необходимых для преобразования матрицы mat в нулевую матрицу или -1, если это невозможно. Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1. Нулевая матрица - это матрица, в которой все ячейки равны 0. Пример:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

👨‍💻 Алгоритм: 1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой. 2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed: Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1. Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке. 3⃣После обработки всех строк проверьте, содержит ли lastState все нули, чтобы определить, является ли это допустимым решением. Верните минимальное количество переворотов для всех допустимых решений. 😎 Решение:

func minFlips(mat [][]int) int {
    return dfs(mat, []int{})
}

func better(x, y int) int {
    if x < 0 || (y >= 0 && y < x) {
        return y
    }
    return x
}

func dfs(mat [][]int, operations []int) int {
    if len(operations) == len(mat[0]) {
        changed := make([]int, len(mat[0]))
        lastState := make([]int, len(operations))
        copy(lastState, operations)
        maybe := 0
        for _, row := range mat {
            state := make([]int, len(changed))
            copy(state, changed)
            for j := range row {
                state[j] ^= row[j]
                if lastState[j] == 1 {
                    state[j] ^= 1
                    if j > 0 {
                        state[j-1] ^= 1
                    }
                    if j+1 < len(row) {
                        state[j+1] ^= 1
                    }
                    maybe++
                }
            }
            changed = lastState
            lastState = state
        }
        for _, x := range lastState {
            if x != 0 {
                return -1
            }
        }
        return maybe
    }
    maybe1 := dfs(mat, append(operations, 0))
    operations = append(operations, 1)
    maybe2 := dfs(mat, operations)
    operations = operations[:len(operations)-1]
    return better(maybe1, maybe2)
}

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

Задача: 1361. Validate Binary Tree Nodes Сложность: easy У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево. Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка. Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче. Пример:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

👨‍💻 Алгоритм: 1⃣Проверка количества родителей для каждого узла: Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false. 2⃣Поиск корневого узла и проверка на единственное дерево: Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов. 3⃣Проверка на достижение всех узлов: Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true. 😎 Решение:

package main

import (
  "fmt"
)

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
  parents := make([]int, n)

  for i := 0; i < n; i++ {
    if leftChild[i] != -1 {
      parents[leftChild[i]]++
      if parents[leftChild[i]] > 1 {
        return false
      }
    }
    if rightChild[i] != -1 {
      parents[rightChild[i]]++
      if parents[rightChild[i]] > 1 {
        return false
      }
    }
  }

  root := -1
  for i := 0; i < n; i++ {
    if parents[i] == 0 {
      if root == -1 {
        root = i
      } else {
        return false
      }
    }
  }

  if root == -1 {
    return false
  }

  visited := make(map[int]struct{})
  queue := []int{root}

  for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    if _, found := visited[node]; found {
      return false
    }
    visited[node] = struct{}{}
    if leftChild[node] != -1 {
      queue = append(queue, leftChild[node])
    }
    if rightChild[node] != -1 {
      queue = append(queue, rightChild[node])
    }
  }

  return len(visited) == n
}

func main() {
  leftChild := []int{1, -1, 3, -1}
  rightChild := []int{2, -1, -1, -1}
  fmt.Println(validateBinaryTreeNodes(4, leftChild, rightChild)) // Output: true
}

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

Задача: 439. Ternary Expression Parser Сложность: medium Дана строка expression, представляющая произвольно вложенные тернарные выражения, вычислите это выражение и верните его результат. Можно всегда считать, что данное выражение является корректным и содержит только цифры, '?', ':', 'T' и 'F', где 'T' означает истину, а 'F' - ложь. Все числа в выражении являются однозначными числами (т.е. в диапазоне от 0 до 9). Условные выражения группируются справа налево (как обычно в большинстве языков), и результат выражения всегда будет либо цифрой, либо 'T', либо 'F'. Пример:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

👨‍💻 Алгоритм: 1⃣Определите вспомогательную функцию isValidAtomic(s), которая принимает строку s и возвращает True, если s является допустимым атомарным выражением. В противном случае функция возвращает False. Функция будет вызываться только с пятисимвольными строками. Если все следующие условия выполнены, функция возвращает True, иначе - False: s[0] является T или F. s[1] является ?. s[2] является T, F или цифрой от 0 до 9. s[3] является :. s[4] является T, F или цифрой от 0 до 9. 2⃣Определите вспомогательную функцию solveAtomic(s), которая принимает строку s и возвращает значение атомарного выражения. Значение атомарного выражения равно E1, если B - это T, иначе значение равно E2. Функция будет вызываться только с пятисимвольными строками и возвращать один символ:. 3⃣Если s[0] является T, функция возвращает s[2], иначе возвращает s[4]. В функции parseTernary(expression) уменьшайте выражение до тех пор, пока не останется односимвольная строка. Инициализируйте j как expression.size() - 1 (это будет самый правый индекс окна). Пока самое правое окно длиной 5 не является допустимым атомарным выражением, уменьшайте j на 1. Когда будет найдено самое правое допустимое атомарное выражение, решите его и уменьшите до одного символа. Замените самое правое допустимое атомарное выражение одним символом, после чего длина выражения уменьшится на 4. В итоге останется односимвольная строка, которую и верните. 😎 Решение:

func parseTernary(expression string) string {
    isValidAtomic := func(s string) bool {
        return (s[0] == 'T' || s[0] == 'F') &&
               s[1] == '?' &&
               (strings.Contains("TF0123456789", string(s[2]))) &&
               s[3] == ':' &&
               (strings.Contains("TF0123456789", string(s[4])))
    }

    solveAtomic := func(s string) byte {
        if s[0] == 'T' {
            return s[2]
        }
        return s[4]
    }

    for len(expression) != 1 {
        j := len(expression) - 1
        for !isValidAtomic(expression[j-4:j+1]) {
            j -= 1
        }
        expression = expression[:j-4] + string(solveAtomic(expression[j-4:j+1])) + expression[j+1:]
    }

    return expression
}

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

Задача: 527. Word Abbreviation Сложность: hard Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова. Правила сокращения строки следующие: Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ. Если более одного слова имеют одинаковое сокращение, выполните следующее: Увеличьте префикс (символы в первой части) каждого из их сокращений на 1. Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"]. Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным. В конце, если сокращение не сделало слово короче, оставьте его в исходном виде. Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

👨‍💻 Алгоритм: 1⃣ Инициализация и создание начальных сокращений: Создайте массив для хранения сокращений и массив для отслеживания длины префикса каждого слова. Для каждого слова создайте начальное сокращение с использованием первого символа, количества символов между первым и последним символом и последнего символа. 2⃣ Обработка коллизий: Для каждого слова проверьте, не совпадает ли его сокращение с уже существующими сокращениями. Если сокращение не уникально, увеличьте длину префикса и повторите проверку. 3⃣ Возврат результата: Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны. 😎 Решение:

func wordsAbbreviation(words []string) []string {
    n := len(words)
    ans := make([]string, n)
    prefix := make([]int, n)

    for i := 0; i < n; i++ {
        ans[i] = abbrev(words[i], 0)
    }

    for i := 0; i < n; i++ {
        for {
            dupes := make(map[int]bool)
            for j := i + 1; j < n; j++ {
                if ans[i] == ans[j] {
                    dupes[j] = true
                }
            }

            if len(dupes) == 0 {
                break
            }

            dupes[i] = true
            for k := range dupes {
                prefix[k]++
                ans[k] = abbrev(words[k], prefix[k])
            }
        }
    }

    return ans
}

func abbrev(word string, i int) string {
    n := len(word)
    if n-i <= 3 {
        return word
    }
    return word[:i+1] + fmt.Sprint(n-i-2) + word[n-1:]
}

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

Задача: 1356. Sort Integers by The Number of 1 Bits Сложность: easy Дан целочисленный массив arr. Отсортируйте целые числа в массиве по возрастанию числа единиц в их двоичном представлении, а в случае, если у двух или более чисел одинаковое количество единиц, отсортируйте их по возрастанию. Верните массив после сортировки. Пример:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

👨‍💻 Алгоритм: 1⃣Создание функции для подсчета единиц: Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении. 2⃣Сортировка массива: Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки. 3⃣Возврат отсортированного массива: Верните отсортированный массив. 😎 Решение:

import (
    "sort"
    "strconv"
)

func sortByBits(arr []int) []int {
    sort.Slice(arr, func(i, j int) bool {
        countI := strconv.FormatInt(int64(arr[i]), 2)
        countJ := strconv.FormatInt(int64(arr[j]), 2)
        countOneI := 0
        countOneJ := 0
        
        for _, char := range countI {
            if char == '1' {
                countOneI++
            }
        }
        for _, char := range countJ {
            if char == '1' {
                countOneJ++
            }
        }
        if countOneI == countOneJ {
            return arr[i] < arr[j]
        }
        return countOneI < countOneJ
    })
    return arr
}

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

Задача: 104. Maximum Depth of Binary Tree Сложность: easy Дан корень бинарного дерева, верните его максимальную глубину. Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла. Пример:

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

👨‍💻 Алгоритм: 1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS). 2⃣Для данной задачи подойдет несколько способов. 3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии. 😎 Решение:

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left_height := maxDepth(root.Left)
    right_height := maxDepth(root.Right)
    return 1 + max(left_height, right_height)
}

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

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

Задача: 916. Word Subsets Сложность: medium Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке. Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

👨‍💻 Алгоритм: 1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2. 2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2. 3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию. 😎 Решение:

package main

func wordSubsets(words1 []string, words2 []string) []string {
    maxCount := make([]int, 26)
    for _, word := range words2 {
        count := getCount(word)
        for i := 0; i < 26; i++ {
            if count[i] > maxCount[i] {
                maxCount[i] = count[i]
            }
        }
    }

    result := []string{}
    for _, word := range words1 {
        count := getCount(word)
        if isUniversal(count, maxCount) {
            result = append(result, word)
        }
    }

    return result
}

func getCount(word string) []int {
    count := make([]int, 26)
    for _, char := range word {
        count[char-'a']++
    }
    return count
}

func isUniversal(count []int, maxCount []int) bool {
    for i := 0; i < 26; i++ {
        if count[i] < maxCount[i] {
            return false
        }
    }
    return true
}

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

Задача: 1332. Remove Palindromic Subsequences Сложность: easy Вам дана строка s, состоящая только из букв 'a' и 'b'. За один шаг вы можете удалить одну палиндромную подпоследовательность из s. Верните минимальное количество шагов, чтобы сделать данную строку пустой. Строка является подпоследовательностью данной строки, если она создается путем удаления некоторых символов из данной строки без изменения их порядка. Обратите внимание, что подпоследовательность не обязательно должна быть непрерывной. Строка называется палиндромом, если она читается одинаково как вперед, так и назад. Пример:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

👨‍💻 Алгоритм: 1⃣Если строка s уже является палиндромом, верните 1, так как можно удалить всю строку за один шаг. 2⃣Если строка s не является палиндромом, верните 2. В этом случае можно удалить все символы 'a' за один шаг, а затем все символы 'b' за второй шаг (или наоборот). 3⃣Таким образом, минимум шагов для опустошения строки всегда будет либо 1, либо 2, в зависимости от того, является ли строка палиндромом. 😎 Решение

func removePalindromeSub(s string) int {
    if len(s) == 0 {
        return 0
    }
    reversedString := reverseString(s)
    if reversedString == s {
        return 1
    }
    return 2
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

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

Задача: 600. Non-negative Integers without Consecutive Ones Сложность: hard Дано число n. Нужно найти количество целых чисел от 0 до n, чьи двоичные представления не содержат двух единиц подряд (т.е. не содержат "11"). Пример:

Input: n = 5  
Output: 5

Пояснение: - 0 => 0 - 1 => 1 - 2 => 10 - 3 => 11 ❌ - 4 => 100 - 5 => 101 → Все кроме 3 удовлетворяют условию, ответ = 5. 👨‍💻 Алгоритм: 1⃣Перебор всех чисел от 0 до n Для каждого числа i от 0 до n вызываем проверку: содержит ли i две единицы подряд в двоичном представлении. 2⃣Проверка двух последовательных единиц Используем битовые маски: на каждом шаге сравниваем, стоят ли единицы на двух соседних позициях i и i-1. 3⃣Подсчёт валидных чисел Если число прошло проверку — увеличиваем счётчик count. В конце возвращаем общее число подходящих значений. 😎 Решение:

func findIntegers(num int) int {
    count := 0
    for i := 0; i <= num; i++ {
        if check(i) {
            count++
        }
    }
    return count
}

func check(n int) bool {
    i := 31
    for i > 0 {
        if (n&(1<<i) != 0) && (n&(1<<(i-1)) != 0) {
            return false
        }
        i--
    }
    return true
}

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