#medium
🤔 Задача: 221. Maximal Square

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

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

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

1⃣Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения.

2⃣Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.

3⃣По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата.

😎 Решение:

func maximalSquare(matrix [][]byte) int {
    rows := len(matrix)
    cols := 0
    if rows > 0 {
        cols = len(matrix[0])
    }
    dp := make([]int, cols+1)
    maxsqlen := 0
    prev := 0
    
    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            temp := dp[j]
            if matrix[i-1][j-1] == '1' {
                dp[j] = min(dp[j-1], min(prev, dp[j])) + 1
                maxsqlen = max(maxsqlen, dp[j])
            } else {
                dp[j] = 0
            }
            prev = temp
        }
    }
    
    return maxsqlen * maxsqlen
}

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
}

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

#easy
🤔 Задача: 222. Count Complete Tree Nodes

Учитывая корень полного двоичного дерева, верните количество узлов в дереве. Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n. Разработайте алгоритм, который выполняется за время, меньшее, чем O(n).

Привет:

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

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

1⃣Инициализация и проверка пустоты дерева
Если дерево пустое, вернуть 0.
Рассчитать глубину дерева d.

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

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

😎 Решение:

import (
    "math"
)

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

func computeDepth(node *TreeNode) int {
    d := 0
    for node.Left != nil {
        node = node.Left
        d++
    }
    return d
}

func exists(idx, d int, node *TreeNode) bool {
    left, right := 0, int(math.Pow(2, float64(d)))-1
    for i := 0; i < d; i++ {
        pivot := left + (right-left)/2
        if idx <= pivot {
            node = node.Left
            right = pivot
        } else {
            node = node.Right
            left = pivot + 1
        }
    }
    return node != nil
}

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    d := computeDepth(root)
    if d == 0 {
        return 1
    }

    left, right := 1, int(math.Pow(2, float64(d)))-1
    for left <= right {
        pivot := left + (right-left)/2
        if exists(pivot, d, root) {
            left = pivot + 1
        } else {
            right = pivot - 1
        }
    }

    return int(math.Pow(2, float64(d)) - 1 + float64(left))
}

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

#medium
Задача: 277. Find the Celebrity

Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них.
Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1.

Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

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

1⃣Найти потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.

2⃣Реализовать функцию isCelebrity(candidate):
Проверить, знает ли кандидат кого-либо из людей (исключая самих себя).
Проверить, знают ли все остальные кандидата (исключая самого кандидата).
Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью.

3⃣Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.

😎 Решение:

type Solution struct {
    n     int
    cache map[pair]bool
}

type pair struct {
    a, b int
}

func (s *Solution) findCelebrity(n int) int {
    s.n = n
    s.cache = make(map[pair]bool)
    celebrityCandidate := 0
    for i := 1; i < n; i++ {
        if s.cachedKnows(celebrityCandidate, i) {
            celebrityCandidate = i
        }
    }
    if s.isCelebrity(celebrityCandidate) {
        return celebrityCandidate
    }
    return -1
}

func (s *Solution) isCelebrity(i int) bool {
    for j := 0; j < s.n; j++ {
        if i == j {
            continue
        }
        if s.cachedKnows(i, j) || !s.cachedKnows(j, i) {
            return false
        }
    }
    return true
}

func (s *Solution) cachedKnows(a, b int) bool {
    key := pair{a, b}
    if _, exists := s.cache[key]; !exists {
        s.cache[key] = knows(a, b)
    }
    return s.cache[key]
}

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

#medium
Задача: 223. Rectangle Area

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

Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2).

Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2).

Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

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

1⃣Вычислить площади двух прямоугольников:
Рассчитайте площади прямоугольников A и B, умножив их ширину на высоту.

2⃣Вычислить перекрытие:
Найдите перекрытие по оси X и оси Y. Если перекрытие существует, вычислите площадь перекрытия.

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

😎 Решение:

func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
    areaOfA := (ay2 - ay1) * (ax2 - ax1)
    areaOfB := (by2 - by1) * (bx2 - bx1)

    left := max(ax1, bx1)
    right := min(ax2, bx2)
    xOverlap := right - left

    top := min(ay2, by2)
    bottom := max(ay1, by1)
    yOverlap := top - bottom

    areaOfOverlap := 0
    if xOverlap > 0 && yOverlap > 0 {
        areaOfOverlap = xOverlap * yOverlap
    }

    totalArea := areaOfA + areaOfB - areaOfOverlap
    return totalArea
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

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

#hard
Задача: 224. Basic Calculator

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

Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

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

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

3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.

😎 Решение:

package main

import (
  "fmt"
  "math"
  "strconv"
  "unicode"
)

type Solution struct{}

func (s Solution) evaluateExpr(stack *[]interface{}) int {
  if len(*stack) == 0 || !isInt((*stack)[len(*stack)-1]) {
    *stack = append(*stack, 0)
  }

  res := pop(stack).(int)

  for len(*stack) != 0 && (*stack)[len(*stack)-1].(rune) != ')' {
    sign := pop(stack).(rune)

    if sign == '+' {
      res += pop(stack).(int)
    } else {
      res -= pop(stack).(int)
    }
  }
  return res
}

func (s Solution) calculate(expr string) int {
  operand := 0
  n := 0
  stack := []interface{}{}

  for i := len(expr) - 1; i >= 0; i-- {
    ch := expr[i]

    if unicode.IsDigit(rune(ch)) {
      operand = int(math.Pow(10, float64(n))) * (int(ch-'0')) + operand
      n += 1
    } else if ch != ' ' {
      if n != 0 {
        stack = append(stack, operand)
        n = 0
        operand = 0
      }
      if ch == '(' {
        res := s.evaluateExpr(&stack)
        pop(&stack)
        stack = append(stack, res)
      } else {
        stack = append(stack, rune(ch))
      }
    }
  }

  if n != 0 {
    stack = append(stack, operand)
  }

  return s.evaluateExpr(&stack)
}

func pop(stack *[]interface{}) interface{} {
  if len(*stack) == 0 {
    return nil
  }
  res := (*stack)[len(*stack)-1]
  *stack = (*stack)[:len(*stack)-1]
  return res
}

func isInt(value interface{}) bool {
  _, ok := value.(int)
  return ok
}

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

#easy
Задача: 225. Implement Stack using Queues

Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).

Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.

Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.

Пример:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

1⃣Реализация методов push и pop:
Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.
Метод pop удаляет элемент из q1 и обновляет значение top.

2⃣Реализация методов top и empty:
Метод top возвращает верхний элемент стека.
Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.

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

😎 Решение:

package main

import "fmt"

type MyStack struct {
    q1 []int
    q2 []int
    topElement int
}

func Constructor() MyStack {
    return MyStack{
        q1: []int{},
        q2: []int{},
    }
}

func (this *MyStack) Push(x int)  {
    this.q2 = append(this.q2, x)
    this.topElement = x
    for len(this.q1) > 0 {
        this.q2 = append(this.q2, this.q1[0])
        this.q1 = this.q1[1:]
    }
    this.q1, this.q2 = this.q2, this.q1
}

func (this *MyStack) Pop() int {
    res := this.q1[0]
    this.q1 = this.q1[1:]
    if len(this.q1) > 0 {
        this.topElement = this.q1[0]
    }
    return res
}

func (this *MyStack) Top() int {
    return this.topElement
}

func (this *MyStack) Empty() bool {
    return len(this.q1) == 0
}

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

#easy
Задача: 226. Invert Binary Tree

Дан корень бинарного дерева, инвертируйте дерево и верните его корень.

Пример:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

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

1⃣Рекурсивная инверсия поддеревьев:
Если текущий узел (root) пустой, возвращаем null.
Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right.
Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left.

2⃣Обмен поддеревьев:
Устанавливаем левое поддерево текущего узла равным правому поддереву.
Устанавливаем правое поддерево текущего узла равным левому поддереву.

3⃣Возврат корня:
Возвращаем текущий узел (root) как новый корень инвертированного дерева.

😎 Решение:

package main

import "fmt"

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

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    right := invertTree(root.Right)
    left := invertTree(root.Left)
    root.Left = right
    root.Right = left
    return root
}

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

#easy
Задача: 278. First Bad Version

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

Предположим, у вас есть 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
}

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

#medium
Задача: 279. Perfect Squares

Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.

Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

import (
    "math"
    "fmt"
)

func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0
    
    maxSquareIndex := int(math.Sqrt(float64(n))) + 1
    squareNums := make([]int, maxSquareIndex)
    for i := 1; i < maxSquareIndex; i++ {
        squareNums[i] = i * i
    }
    
    for i := 1; i <= n; i++ {
        for s := 1; s < maxSquareIndex; s++ {
            if i < squareNums[s] {
                break
            }
            dp[i] = min(dp[i], dp[i-squareNums[s]]+1)
        }
    }
    
    return dp[n]
}

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

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

#medium
Задача: 382. Linked List Random Node

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

Реализуйте класс Solution:

Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

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

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type ListNode struct {
  Val  int
  Next *ListNode
}

type Solution struct {
  rangeVals []int
}

func Constructor(head *ListNode) Solution {
  var rangeVals []int
  for head != nil {
    rangeVals = append(rangeVals, head.Val)
    head = head.Next
  }
  rand.Seed(time.Now().UnixNano())
  return Solution{rangeVals: rangeVals}
}

func (this *Solution) GetRandom() int {
  pick := rand.Intn(len(this.rangeVals))
  return this.rangeVals[pick]
}

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

#easy
Задача: 383. Ransom Note

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

Каждая буква из magazine может быть использована в ransomNote только один раз.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления".

2⃣По этой причине необходимо заменять строку magazine новой строкой, в которой отсутствует символ, который мы хотели удалить.

3⃣Повторяйте этот процесс, пока не будут удалены все необходимые символы.

😎 Решение:

package main

import (
  "strings"
)

func canConstruct(ransomNote string, magazine string) bool {
  for _, char := range ransomNote {
    index := strings.IndexRune(magazine, char)
    if index == -1 {
      return false
    }
    magazine = magazine[:index] + magazine[index+1:]
  }
  return true
}

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

#medium
Задача: 384. Shuffle an Array

Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.

Реализуйте класс Solution:

Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.

2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.

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

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type Solution struct {
  array    []int
  original []int
}

func Constructor(nums []int) Solution {
  original := make([]int, len(nums))
  copy(original, nums)
  return Solution{array: nums, original: original}
}

func (this *Solution) Reset() []int {
  copy(this.array, this.original)
  return this.original
}

func (this *Solution) Shuffle() []int {
  rand.Seed(time.Now().UnixNano())
  for i := range this.array {
    randIndex := rand.Intn(len(this.array)-i) + i
    this.array[i], this.array[randIndex] = this.array[randIndex], this.array[i]
  }
  return this.array
}

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

#medium
Задача: 368. Largest Divisible Subset

Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию:

answer[i] % answer[j] == 0, или
answer[j] % answer[i] == 0
Если существует несколько решений, вернуть любое из них.

Пример:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

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

1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4).

2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8).

3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}.

😎 Решение:

package main

import (
  "fmt"
  "sort"
)

func largestDivisibleSubset(nums []int) []int {
  n := len(nums)
  if n == 0 {
    return []int{}
  }

  sort.Ints(nums)
  EDS := make([][]int, n)

  for i := 0; i < n; i++ {
    maxSubset := []int{}
    for k := 0; k < i; k++ {
      if nums[i]%nums[k] == 0 && len(maxSubset) < len(EDS[k]) {
        maxSubset = EDS[k]
      }
    }
    EDS[i] = append([]int{}, maxSubset...)
    EDS[i] = append(EDS[i], nums[i])
  }

  ret := []int{}
  for _, subset := range EDS {
    if len(ret) < len(subset) {
      ret = subset
    }
  }
  return ret
}

func main() {
  nums := []int{1, 2, 4, 8}
  fmt.Println(largestDivisibleSubset(nums))
}

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

#easy
Задача: 387. First Unique Character in a String

Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1.

Пример:

Input: s = "leetcode"
Output: 0

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

1⃣Постройте хеш-таблицу, где ключами являются символы строки, а значениями — количество их появлений. Для этого пройдите по строке и для каждого символа увеличивайте его счетчик в хеш-таблице.

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

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

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type Solution struct {
  original []int
  array    []int
}

func Constructor(nums []int) Solution {
  original := make([]int, len(nums))
  copy(original, nums)
  return Solution{
    original: original,
    array:    append([]int(nil), nums...),
  }
}

func (this *Solution) Reset() []int {
  this.array = append([]int(nil), this.original...)
  return this.original
}

func (this *Solution) Shuffle() []int {
  rand.Seed(time.Now().UnixNano())
  for i := range this.array {
    randIndex := rand.Intn(len(this.array)-i) + i
    this.array[i], this.array[randIndex] = this.array[randIndex], this.array[i]
  }
  return this.array
}

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

#hard
Задача: 369. Plus One Linked List

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

Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

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

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

1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.

2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).

😎 Решение:

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func plusOne(head *ListNode) *ListNode {
    sentinel := &ListNode{0, head}
    notNine := sentinel

    current := head
    for current != nil {
        if current.Val != 9 {
            notNine = current
        }
        current = current.Next
    }

    notNine.Val += 1
    notNine = notNine.Next

    for notNine != nil {
        notNine.Val = 0
        notNine = notNine.Next
    }

    if sentinel.Val == 0 {
        return sentinel.Next
    } else {
        return sentinel
    }
}

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

#easy
Задача: 389. Find the Difference

Даны две строки s и t.

Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.

Верните букву, которая была добавлена в t.

Пример:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

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

1⃣Отсортируйте строки s и t.

2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s.

3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время.

😎 Решение:

package main

import (
    "sort"
    "strings"
)

func findTheDifference(s string, t string) byte {
    sortedS := strings.Split(s, "")
    sortedT := strings.Split(t, "")
    sort.Strings(sortedS)
    sort.Strings(sortedT)

    for i := 0; i < len(sortedS); i++ {
        if sortedS[i] != sortedT[i] {
            return sortedT[i][0]
        }
    }

    return sortedT[len(sortedS)][0]
}

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

#easy
Задача: 392. Is Subsequence

Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.

Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).

Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

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

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

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

😎 Решение:

package main

import "fmt"

func isSubsequence(s string, t string) bool {
    leftBound, rightBound := len(s), len(t)
    pLeft, pRight := 0, 0

    for pLeft < leftBound && pRight < rightBound {
        if s[pLeft] == t[pRight] {
            pLeft++
        }
        pRight++
    }
    return pLeft == leftBound
}

func main() {
    s := "abc"
    t := "ahbgdc"
    fmt.Println(isSubsequence(s, t)) // Output: true

    s = "axc"
    t = "ahbgdc"
    fmt.Println(isSubsequence(s, t)) // Output: false
}

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

#medium
Задача: 393. UTF-8 Validation

Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов).

Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила:

Для 1-байтового символа первый бит — 0, за которым следует его Unicode код.
Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10.
Это работает следующим образом:

     Количество байтов  |        UTF-8 Октетная последовательность
                       |              (бинарная)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x обозначает бит в бинарной форме байта, который может быть как 0, так и 1.

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

Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

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

1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep.

2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа.

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

Теперь давайте перейдем к реализации этого алгоритма.

😎 Решение:

package main

import (
    "fmt"
)

func validUtf8(data []int) bool {
    nBytes := 0
    for _, num := range data {
        binRep := fmt.Sprintf("%08b", num)[-8:]
        if nBytes == 0 {
            for _, bit := range binRep {
                if bit == '0' {
                    break
                }
                nBytes++
            }
            if nBytes == 0 {
                continue
            }
            if nBytes == 1 || nBytes > 4 {
                return false
            }
        } else {
            if !(binRep[0] == '1' && binRep[1] == '0') {
                return false
            }
        }
        nBytes--
    }
    return nBytes == 0
}

func main() {
    data1 := []int{197, 130, 1}
    data2 := []int{235, 140, 4}
    fmt.Println(validUtf8(data1)) // true
    fmt.Println(validUtf8(data2)) // false
}

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

#medium
Задача: 394. Decode String

Дана закодированная строка, вернуть её декодированную версию.

Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.

Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4].

Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105.

Пример:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

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

1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек.

2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k.

3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его.

😎 Решение:

package main

import (
    "fmt"
    "unicode"
)

func decodeString(s string) string {
    stack := []rune{}
    for _, char := range s {
        if char == ']' {
            decodedString := ""
            for stack[len(stack)-1] != '[' {
                decodedString = string(stack[len(stack)-1]) + decodedString
                stack = stack[:len(stack)-1]
            }
            stack = stack[:len(stack)-1]
            base := 1
            k := 0
            for len(stack) > 0 && unicode.IsDigit(stack[len(stack)-1]) {
                k = k + int(stack[len(stack)-1]-'0')*base
                stack = stack[:len(stack)-1]
                base *= 10
            }
            for k > 0 {
                for j := 0; j < len(decodedString); j++ {
                    stack = append(stack, rune(decodedString[j]))
                }
                k--
            }
        } else {
            stack = append(stack, char)
        }
    }
    return string(stack)
}

func main() {
    fmt.Println(decodeString("3[a2[c]]")) // Output: "accaccacc"
}

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

#medium
Задача: 280. Wiggle Sort

Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....

Вы можете считать, что входной массив всегда имеет допустимый ответ.

Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

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

1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена.

2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

😎 Решение:

func swap(nums []int, i, j int) {
    nums[i], nums[j] = nums[j], nums[i]
}

func wiggleSort(nums []int) {
    for i := 0; i < len(nums)-1; i++ {
        if (i%2 == 0 && nums[i] > nums[i+1]) || (i%2 == 1 && nums[i] < nums[i+1]) {
            swap(nums, i, i+1)
        }
    }
}

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

#hard
Задача: 301. Remove Invalid Parentheses

Дана строка s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой.

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

Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

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

1⃣Инициализация:
Инициализируйте массив, который будет хранить все допустимые выражения.
Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо.
Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно.

2⃣Обработка текущего символа:
Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии.
Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения.

3⃣Завершение рекурсии и проверка:
Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны).
Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор.
Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений.

😎 Решение:

package main

import (
  "fmt"
)

type Solution struct {
  validExpressions map[string]bool
  minimumRemoved   int
}

func (sol *Solution) reset() {
  sol.validExpressions = make(map[string]bool)
  sol.minimumRemoved = int(^uint(0) >> 1) // Max int value
}

func (sol *Solution) recurse(s string, index, leftCount, rightCount, removedCount int, expression []rune) {
  if index == len(s) {
    if leftCount == rightCount {
      if removedCount <= sol.minimumRemoved {
        possibleAnswer := string(expression)
        if removedCount < sol.minimumRemoved {
          sol.validExpressions = make(map[string]bool)
          sol.minimumRemoved = removedCount
        }
        sol.validExpressions[possibleAnswer] = true
      }
    }
    return
  }

  currentCharacter := rune(s[index])
  length := len(expression)

  if currentCharacter != '(' && currentCharacter != ')' {
    sol.recurse(s, index+1, leftCount, rightCount, removedCount, append(expression, currentCharacter))
  } else {
    sol.recurse(s, index+1, leftCount, rightCount, removedCount+1, expression)

    expression = append(expression, currentCharacter)

    if currentCharacter == '(' {
      sol.recurse(s, index+1, leftCount+1, rightCount, removedCount, expression)
    } else if rightCount < leftCount {
      sol.recurse(s, index+1, leftCount, rightCount+1, removedCount, expression)
    }

    expression = expression[:length]
  }
}

func (sol *Solution) RemoveInvalidParentheses(s string) []string {
  sol.reset()
  sol.recurse(s, 0, 0, 0, 0, []rune{})
  results := []string{}
  for expr := range sol.validExpressions {
    results = append(results, expr)
  }
  return results
}

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