Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

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

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

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

3⃣Рекурсивный вызов для левого и правого дочерних узлов:
Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎 Решение:

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

func longestZigZag(root *TreeNode) int {
    maxLength := 0

    var dfs func(node *TreeNode, isLeft bool, length int)
    dfs = func(node *TreeNode, isLeft bool, length int) {
        if node == nil {
            return
        }
        if length > maxLength {
            maxLength = length
        }
        if isLeft {
            dfs(node.Left, false, length+1)
            dfs(node.Right, true, 1)
        } else {
            dfs(node.Right, true, length+1)
            dfs(node.Left, false, 1)
        }
    }

    dfs(root, true, 0)
    dfs(root, false, 0)

    return maxLength
}

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

Задача: 144. Binary Tree Preorder Traversal
Сложность: easy

Дан корень бинарного дерева, верните предварительный обход значений его узлов.

Пример:

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

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

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

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

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

😎 Решение:

func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    stack := []*TreeNode{root}

    output := []int{}

    for len(stack) > 0 {
        length := len(stack)
        root = stack[length-1]
        stack = stack[:length-1]

        if root != nil {
            output = append(output, root.Val)
        }

        if root.Right != nil {
            stack = append(stack, root.Right)
        }

        if root.Left != nil {
            stack = append(stack, root.Left)
        }
    }

    return output
}

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

Задача: 688. Knight Probability in Chessboard
Сложность: medium

На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1).

Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении.

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

Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски.

Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы.

Пример:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

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

1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня.

2⃣Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j].

3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность.

😎 Решение:

package main

func knightProbability(n int, k int, row int, column int) float64 {
    directions := [8][2]int{{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}
    dp := make([][][]float64, k+1)
    for i := range dp {
        dp[i] = make([][]float64, n)
        for j := range dp[i] {
            dp[i][j] = make([]float64, n)
        }
    }
    dp[0][row][column] = 1

    for moves := 1; moves <= k; moves++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                for _, direction := range directions {
                    prevI, prevJ := i-direction[0], j-direction[1]
                    if prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n {
                        dp[moves][i][j] += dp[moves-1][prevI][prevJ] / 8
                    }
                }
            }
        }
    }

    totalProbability := 0.0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            totalProbability += dp[k][i][j]
        }
    }

    return totalProbability
}

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

Задача: №93. Restore IP Addresses
Сложность: medium

Дана строка s, представляющая только цифры. Необходимо вернуть все возможные допустимые комбинации разделения строки на IP-адреса.

Пример:

Input: s = "25525511135"  
Output: ["255.255.11.135", "255.255.111.35"]  

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

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

2⃣Проверяем, что каждая часть является допустимой (1-3 цифры, не начинается с 0, не превышает 255).

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

😎 Решение:

func restoreIpAddresses(s string) []string {
    var ans []string
    var valid func(s string, start int, length int) bool
    valid = func(s string, start int, length int) bool {
        return length == 1 ||
            (s[start] != '0' && (length < 3 || s[start:start+length] <= "255"))
    }
    var helper func(s string, startIndex int, dots []int)
    helper = func(s string, startIndex int, dots []int) {
        remainingLength := len(s) - startIndex
        remainingNumberOfIntegers := 4 - len(dots)
        if remainingLength > remainingNumberOfIntegers*3 ||
            remainingLength < remainingNumberOfIntegers {
            return
        }
        if len(dots) == 3 {
            if valid(s, startIndex, remainingLength) {
                temp := ""
                last := 0
                for i := 0; i < len(dots); i++ {
                    temp += s[last : last+dots[i]]
                    if last != startIndex {
                        temp += "."
                    }
                    last += dots[i]
                }
                temp += s[startIndex:]
                ans = append(ans, temp)
            }
            return
        }
        for curPos := 1; curPos <= 3 && curPos <= remainingLength; curPos++ {
            dots = append(dots, curPos)
            if valid(s, startIndex, curPos) {
                helper(s, startIndex+curPos, dots)
            }
            dots = dots[:len(dots)-1]
        }
    }
    helper(s, 0, []int{})
    return ans
}

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

Задача: 636. Exclusive Time of Functions
Сложность: medium

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов
Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

3⃣Обновление времени выполнения
Когда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций.

😎 Решение:

package main

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

func exclusiveTime(n int, logs []string) []int {
  stack := []int{}
  times := make([]int, n)
  prevTime := 0

  for _, log := range logs {
    parts := strings.Split(log, ":")
    fid, _ := strconv.Atoi(parts[0])
    typ := parts[1]
    time, _ := strconv.Atoi(parts[2])

    if typ == "start" {
      if len(stack) > 0 {
        times[stack[len(stack)-1]] += time - prevTime
      }
      stack = append(stack, fid)
      prevTime = time
    } else {
      times[stack[len(stack)-1]] += time - prevTime + 1
      stack = stack[:len(stack)-1]
      prevTime = time + 1
    }
  }

  return times
}

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

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

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

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.

2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

import (
    "container/heap"
)

func isPossible(target []int) bool {
    pq := &MaxHeap{}
    heap.Init(pq)
    total := 0
    for _, num := range target {
        heap.Push(pq, num)
        total += num
    }
    
    for (*pq)[0] > 1 {
        maxVal := heap.Pop(pq).(int)
        total -= maxVal
        if maxVal < total || total == 0 || maxVal % total == 0 {
            return false
        }
        heap.Push(pq, maxVal % total)
        total += (*pq)[0]
    }
    return true
}

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

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

Задача: 567. Permutation in String
Сложность: medium

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

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

func checkInclusion(s1 string, s2 string) bool {
    s1Len, s2Len := len(s1), len(s2)
    if s1Len > s2Len {
        return false
    }

    s1Count, s2Count := make([]int, 26), make([]int, 26)
    for i := 0; i < s1Len; i++ {
        s1Count[s1[i]-'a']++
        s2Count[s2[i]-'a']++
    }

    for i := 0; i < s2Len-s1Len; i++ {
        if equal(s1Count, s2Count) {
            return true
        }
        s2Count[s2[i]-'a']--
        s2Count[s2[i+s1Len]-'a']++
    }

    return equal(s1Count, s2Count)
}

func equal(a, b []int) bool {
    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

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

Задача: 906. Super Palindromes
Сложность: hard

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

Input: left = "4", right = "1000"
Output: 4

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

1⃣Найти все палиндромы до корня из right.

2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right].

3⃣Подсчитать количество таких суперпалиндромов.

😎 Решение:

public class Solution {
    private bool IsPalindrome(long x) {
        string s = x.ToString();
        char[] arr = s.ToCharArray();
        Array.Reverse(arr);
        return s == new string(arr);
    }

    public int SuperpalindromesInRange(string left, string right) {
        long leftNum = long.Parse(left);
        long rightNum = long.Parse(right);
        int count = 0;

        for (int i = 1; i < 100000; i++) {
            string s = i.ToString();
            long palin1 = long.Parse(s + new string(s.Reverse().ToArray()));
            long palin2 = long.Parse(s + new string(s.Reverse().Skip(1).ToArray()));

            if (palin1 * palin1 > rightNum) {
                break;
            }
            if (palin1 * palin1 >= leftNum && IsPalindrome(palin1 * palin1)) {
                count++;
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && IsPalindrome(palin2 * palin2)) {
                count++;
            }
        }

        return count;
    }
}

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

Задача: №58. Length of Last Word
Сложность: easy

Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке.

Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами.

Пример:

Input: s = "Hello World"  
Output: 5  
Explanation: The last word is "World" with length 5.  

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

1⃣Поиск последнего слова:
- Начинаем обход строки с конца, пропуская пробелы.
- Как только встречаем первый непробельный символ, находим последний символ последнего слова.

2⃣Определение длины последнего слова:
- Подсчитываем количество символов, пока не встретим пробел или не дойдём до начала строки.

3⃣Итог:
- Используя обратную итерацию и пропуск пробелов, определяем начало и конец последнего слова для вычисления его длины.

😎 Решение:

func lengthOfLastWord(s string) int {
    p := len(s) - 1
    for p >= 0 && s[p] == ' ' {
        p--
    }
    length := 0
    for p >= 0 && s[p] != ' ' {
        p--
        length++
    }
    return length
}

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

Задача: 506. Relative Ranks
Сложность: easy

Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.

Пример:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

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

1⃣Инициализация и нахождение максимального значения
Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score.

2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].

3⃣Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.

😎 Решение:

func findRelativeRanks(score []int) []string {
    N := len(score)
    maxScore := 0
    for _, s := range score {
        if s > maxScore {
            maxScore = s
        }
    }
    scoreToIndex := make([]int, maxScore + 1)
    
    for i, s := range score {
        scoreToIndex[s] = i + 1
    }
    
    rank := make([]string, N)
    medals := []string{"Gold Medal", "Silver Medal", "Bronze Medal"}
    place := 1
    
    for i := maxScore; i >= 0; i-- {
        if scoreToIndex[i] != 0 {
            originalIndex := scoreToIndex[i] - 1
            if place < 4 {
                rank[originalIndex] = medals[place - 1]
            } else {
                rank[originalIndex] = fmt.Sprintf("%d", place)
            }
            place++
        }
    }
    
    return rank
}

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

Задача: 1171. Remove Zero Sum Consecutive Nodes from Linked List
Сложность: medium

Дан указатель на голову связанного списка. Мы многократно удаляем последовательные последовательности узлов, сумма которых равна 0, до тех пор, пока такие последовательности не исчезнут.

После этого верните голову конечного связанного списка. Вы можете вернуть любой такой ответ.

Пример:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

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

1⃣Инициализируйте новый узел ListNode с именем front со значением 0, у которого поле next указывает на head, и узел start, указывающий на front.

2⃣Обрабатывайте все узлы в связанном списке, пока start != null. Инициализируйте переменную prefixSum значением 0 и узел ListNode с именем end, указывающий на start.next. Обрабатывайте остальные узлы в связанном списке, пока end != null: добавьте значение узла end к prefixSum. Если prefixSum равен 0, установите соединение от узла start к последнему узлу после последовательности с суммой ноль, установив start.next равным end.next. Установите end равным end.next.

3⃣Установите start равным start.next. Верните front.next. Узел front указывает на голову конечного связанного списка.

😎 Решение

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeZeroSumSublists(head *ListNode) *ListNode {
    front := &ListNode{0, head}
    start := front

    for start != nil {
        prefixSum := 0
        end := start.Next

        for end != nil {
            prefixSum += end.Val
            if prefixSum == 0 {
                start.Next = end.Next
            }
            end = end.Next
        }

        start = start.Next
    }
    return front.Next
}

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

Задача: 741. Cherry Pickup
Сложность: hard

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

3⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.

😎 Решение:

package main

import "math"

func cherryPickup(grid [][]int) int {
    n := len(grid)
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, 2*n-1)
            for k := range dp[i][j] {
                dp[i][j][k] = math.MinInt32
            }
        }
    }
    dp[0][0][0] = grid[0][0]

    for k := 1; k < 2*n-1; k++ {
        for i1 := max(0, k-n+1); i1 <= min(n-1, k); i1++ {
            for i2 := max(0, k-n+1); i2 <= min(n-1, k); i2++ {
                j1, j2 := k-i1, k-i2
                if j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1 {
                    maxCherries := math.MinInt32
                    if i1 > 0 && i2 > 0 {
                        maxCherries = max(maxCherries, dp[i1-1][i2-1][k-1])
                    }
                    if i1 > 0 {
                        maxCherries = max(maxCherries, dp[i1-1][i2][k-1])
                    }
                    if i2 > 0 {
                        maxCherries = max(maxCherries, dp[i1][i2-1][k-1])
                    }
                    maxCherries = max(maxCherries, dp[i1][i2][k-1])
                    if maxCherries != math.MinInt32 {
                        dp[i1][i2][k] = maxCherries + grid[i1][j1]
                        if i1 != i2 {
                            dp[i1][i2][k] += grid[i2][j2]
                        }
                    }
                }
            }
        }
    }

    return max(0, dp[n-1][n-1][2*n-1])
}

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

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

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

Задача: 786. K-th Smallest Prime Fraction
Сложность: medium

Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k.

Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j].

Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

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

1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей.

2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью.

3⃣Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби.

😎 Решение:

package main

import (
    "container/heap"
)

type Fraction struct {
    value   float64
    indices [2]int
}

type PriorityQueue []Fraction

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].value < pq[j].value
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(Fraction))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func kthSmallestPrimeFraction(arr []int, k int) []int {
    pq := &PriorityQueue{}
    heap.Init(pq)

    for i := 0; i < len(arr)-1; i++ {
        heap.Push(pq, Fraction{float64(arr[i]) / float64(arr[len(arr)-1]), [2]int{i, len(arr) - 1}})
    }

    for i := 0; i < k-1; i++ {
        cur := heap.Pop(pq).(Fraction)
        if cur.indices[1]-1 > cur.indices[0] {
            heap.Push(pq, Fraction{float64(arr[cur.indices[0]]) / float64(arr[cur.indices[1]-1]), [2]int{cur.indices[0], cur.indices[1] - 1}})
        }
    }

    result := heap.Pop(pq).(Fraction)
    return []int{arr[result.indices[0]], arr[result.indices[1]]}
}

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

Задача: №21. Merge Two Sorted Lists
Сложность: easy

Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.

Пример:

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]  

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

1⃣Создать фиктивный (dummy) узел и указатель current, который будет использоваться для сборки нового списка.

2⃣Использовать цикл, чтобы попарно сравнивать узлы list1 и list2, добавляя в новый список меньший из элементов.

3⃣Когда один из списков закончится, просто присоединить оставшиеся элементы второго списка.

😎 Решение:

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    result := &ListNode{}
    current := result

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            current.Next = list1
            list1 = list1.Next
        } else {
            current.Next = list2
            list2 = list2.Next
        }
        current = current.Next
    }

    if list1 != nil {
        current.Next = list1
    } else {
        current.Next = list2
    }

    return result.Next
}

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

Задача: 648. Replace Words
Сложность: medium

В английском языке есть понятие "корень", за которым может следовать какое-то другое слово, чтобы образовать другое более длинное слово - назовем это слово производным. Например, если за корнем "help" следует слово "ful", мы можем образовать производное "helpful". Дайте словарь, состоящий из множества корней, и предложение, состоящее из слов, разделенных пробелами, замените все производные в предложении на образующий их корень. Если производное может быть заменено более чем одним корнем, замените его корнем, имеющим наименьшую длину. Верните предложение после замены.

Пример:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

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

1⃣Преобразуйте словарь корней в набор для быстрого поиска.

2⃣Пройдите по каждому слову в предложении и найдите самый короткий корень, который является префиксом этого слова.

3⃣Замените слово найденным корнем и соберите обновленное предложение.

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

func replaceWords(roots []string, sentence string) string {
    rootSet := make(map[string]struct{})
    for _, root := range roots {
        rootSet[root] = struct{}{}
    }
    
    replace := func(word string) string {
        for i := 1; i <= len(word); i++ {
            if _, exists := rootSet[word[:i]]; exists {
                return word[:i]
            }
        }
        return word
    }
    
    words := strings.Split(sentence, " ")
    for i, word := range words {
        words[i] = replace(word)
    }
    
    return strings.Join(words, " ")
}

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

Задача: 361. Bomb Enemy
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

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

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

2⃣Реализовать функцию killEnemies(row, col), которая считает количество врагов, убитых бомбой, установленных в пустой ячейке (row, col), проверяя все четыре направления (влево, вправо, вверх, вниз) до стены или границы сетки.

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

😎 Решение:

package main

func maxKilledEnemies(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])
    maxCount := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == '0' {
                hits := killEnemies(row, col, grid)
                if hits > maxCount {
                    maxCount = hits
                }
            }
        }
    }

    return maxCount
}

func killEnemies(row, col int, grid [][]byte) int {
    enemyCount := 0
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for _, dir := range directions {
        r, c := row + dir[0], col + dir[1]

        for r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) {
            if grid[r][c] == 'W' {
                break
            }
            if grid[r][c] == 'E' {
                enemyCount++
            }
            r += dir[0]
            c += dir[1]
        }
    }

    return enemyCount
}

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

Задача: 672. Bulb Switcher II
Сложность: medium


Дано количество лампочек n (все включены) и количество нажатий presses. Есть 4 кнопки с разной логикой.
Нужно определить, сколько различных состояний лампочек может быть получено после ровно presses нажатий.

Пример:

Input: n = 1, presses = 1` → 
Output: 2

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

1⃣Ограничиваем количество лампочек до 6
Поскольку шаблоны переключений кнопок начинают повторяться при n > 6, достаточно проверять только первые min(n, 6) лампочек. Остальные комбинации будут симметричны и не дадут новых состояний.

2⃣Перебираем все возможные комбинации нажатий кнопок
Каждая из 4 кнопок может быть либо нажата, либо нет — всего 2⁴ = 16 комбинаций.
Проверяем каждую комбинацию cand, у которой:
- Кол-во нажатых кнопок bcount ≤ presses
- Чётность bcount % 2 == presses % 2 (так как порядок не важен)

3⃣Симулируем состояние лампочек и собираем уникальные
Для каждой валидной комбинации симулируем, какие лампочки будут переключены (с помощью битовых масок и XOR).
Сохраняем результат в map, чтобы получить множество уникальных состояний. Возвращаем размер множества.

😎 Решение:

import (
    "math/bits"
)

func flipLights(n int, m int) int {
    seen := make(map[int]struct{})
    n = min(n, 6)
    shift := max(0, 6-n)

    for cand := 0; cand < 16; cand++ {
        bcount := bits.OnesCount(uint(cand))
        if bcount % 2 == m % 2 && bcount <= m {
            lights := 0
            if (cand>>0)&1 > 0 { lights ^= 0b111111 >> shift }
            if (cand>>1)&1 > 0 { lights ^= 0b010101 >> shift }
            if (cand>>2)&1 > 0 { lights ^= 0b101010 >> shift }
            if (cand>>3)&1 > 0 { lights ^= 0b100100 >> shift }
            seen[lights] = struct{}{}
        }
    }

    return len(seen)
}

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

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

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