Задача: 116. Populating Next Right Pointers in Each Node
Сложность: medium

Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next так, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1⃣Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных.

2⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня заключается в использовании некоторой разграничительной метки между уровнями. Обычно мы вставляем в очередь элемент NULL, который отмечает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого количества памяти, пропорционально количеству уровней в дереве.

3⃣Подход, который мы будем использовать здесь, будет иметь структуру вложенных циклов, чтобы обойти необходимость указателя NULL. По сути, на каждом шаге мы записываем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и не более. К моменту, когда мы закончим обработку заданного количества элементов, в очереди будут все узлы следующего уровня.
Мы начинаем с добавления корня дерева в очередь. Поскольку на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    Q := []*Node{root}
    for len(Q) > 0 {
        size := len(Q)
        for i := 0; i < size; i++ {
            node := Q[0]
            Q = Q[1:]
            if i < size-1 {
                node.Next = Q[0]
            }
            if node.Left != nil {
                Q = append(Q, node.Left)
            }
            if node.Right != nil {
                Q = append(Q, node.Right)
            }
        }
    }
    return root
}

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

Задача: 861. Score After Flipping Matrix
Сложность: hard

Дан целочисленный массив nums и целое число k. Верните длину самой короткой непустой подмассива nums, сумма которого составляет как минимум k. Если такого подмассива нет, верните -1.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1], k = 1
Output: 1

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

1⃣Создайте "моноочередь" индексов P: дек индексов x_0, x_1, ..., так чтобы P[x_0], P[x_1], ... увеличивались.

2⃣При добавлении нового индекса y, удалите x_i из конца дека, чтобы P[x_0], P[x_1], ..., P[y] увеличивались.

3⃣Если P[y] >= P[x_0] + K, то (как описано ранее) мы больше не рассматриваем этот x_0 и удаляем его из начала дека.

😎 Решение:

func shortestSubarray(A []int, K int) int {
    N := len(A)
    P := make([]int64, N+1)
    for i := 0; i < N; i++ {
        P[i+1] = P[i] + int64(A[i])
    }

    ans := N + 1
    monoq := []int{}

    for y := 0; y < len(P); y++ {
        for len(monoq) > 0 && P[y] <= P[monoq[len(monoq)-1]] {
            monoq = monoq[:len(monoq)-1]
        }
        for len(monoq) > 0 && P[y] >= P[monoq[0]]+int64(K) {
            ans = min(ans, y-monoq[0])
            monoq = monoq[1:]
        }
        monoq = append(monoq, y)
    }

    if ans < N+1 {
        return ans
    }
    return -1
}

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

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

Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy

Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.

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

Пример:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

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

1⃣Построение списка символов для word2:
Создайте список list2 для хранения всех символов из массива строк word2.

2⃣Итерация по word1 и проверка соответствующих символов:
Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2.

3⃣Возврат результата:
Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают.

😎 Решение:

func arrayStringsAreEqual(word1 []string, word2 []string) bool {
    list2 := strings.Join(word2, "")
    index := 0
    n := len(list2)

    for _, word := range word1 {
        for _, char := range word {
            if index >= n || byte(char) != list2[index] {
                return false
            }
            index++
        }
    }

    return index == n
}

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

Задача: 276. Paint Fence
Сложность: medium

Вы красите забор из n столбцов, используя k различных цветов. Вы должны красить столбы, следуя этим правилам:
Каждый столб должен быть окрашен в один цвет.
Не может быть трех или более подряд идущих столбцов одного цвета.
Учитывая два целых числа n и k, верните количество способов покрасить забор.

Пример:

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

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

1⃣Инициализация и определение вспомогательной функции:
Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов.
Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов.

2⃣Реализация базы и проверка кэша:
В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2.
Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i].

3⃣Расчет с использованием рекуррентного соотношения:
В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его.
Вызвать и вернуть totalWays(n).

😎 Решение:

func numWays(n int, k int) int {
    if n == 1 {
        return k
    }
    
    twoPostsBack := k
    onePostBack := k * k
    
    for i := 3; i <= n; i++ {
        curr := (k - 1) * (onePostBack + twoPostsBack)
        twoPostsBack = onePostBack
        onePostBack = curr
    }
    
    return onePostBack
}

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

Задача: 409. Longest Palindrome
Сложность: easy

Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.

Пример:

Input: s = "abccccdd"
Output: 7

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

1⃣Создайте словарь для подсчета количества каждого символа в строке.

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

3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа.

😎 Решение:

package main

func longestPalindrome(s string) int {
    charCount := make(map[rune]int)
    for _, char := range s {
        charCount[char]++
    }
    length := 0
    oddFound := false
    for _, count := range charCount {
        if count % 2 == 0 {
            length += count
        } else {
            length += count - 1
            oddFound = true
        }
    }
    if oddFound {
        return length + 1
    }
    return length
}

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

Задача: 611. Valid Triangle Number
Сложность: medium

Если задан целочисленный массив nums, верните количество выбранных из массива троек, которые могут образовывать треугольники, если принять их за длины сторон треугольника.

Пример:

Input: nums = [2,2,3,4]
Output: 3

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

1⃣Отсортируйте массив nums.

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

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

😎 Решение:

package main

import (
    "sort"
)

func triangleNumber(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    count := 0
    
    for k := n - 1; k >= 2; k-- {
        i := 0
        j := k - 1
        for i < j {
            if nums[i] + nums[j] > nums[k] {
                count += j - i
                j--
            } else {
                i++
            }
        }
    }
    
    return count
}

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

Задача: 1424. Diagonal Traverse II
Сложность: medium

Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке.

Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

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

1⃣Инициализируйте очередь с (0, 0) и список ответов ans.

2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.

3⃣Верните ans.

😎 Решение:

func findDiagonalOrder(nums [][]int) []int {
    queue := []struct{ row, col int }{{0, 0}}
    ans := []int{}
    
    for len(queue) > 0 {
        row, col := queue[0].row, queue[0].col
        queue = queue[1:]
        ans = append(ans, nums[row][col])
        
        if col == 0 && row + 1 < len(nums) {
            queue = append(queue, struct{ row, col int }{row + 1, col})
        }
        
        if col + 1 < len(nums[row]) {
            queue = append(queue, struct{ row, col int }{row, col + 1})
        }
    }
    
    return ans
}

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

Задача: 940. Distinct Subsequences II
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.

Пример:

Input: s = "abc"
Output: 7

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

1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.

2⃣Инициализировать матрицу DP нулями.
Пройти по каждому символу строки:
Если символ еще не был встречен, все подпоследовательности до текущего символа + текущий символ.
Если символ уже был встречен, учет всех подпоследовательностей, включающих текущий символ, с учетом предыдущих вхождений.

3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7.

😎 Решение:

package main

const MOD = 1000000007

func countSubsequences(s string) int {
    dp := make([]int, 26)
    for _, c := range s {
        index := c - 'a'
        sum := 0
        for _, val := range dp {
            sum = (sum + val) % MOD
        }
        dp[index] = (sum + 1) % MOD
    }
    result := 0
    for _, val := range dp {
        result = (result + val) % MOD
    }
    return result
}

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

Задача: 983. Minimum Cost For Tickets
Сложность: medium

Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365.

Билеты на поезд продаются тремя различными способами:

однодневный билет продаётся за costs[0] долларов,
семидневный билет продаётся за costs[1] долларов, и
тридцатидневный билет продаётся за costs[2] долларов.
Билеты позволяют путешествовать указанное количество дней подряд.

Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8.
Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days.

Пример:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

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

1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days.

2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его.

3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ.

😎 Решение:

package main

import "math"

type Solution struct {
    isTravelNeeded map[int]bool
}

func (s *Solution) solve(dp []int, days []int, costs []int, currDay int) int {
    if currDay > days[len(days)-1] {
        return 0
    }
    
    if !s.isTravelNeeded[currDay] {
        return s.solve(dp, days, costs, currDay+1)
    }
    
    if dp[currDay] != -1 {
        return dp[currDay]
    }
    
    oneDay := costs[0] + s.solve(dp, days, costs, currDay+1)
    sevenDay := costs[1] + s.solve(dp, days, costs, currDay+7)
    thirtyDay := costs[2] + s.solve(dp, days, costs, currDay+30)
    
    dp[currDay] = int(math.Min(float64(oneDay), math.Min(float64(sevenDay), float64(thirtyDay))))
    return dp[currDay]
}

func (s *Solution) MincostTickets(days []int, costs []int) int {
    lastDay := days[len(days)-1]
    dp := make([]int, lastDay+1)
    for i := range dp {
        dp[i] = -1
    }
    
    s.isTravelNeeded = make(map[int]bool)
    for _, day := range days {
        s.isTravelNeeded[day] = true
    }
    
    return s.solve(dp, days, costs, 1)
}

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

Задача: 772. Basic Calculator III
Сложность: medium

Реализуйте калькулятор, который вычисляет строковое выражение, содержащее числа, операторы +, -, *, /, а также скобки ( и ).

Пример:

Input: s = "1+1"
Output: 2

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

1⃣Стек и текущие переменные
Создаем стек stack, переменную curr для текущего числа и previousOperator, чтобы отслеживать последний оператор. Добавляем в строку символ @ как маркер конца строки.

2⃣Обработка символов строки
- Если символ — цифра, добавляем к текущему числу.
- Если символ — (, помещаем текущий оператор в стек и сбрасываем его.
- Если символ — оператор, применяем предыдущий оператор и добавляем результат в стек.
- Если символ — ), вычисляем сумму текущей группы внутри скобок, обновляем стек и оператор.

3⃣Подсчет результата
После обработки всей строки, складываем все числа в стеке и возвращаем итог.

😎 Решение:

package main

import (
    "strconv"
)

type Solution struct{}

func (sol *Solution) evaluate(operator byte, first, second string) string {
    x, _ := strconv.Atoi(first)
    y, _ := strconv.Atoi(second)
    res := 0

    if operator == '+' {
        res = x
    } else if operator == '-' {
        res = -x
    } else if operator == '*' {
        res = x * y
    } else {
        res = x / y
    }

    return strconv.Itoa(res)
}

func (sol *Solution) calculate(s string) int {
    stack := []string{}
    curr := ""
    previousOperator := byte('+')
    s += "@"
    operators := map[string]struct{}{"+": {}, "-": {}, "*": {}, "/": {}}

    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            curr += string(c)
        } else if c == '(' {
            stack = append(stack, string(previousOperator))
            previousOperator = '+'
        } else {
            if previousOperator == '*' || previousOperator == '/' {
                top := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                stack = append(stack, sol.evaluate(previousOperator, top, curr))
            } else {
                stack = append(stack, sol.evaluate(previousOperator, curr, "0"))
            }

            curr = ""
            previousOperator = c
            if c == ')' {
                currentTerm := 0
                for len(stack) > 0 {
                    top := stack[len(stack)-1]
                    if _, ok := operators[top]; ok {
                        break
                    }
                    stack = stack[:len(stack)-1]
                    val, _ := strconv.Atoi(top)
                    currentTerm += val
                }
                curr = strconv.Itoa(currentTerm)
                previousOperator = stack[len(stack)-1][0]
                stack = stack[:len(stack)-1]
            }
        }
    }

    ans := 0
    for _, num := range stack {
        val, _ := strconv.Atoi(num)
        ans += val
    }

    return ans
}

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

Задача: 739. Daily Temperatures
Сложность: medium

Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

1⃣Создайте стек для хранения индексов дней с температурами, для которых еще не найден более теплый день.

2⃣Пройдите по массиву температур и для каждого дня: Пока текущая температура больше температуры дня на вершине стека, обновляйте массив ответов и удаляйте вершину стека. Добавьте текущий день в стек.

3⃣Возвращайте массив ответов.

😎 Решение:

vpackage main

func dailyTemperatures(T []int) []int {
    n := len(T)
    answer := make([]int, n)
    stack := []int{}
    
    for i := 0; i < n; i++ {
        for len(stack) > 0 && T[i] > T[stack[len(stack)-1]] {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            answer[j] = i - j
        }
        stack = append(stack, i)
    }
    
    return answer
}

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

func crackSafe(n int, k int) string {
    seen := make(map[string]bool)
    var result []byte

    startNode := strings.Repeat("0", n-1)
    dfs(startNode, k, seen, &result)

    result = append(result, startNode...)
    return string(result)
}

func dfs(node string, k int, seen map[string]bool, result *[]byte) {
    for x := 0; x < k; x++ {
        neighbor := node + fmt.Sprint(x)
        if !seen[neighbor] {
            seen[neighbor] = true
            dfs(neighbor[1:], k, seen, result)
            *result = append(*result, byte(x+'0'))
        }
    }
}

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

Задача: 278. First Bad Version
Сложность: easy

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

Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.

Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.

Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

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

1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.

2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.

3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.

😎 Решение:

package main

func firstBadVersion(n int) int {
    left, right := 1, n
    for left < right {
        mid := left + (right-left)/2
        if isBadVersion(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

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

Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

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

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

func isBoomerang(points [][]int) bool {
    x1, y1 := points[0][0], points[0][1]
    x2, y2 := points[1][0], points[1][1]
    x3, y3 := points[2][0], points[2][1]
    return (x1 != x2 || y1 != y2) && (x1 != x3 || y1 != y3) && (x2 != x3 || y2 != y3) && (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)) != 0
}

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

Задача: 789. Escape The Ghosts
Сложность: medium

Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами.

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

Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом.

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

Пример:

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

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

1⃣Проверьте, что наше таксическое расстояние до цели меньше, чем расстояние от любого привидения до цели.

2⃣Если это так, мы можем гарантированно добраться до цели раньше любого привидения.

3⃣Если привидение может добраться до цели раньше нас или одновременно с нами, побег невозможен.

😎 Решение:

package main

import "math"

func escapeGhosts(ghosts [][]int, target []int) bool {
    taxi := func(P, Q []int) int {
        return int(math.Abs(float64(P[0] - Q[0])) + math.Abs(float64(P[1] - Q[1])))
    }

    playerDistance := taxi([]int{0, 0}, target)
    for _, ghost := range ghosts {
        if taxi(ghost, target) <= playerDistance {
            return false
        }
    }
    return true
}

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

Задача: 114. Flatten Binary Tree to Linked List
Сложность: medium

"Связный список" должен использовать тот же класс TreeNode, где указатель на правого ребенка указывает на следующий узел в списке, а указатель на левого ребенка всегда равен null.
"Связный список" должен быть в том же порядке, что и обход бинарного дерева в прямом порядке.

Пример:

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

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

1⃣Плоское преобразование дерева: Рекурсивно преобразуем левое и правое поддеревья заданного узла, сохраняя соответствующие конечные узлы в leftTail и rightTail.

2⃣Установка соединений: Если у текущего узла есть левый ребенок, выполняем следующие соединения:
leftTail.right = node.right
node.right = node.left
node.left = None

3⃣Возврат конечного узла: Возвращаем rightTail, если у узла есть правый ребенок, иначе возвращаем leftTail.

😎 Решение:

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

func flattenTree(node *TreeNode) *TreeNode {
    if node == nil {
        return nil
    }
    if node.Left == nil && node.Right == nil {
        return node
    }
    leftTail := flattenTree(node.Left)
    rightTail := flattenTree(node.Right)
    if leftTail != nil {
        leftTail.Right = node.Right
        node.Right = node.Left
        node.Left = nil
    }
    if rightTail != nil {
        return rightTail
    } else {
        return leftTail
    }
}

func flatten(root *TreeNode) {
    flattenTree(root)
}

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

Задача: 296. Best Meeting Point
Сложность: hard

Дан бинарный сетка размером m x n, где каждая 1 обозначает дом одного друга. Верните минимальное общее расстояние путешествия.

Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи.

Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Пример:

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.

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

1⃣Определение координат домов:
Пройдите по сетке и соберите координаты всех домов (ячейки с значением 1) в два списка: один для координат x и один для координат y.

2⃣Нахождение медианы:
Отсортируйте списки координат x и y.
Найдите медианы в обоих списках. Медианы координат x и y укажут оптимальную точку встречи.

3⃣Вычисление минимального общего расстояния:
Вычислите сумму Манхэттенских расстояний от каждого дома до точки встречи, используя найденные медианы в качестве координат точки встречи.
Верните это значение как минимальное общее расстояние путешествия.

😎 Решение:

package main

import (
  "math"
)

func minTotalDistance(grid [][]int) int {
  minDistance := math.MaxInt32
  for row := 0; row < len(grid); row++ {
    for col := 0; col < len(grid[0]); col++ {
      distance := search(grid, row, col)
      if distance < minDistance {
        minDistance = distance
      }
    }
  }
  return minDistance
}

func search(grid [][]int, row int, col int) int {
  type Point struct {
    r, c, d int
  }
  q := []Point{{row, col, 0}}
  m := len(grid)
  n := len(grid[0])
  visited := make([][]bool, m)
  for i := range visited {
    visited[i] = make([]bool, n)
  }
  totalDistance := 0

  for len(q) > 0 {
    point := q[0]
    q = q[1:]
    r, c, d := point.r, point.c, point.d

    if r < 0 || c < 0 || r >= m || c >= n || visited[r][c] {
      continue
    }

    if grid[r][c] == 1 {
      totalDistance += d
    }

    visited[r][c] = true

    q = append(q, Point{r + 1, c, d + 1})
    q = append(q, Point{r - 1, c, d + 1})
    q = append(q, Point{r, c + 1, d + 1})
    q = append(q, Point{r, c - 1, d + 1})
  }

  return totalDistance
}

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

Задача: 1234. Replace the Substring for Balanced String
Сложность: medium

Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.

Пример:

Input: s = "QWER"
Output: 0

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

1⃣Проверка баланса:
Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0.

2⃣Подсчет частоты символов:
Подсчитаем количество каждого символа в строке s.

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

😎 Решение:

func balancedString(s string) int {
    n := len(s)
    count := make(map[byte]int)
    for i := 0; i < n; i++ {
        count[s[i]]++
    }
    target := n / 4

    isBalanced := func() bool {
        return count['Q'] <= target && count['W'] <= target && count['E'] <= target && count['R'] <= target
    }

    if isBalanced() {
        return 0
    }

    minLength := n
    left := 0

    for right := 0; right < n; right++ {
        count[s[right]]--
        for isBalanced() {
            if right-left+1 < minLength {
                minLength = right-left+1
            }
            count[s[left]]++
            left++
        }
    }

    return minLength
}

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

Задача: 348. Design Tic-Tac-Toe
Сложность: medium

Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:

Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:

TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.

Пример:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

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

1⃣Инициализация:
Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно.
Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно.
Инициализируйте размер доски n.

2⃣Выполнение хода:
Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода.
Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal.

3⃣Проверка победы:
Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя.
Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода.

😎 Решение:

type TicTacToe struct {
    rows        []int
    cols        []int
    diagonal    int
    antiDiagonal int
    n           int
}

func Constructor(n int) TicTacToe {
    return TicTacToe{
        rows:        make([]int, n),
        cols:        make([]int, n),
        diagonal:    0,
        antiDiagonal: 0,
        n:           n,
    }
}

func (this *TicTacToe) Move(row int, col int, player int) int {
    add := 1
    if player == 2 {
        add = -1
    }

    this.rows[row] += add
    this.cols[col] += add
    if row == col {
        this.diagonal += add
    }
    if row+col == this.n-1 {
        this.antiDiagonal += add
    }

    if abs(this.rows[row]) == this.n || abs(this.cols[col]) == this.n || abs(this.diagonal) == this.n || abs(this.antiDiagonal) == this.n {
        return player
    }
    return 0
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

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

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

2⃣Определение границ компонента:
Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет.

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

func colorBorder(grid [][]int, row int, col int, color int) [][]int {
    m, n := len(grid), len(grid[0])
    originalColor := grid[row][col]
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    borders := [][]int{}

    var dfs func(r, c int)
    dfs = func(r, c int) {
        visited[r][c] = true
        isBorder := false
        for _, dir := range [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
            nr, nc := r+dir[0], c+dir[1]
            if nr >= 0 && nr < m && nc >= 0 && nc < n {
                if !visited[nr][nc] {
                    if grid[nr][nc] == originalColor {
                        dfs(nr, nc)
                    } else {
                        isBorder = true
                    }
                }
            } else {
                isBorder = true
            }
        }
        if isBorder || r == 0 || r == m-1 || c == 0 || c == n-1 {
            borders = append(borders, []int{r, c})
        }
    }

    dfs(row, col)
    for _, border := range borders {
        grid[border[0]][border[1]] = color
    }

    return grid
}

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