Golang | LeetCode

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

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

Задача: 150. Evaluate Reverse Polish Notation Сложность: medium Вам дан массив строк под названием tokens, который представляет арифметическое выражение в обратной польской нотации. Вычислите это выражение. Верните целое число, которое представляет значение этого выражения. Обратите внимание на следующие моменты: Допустимые операторы: '+', '-', '*' и '/'. Каждый операнд может быть целым числом или другим выражением. Деление двух целых чисел всегда округляется к нулю. Деление на ноль в выражении отсутствует. Входные данные представляют собой действительное арифметическое выражение в обратной польской нотации. Ответ и все промежуточные вычисления можно представить 32-битным целым числом. Пример:

    
        Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9{}
    

👨‍💻 Алгоритм: 1⃣Обработка входных массивов: Для языков, таких как Java, где входные данные представлены фиксированным массивом, необходимо определить собственные методы для манипулирования массивом (например, удаление элементов). Это может включать сдвиг элементов для заполнения пробелов после удаления элемента. В качестве альтернативы, копирование массива в ArrayList могло бы упростить удаление, но за счет увеличения сложности по памяти с O(1) до O(n). 2⃣Обработка типов и деление в Python: Необходимо быть внимательным при обработке типов в Python во время обработки списка, поскольку числа могут быть представлены как строки или целые числа. Кроме того, стандартное деление в Python не округляет к нулю. Вместо этого использование int(a / b) достигает желаемого результата округления, что отличается от деления нацело int(a // b), которое является другим распространенным подходом. 3⃣Использование лямбда-функций: Лямбда-функции могут упростить реализацию арифметических операций (таких как +, -, *, /). Если вы знакомы с лямбда-функциями, они предлагают элегантное решение для динамической обработки операций. Если лямбда-функции новы или не поддерживаются в используемом языке программирования, можно использовать другие методы, а изучение лямбда-функций можно отложить на потом. 😎 Решение:

    
        func evalRPN(tokens []string) int {
    OPERATIONS := map[string]func(int, int) int{
        "+": func(a, b int) int { return a + b },
        "-": func(a, b int) int { return a - b },
        "*": func(a, b int) int { return a * b },
        "/": func(a, b int) int { return a / b },
    }
    currentPosition := 0
    for len(tokens) > 1 {
        for _, exist := OPERATIONS[strings.TrimSpace(tokens[currentPosition])]; !exist; {
            currentPosition += 1
            _, exist = OPERATIONS[strings.TrimSpace(tokens[currentPosition])]
        }
        operator := strings.TrimSpace(tokens[currentPosition])
        operation, _ := OPERATIONS[operator]
        number1, _ := strconv.Atoi(tokens[currentPosition-2])
        number2, _ := strconv.Atoi(tokens[currentPosition-1])
        tokens[currentPosition] = fmt.Sprintf("%d", operation(number1, number2))
        tokens = append(tokens[:currentPosition-2], tokens[currentPosition:]...)
        currentPosition -= 1
    }
    result, _ := strconv.Atoi(tokens[0])
    return result
}{}
    

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

Задача: №19. Remove Nth Node From End of List Сложность: medium Учитывая заголовок связанного списка, удалите n-й узел с конца списка и верните его заголовок. Пример:

    
        Input: head = [1,2,3,4,5], n = 2  
Output: [1,2,3,5]  
{}
    

👨‍💻 Алгоритм: 1⃣Создать фиктивный узел перед head, чтобы упростить обработку удаления. 2⃣Использовать два указателя (lead и cur), переместив lead на n+1 шагов вперед. 3⃣Перемещать оба указателя, пока lead не достигнет конца, затем удалить n-й узел. 😎 Решение:

    
        func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    lead, cur := dummy, dummy

    for i := 0; i <= n; i++ {
        lead = lead.Next
    }

    for lead != nil {
        lead = lead.Next
        cur = cur.Next
    }

    cur.Next = cur.Next.Next
    return dummy.Next
}{}
    

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

Задача: 673. Number of Longest Increasing Subsequence Сложность: medium Дан массив nums, нужно найти количество самых длинных строго возрастающих подпоследовательностей. Пример:

    
        Input: nums = [1,3,5,4,7]  
Output: 2
{}
    

Пояснение: Две последовательности длины 4 → [1,3,4,7] и [1,3,5,7] 👨‍💻 Алгоритм: 1⃣Инициализация Создаём два массива: - length[i] — длина наибольшей возрастающей подпоследовательности, заканчивающейся на i - count[i] — количество таких последовательностей длины length[i] Начальное значение: length[i] = 1, count[i] = 1 (каждый элемент сам по себе — подпоследовательность длины 1) 2⃣Динамика Для каждого i перебираем все j < i: - если nums[j] < nums[i], то nums[i] может продолжить подпоследовательность от j - если length[j]+1 > length[i], обновляем длину и сбрасываем счётчик - если length[j]+1 == length[i], добавляем count[j] к count[i] 3⃣Подсчёт результата Определяем максимальную длину maxLength, затем суммируем все count[i], где length[i] == maxLength. 😎 Решение:

    
        func findNumberOfLIS(nums []int) int {
    n := len(nums)
    length := make([]int, n)
    count := make([]int, n)
    for i := range length {
        length[i] = 1
        count[i] = 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                if length[j]+1 > length[i] {
                    length[i] = length[j] + 1
                    count[i] = count[j]
                } else if length[j]+1 == length[i] {
                    count[i] += count[j]
                }
            }
        }
    }

    maxLength := 0
    for _, l := range length {
        if l > maxLength {
            maxLength = l
        }
    }

    result := 0
    for i := 0; i < n; i++ {
        if length[i] == maxLength {
            result += count[i]
        }
    }

    return result
}{}
    

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

Задача: 779. K-th Symbol in Grammar Сложность: medium Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10. Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110. Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк. Пример:

    
        Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0{}
    

👨‍💻 Алгоритм: 1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal. 2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal). 3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal). 😎 Решение:

    
        package main

type Solution struct{}

func (s Solution) depthFirstSearch(n, k, rootVal int) int {
    if n == 1 {
        return rootVal
    }
    totalNodes := 1 << (n - 1)
    if k > totalNodes/2 {
        nextRootVal := 1
        if rootVal == 1 {
            nextRootVal = 0
        }
        return s.depthFirstSearch(n-1, k-totalNodes/2, nextRootVal)
    } else {
        nextRootVal := 0
        if rootVal == 1 {
            nextRootVal = 1
        }
        return s.depthFirstSearch(n-1, k, nextRootVal)
    }
}

func (s Solution) kthGrammar(n, k int) int {
    return s.depthFirstSearch(n, k, 0)
}{}
    

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

Задача: 993. Cousins in Binary Tree Сложность: easy Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false. Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей. Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1. Пример:

    
        Input: root = [1,2,3,4], x = 4, y = 3
Output: false{}
    

👨‍💻 Алгоритм: 1⃣Поиск глубины и родителя для каждого узла: Используйте поиск в глубину (DFS) для обхода дерева. Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y. 2⃣Проверка условий на кузенов: Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей. 3⃣Возврат результата: Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false. 😎 Решение:

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

func isCousins(root *TreeNode, x int, y int) bool {
    var parentX, parentY *TreeNode
    var depthX, depthY int = -1, -1

    var dfs func(*TreeNode, *TreeNode, int)
    dfs = func(node *TreeNode, parent *TreeNode, depth int) {
        if node == nil {
            return
        }
        if node.Val == x {
            parentX = parent
            depthX = depth
        } else if node.Val == y {
            parentY = parent
            depthY = depth
        } else {
            dfs(node.Left, node, depth + 1)
            dfs(node.Right, node, depth + 1)
        }
    }

    dfs(root, nil, 0)
    return depthX == depthY && parentX != parentY
}{}
    

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

Задача: 583. Delete Operation for Two Strings Сложность: medium Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми. На одном шаге можно удалить ровно один символ в любой строке. Пример:

    
        Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".{}
    

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

    
        func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([]int, n+1)

    for i := 0; i <= m; i++ {
        temp := make([]int, n+1)
        for j := 0; j <= n; j++ {
            if i == 0 || j == 0 {
                temp[j] = i + j
            } else if word1[i-1] == word2[j-1] {
                temp[j] = dp[j-1]
            } else {
                temp[j] = 1 + min(dp[j], temp[j-1])
            }
        }
        dp = temp
    }

    return dp[n]
}

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

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

Задача: 179. Largest Number Сложность: medium Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его. Поскольку результат может быть очень большим, вам необходимо вернуть строку вместо целого числа. Пример:

    
        Input: nums = [10,2]
Output: "210"{}
    

👨‍💻 Алгоритм: 1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎. 2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули. 3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки. 😎 Решение:

    
        package main

import (
    "sort"
    "strconv"
    "strings"
)

type Solution struct{}

func (s *Solution) LargestNumber(nums []int) string {
    strNums := make([]string, len(nums))
    for i, num := range nums {
        strNums[i] = strconv.Itoa(num)
    }

    sort.Slice(strNums, func(i, j int) bool {
        return strNums[i]+strNums[j] > strNums[j]+strNums[i]
    })

    if strNums[0] == "0" {
        return "0"
    }

    return strings.Join(strNums, "")
}

func main() {
    solution := Solution{}
    nums := []int{3, 30, 34, 5, 9}
    result := solution.LargestNumber(nums)
    println(result)
}{}
    

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

Задача: 130. Surrounded Regions Сложность: medium Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены: Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали. Регион: Для формирования региона соедините каждую ячейку 'O'. Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски. Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице. Пример:

    
        Input: board = [["X"]]

Output: [["X"]]{}
    

👨‍💻 Алгоритм: 1⃣Выбор начальных ячеек и инициация DFS: Начинаем с выбора всех ячеек, расположенных на границах доски. Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS). 2⃣Логика и выполнение DFS: Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'. Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'. 3⃣Классификация и финальная обработка ячеек: После обхода всех граничных ячеек мы получаем три типа ячеек: Ячейки с буквой 'X': эти ячейки можно считать стеной. Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'. Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'. 😎 Решение:

    
        func solve(board [][]byte) {
    if board == nil || len(board) == 0 {
        return
    }
    ROWS := len(board)
    COLS := len(board[0])
    borders := [][]int{}
    for r := 0; r < ROWS; r++ {
        borders = append(borders, []int{r, 0})
        borders = append(borders, []int{r, COLS - 1})
    }
    for c := 0; c < COLS; c++ {
        borders = append(borders, []int{0, c})
        borders = append(borders, []int{ROWS - 1, c})
    }
    var DFS func([][]byte, int, int)
    DFS = func(board [][]byte, row int, col int) {
        if board[row][col] != 'O' {
            return
        }
        board[row][col] = 'E'
        if col < COLS-1 {
            DFS(board, row, col+1)
        }
        if row < ROWS-1 {
            DFS(board, row+1, col)
        }
        if col > 0 {
            DFS(board, row, col-1)
        }
        if row > 0 {
            DFS(board, row-1, col)
        }
    }
    for _, pair := range borders {
        DFS(board, pair[0], pair[1])
    }
    for r := 0; r < ROWS; r++ {
        for c := 0; c < COLS; c++ {
            if board[r][c] == 'O' {
                board[r][c] = 'X'
            }
            if board[r][c] == 'E' {
                board[r][c] = 'O'
            }
        }
    }
}{}
    

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