#hard
Задача: 282. Expression Add Operators

Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.

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

Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

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

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

2⃣Рекурсивная генерация выражений:
В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения.
Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение.

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

😎 Решение:

import (
  "strconv"
)

type Solution struct {
  answer []string
  digits string
  target int64
}

func (s *Solution) recurse(index int, previousOperand, currentOperand, value int64, ops []string) {
  if index == len(s.digits) {
    if value == s.target && currentOperand == 0 {
      expression := ""
      for i := 1; i < len(ops); i++ {
        expression += ops[i]
      }
      s.answer = append(s.answer, expression)
    }
    return
  }

  currentOperand = currentOperand*10 + int64(s.digits[index]-'0')
  currentValRep := strconv.FormatInt(currentOperand, 10)

  if currentOperand > 0 {
    s.recurse(index+1, previousOperand, currentOperand, value, ops)
  }

  ops = append(ops, "+", currentValRep)
  s.recurse(index+1, currentOperand, 0, value+currentOperand, ops)
  ops = ops[:len(ops)-2]

  if len(ops) > 0 {
    ops = append(ops, "-", currentValRep)
    s.recurse(index+1, -currentOperand, 0, value-currentOperand, ops)
    ops = ops[:len(ops)-2]

    ops = append(ops, "*", currentValRep)
    s.recurse(index+1, currentOperand*previousOperand, 0, value-previousOperand+(currentOperand*previousOperand), ops)
    ops = ops[:len(ops)-2]
  }
}

func (s *Solution) addOperators(num string, target int) []string {
  if len(num) == 0 {
    return []string{}
  }

  s.target = int64(target)
  s.digits = num
  s.answer = []string{}
  s.recurse(0, 0, 0, 0, []string{})
  return s.answer
}

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

#easy
Задача: 283. Move Zeroes

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

Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.

Пример:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

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

1⃣Инициализация указателей:
Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву.

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

3⃣Завершение итерации:
Повторяйте шаг 2 до конца массива. В итоге все нули будут перемещены в конец массива, сохраняя относительный порядок ненулевых элементов.

😎 Решение:

func moveZeroes(nums []int) {
    lastNonZeroFoundAt := 0
    for cur := 0; cur < len(nums); cur++ {
        if nums[cur] != 0 {
            nums[lastNonZeroFoundAt], nums[cur] = nums[cur], nums[lastNonZeroFoundAt]
            lastNonZeroFoundAt++
        }
    }
}

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

#medium
Задача: 284. Peeking Iterator

Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента).

Реализуйте класс PeekingIterator:
PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел.
int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент.
boolean hasNext(): Возвращает true, если в массиве еще есть элементы.
int peek(): Возвращает следующий элемент в массиве без перемещения указателя.

Пример:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

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

1⃣Инициализация итератора:
В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null.

2⃣Операция peek:
Метод peek возвращает значение next, не перемещая указатель итератора.

3⃣Операции next и hasNext:
Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException.
Метод hasNext возвращает true, если next не равно null, и false в противном случае.

😎 Решение:

type PeekingIterator struct {
    iterator  Iterator
    nextElem  *int
}

func Constructor(iter Iterator) *PeekingIterator {
    var next *int
    if iter.HasNext() {
        val := iter.Next()
        next = &val
    }
    return &PeekingIterator{iterator: iter, nextElem: next}
}

func (this *PeekingIterator) hasNext() bool {
    return this.nextElem != nil
}

func (this *PeekingIterator) next() int {
    current := *this.nextElem
    if this.iterator.HasNext() {
        val := this.iterator.Next()
        this.nextElem = &val
    } else {
        this.nextElem = nil
    }
    return current
}

func (this *PeekingIterator) peek() int {
    return *this.nextElem
}

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

#medium
Задача: 285. Inorder Successor in BST

Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.

Преемник узла p — это узел с наименьшим ключом, который больше p.val.

Пример:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

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

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

2⃣Обработка двух случаев:
В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента.
Правый дочерний элемент существует:
- присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве.
Правый дочерний элемент не существует:
- определите функцию inorderCase2 и передайте ей узел и узел p.
- выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла.
- когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции.
- наконец, верните inorderSuccessorNode как результат.

3⃣Итерация и обновление:
В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент.

😎 Решение:

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

type Solution struct {
    previous              *TreeNode
    inorderSuccessorNode  *TreeNode
}

func (s *Solution) inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
    if p.Right != nil {
        leftmost := p.Right
        for leftmost.Left != nil {
            leftmost = leftmost.Left
        }
        s.inorderSuccessorNode = leftmost
    } else {
        s.inorderCase2(root, p)
    }
    return s.inorderSuccessorNode
}

func (s *Solution) inorderCase2(node *TreeNode, p *TreeNode) {
    if node == nil {
        return
    }

    s.inorderCase2(node.Left, p)

    if s.previous == p && s.inorderSuccessorNode == nil {
        s.inorderSuccessorNode = node
        return
    }

    s.previous = node

    s.inorderCase2(node.Right, p)
}

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

#medium
Задача: 286. Walls and Gates

Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями:
-1: Стена или препятствие.
0: Ворота.
INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 = 2147483647 для представления INF, так как можно предположить, что расстояние до ворот меньше 2147483647.
Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF.

Пример:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

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

1⃣Обход всех комнат:
Пройдите через каждую клетку сетки, инициализируя очередь для BFS. Если клетка содержит ворота (0), добавьте её в очередь.

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

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

😎 Решение:

package main

import "container/list"

func wallsAndGates(rooms [][]int) {
    if len(rooms) == 0 {
        return
    }

    m, n := len(rooms), len(rooms[0])
    q := list.New()
    INF := 2147483647
    directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if rooms[i][j] == 0 {
                q.PushBack([2]int{i, j})
            }
        }
    }

    for q.Len() > 0 {
        front := q.Front()
        q.Remove(front)
        x, y := front.Value.([2]int)[0], front.Value.([2]int)[1]
        for _, dir := range directions {
            nx, ny := x+dir[0], y+dir[1]
            if nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF {
                rooms[nx][ny] = rooms[x][y] + 1
                q.PushBack([2]int{nx, ny})
            }
        }
    }
}

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

#medium
Задача: 287. Find the Duplicate Number

Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.

Пример:

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

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

1⃣Определение дубликата:
Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс.
Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла.
Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу.

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

3⃣Возврат результата:
Верните найденный дубликат.

😎 Решение:

func findDuplicate(nums []int) int {
    duplicate := -1
    for i := 0; i < len(nums); i++ {
        cur := abs(nums[i])
        if nums[cur] < 0 {
            duplicate = cur
            break
        }
        nums[cur] *= -1
    }
    for i := 0; i < len(nums); i++ {
        nums[i] = abs(nums[i])
    }
    return duplicate
}

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

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

#medium
Задача: 288. Unique Word Abbreviation

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

Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:

ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.

Пример:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

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

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

2⃣Генерация сокращений:
При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение.
Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное).

3⃣Проверка уникальности:
Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict.
Если сокращение отсутствует в abbrDict, возвращайте true.
Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false.

😎 Решение:

type ValidWordAbbr struct {
    abbrDict map[string]bool
    dict     map[string]struct{}
}

func Constructor(dictionary []string) ValidWordAbbr {
    abbrDict := make(map[string]bool)
    dict := make(map[string]struct{})
    for _, word := range dictionary {
        dict[word] = struct{}{}
        abbr := toAbbr(word)
        abbrDict[abbr] = !abbrDict[abbr]
    }
    return ValidWordAbbr{abbrDict: abbrDict, dict: dict}
}

func (this *ValidWordAbbr) IsUnique(word string) bool {
    abbr := toAbbr(word)
    _, hasAbbr := this.abbrDict[abbr]
    _, inDict := this.dict[word]
    return !hasAbbr || (this.abbrDict[abbr] && inDict)
}

func toAbbr(word string) string {
    n := len(word)
    if n <= 2 {
        return word
    }
    return fmt.Sprintf("%c%d%c", word[0], n-2, word[n-1])
}

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

#easy
Задача: 459. Repeated Substring Pattern

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

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

1⃣Создайте целочисленную переменную n, равную длине строки s.

2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2:
Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s.
Если pattern равен s, вернуть true.

3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false.

😎 Решение:

package main

import "strings"

func repeatedSubstringPattern(s string) bool {
    n := len(s)
    for i := 1; i <= n/2; i++ {
        if n%i == 0 {
            pattern := strings.Repeat(s[:i], n/i)
            if s == pattern {
                return true
            }
        }
    }
    return false
}

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

#medium
Задача: 289. Game of Life

Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году."

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

Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения.
Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения.
Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения.
Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения.
Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние.

Пример:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

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

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

2⃣Применение правил:
На основе количества живых соседей и текущего состояния клетки примените правила игры:
Любая живая клетка с менее чем двумя живыми соседями умирает (становится -1).
Любая живая клетка с двумя или тремя живыми соседями остаётся живой (без изменений).
Любая живая клетка с более чем тремя живыми соседями умирает (становится -1).
Любая мёртвая клетка с ровно тремя живыми соседями становится живой (становится 2).

3⃣Обновление доски:
Пройдите через доску ещё раз и обновите состояния клеток:
Если значение клетки больше 0, установите её в 1 (живая).
Если значение клетки меньше или равно 0, установите её в 0 (мёртвая).

😎 Решение:

func gameOfLife(board [][]int) {
    neighbors := []int{0, 1, -1}
    rows := len(board)
    cols := len(board[0])

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            liveNeighbors := 0

            for _, i := range neighbors {
                for _, j := range neighbors {
                    if !(i == 0 && j == 0) {
                        r := row + i
                        c := col + j

                        if r >= 0 && r < rows && c >= 0 && c < cols && abs(board[r][c]) == 1 {
                            liveNeighbors++
                        }
                    }
                }
            }

            if board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3) {
                board[row][col] = -1
            }
            if board[row][col] == 0 && liveNeighbors == 3 {
                board[row][col] = 2
            }
        }
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if board[row][col] > 0 {
                board[row][col] = 1
            } else {
                board[row][col] = 0
            }
        }
    }
}

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

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

#medium
Задача: 328. Odd Even Linked List

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

Первый узел считается нечетным, второй узел — четным и так далее.

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

Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n).

Пример:

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

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

1⃣Инициализация указателей:
Создайте указатели odd и even для работы с нечетными и четными узлами, соответственно. Инициализируйте odd началом списка head, а even — следующим узлом head.next. Также создайте указатель evenHead для сохранения начала четного списка.

2⃣Разделение списка:
Используйте цикл для прохождения списка, перенаправляя нечетные узлы в oddList, а четные узлы в evenList. Обновляйте указатели odd и even в процессе итерации.

3⃣Соединение списков:

После окончания цикла соедините конец нечетного списка с началом четного списка, используя указатель evenHead.

😎 Решение:

type ListNode struct {
    Val  int
    Next *ListNode
}

func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    odd := head
    even := head.Next
    evenHead := even
    
    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next
        even.Next = odd.Next
        even = even.Next
    }
    odd.Next = evenHead
    return head
}

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

#medium
Задача: 473. Matchsticks to Square

Дано целочисленный массив спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.

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

Пример:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

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

1⃣Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True.

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

3⃣Если какой-либо из рекурсивных вызовов возвращает True, возвращаем True, в противном случае возвращаем False.

😎 Решение:

package main

import (
    "sort"
)

type Solution struct {
    nums              []int
    sums              []int
    possibleSquareSide int
}

func Constructor() Solution {
    return Solution{sums: make([]int, 4)}
}

func (this *Solution) dfs(index int) bool {
    if index == len(this.nums) {
        return this.sums[0] == this.sums[1] && this.sums[1] == this.sums[2] && this.sums[2] == this.sums[3]
    }

    element := this.nums[index]

    for i := 0; i < 4; i++ {
        if this.sums[i]+element <= this.possibleSquareSide {
            this.sums[i] += element
            if this.dfs(index + 1) {
                return true
            }
            this.sums[i] -= element
        }
    }

    return false
}

func (this *Solution) makesquare(nums []int) bool {
    if len(nums) == 0 {
        return false
    }

    perimeter := 0
    for _, num := range nums {
        perimeter += num
    }

    this.possibleSquareSide = perimeter / 4
    if this.possibleSquareSide*4 != perimeter {
        return false
    }

    this.nums = nums
    sort.Sort(sort.Reverse(sort.IntSlice(this.nums)))
    return this.dfs(0)
}

func main() {}

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

#medium
Задача: 227. Basic Calculator II

Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение.

Целочисленное деление должно округляться к нулю.

Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].

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

Пример:

Input: s = "3+2*2"
Output: 7

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

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

2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации.

3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки.

😎 Решение:

package main

import (
    "strconv"
    "unicode"
)

func calculate(s string) int {
    length := len(s)
    if length == 0 {
        return 0
    }
    currentNumber, lastNumber, result := 0, 0, 0
    sign := '+'
    
    for i := 0; i < length; i++ {
        currentChar := rune(s[i])
        if unicode.IsDigit(currentChar) {
            num, _ := strconv.Atoi(string(currentChar))
            currentNumber = (currentNumber * 10) + num
        }
        if !unicode.IsDigit(currentChar) && !unicode.IsSpace(currentChar) || i == length-1 {
            if sign == '+' || sign == '-' {
                result += lastNumber
                lastNumber = currentNumber
                if sign == '-' {
                    lastNumber = -currentNumber
                }
            } else if sign == '*' {
                lastNumber *= currentNumber
            } else if sign == '/' {
                lastNumber /= currentNumber
            }
            sign = currentChar
            currentNumber = 0
        }
    }
    result += lastNumber
    return result
}

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

#easy
Задача: 228. Summary Ranges

Вам дан отсортированный массив уникальных целых чисел nums.

Диапазон [a,b] - это множество всех целых чисел от a до b (включительно).

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

Каждый диапазон [a,b] в списке должен быть представлен в формате:

"a->b" если a != b
"a" если a == b

Пример:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

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

1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i].

2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики.

3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон.

😎 Решение:

package main

import (
    "fmt"
    "strconv"
)

func summaryRanges(nums []int) []string {
    ranges := []string{}
    i := 0
    for i < len(nums) {
        start := nums[i]
        for i+1 < len(nums) && nums[i]+1 == nums[i+1] {
            i++
        }
        if start != nums[i] {
            ranges = append(ranges, strconv.Itoa(start)+"->"+strconv.Itoa(nums[i]))
        } else {
            ranges = append(ranges, strconv.Itoa(start))
        }
        i++
    }
    return ranges
}

func main() {
    nums := []int{0, 1, 2, 4, 5, 7}
    fmt.Println(summaryRanges(nums))
}

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

#medium
Задача: 474. Ones and Zeroes

Дан массив двоичных строк strs и два целых числа m и n.

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

Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.

Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

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

1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.

2⃣Считаем количество нулей и единиц в каждом подмножестве.

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

😎 Решение:

package main

import (
    "fmt"
)

type Solution struct{}

func (s *Solution) findMaxForm(strs []string, m int, n int) int {
    maxlen := 0
    for i := 0; i < (1 << len(strs)); i++ {
        zeroes, ones, length := 0, 0, 0
        for j := 0; j < 32; j++ {
            if (i & (1 << j)) != 0 {
                count := s.countZeroesOnes(strs[j])
                zeroes += count[0]
                ones += count[1]
                if zeroes > m || ones > n {
                    break
                }
                length++
            }
        }
        if zeroes <= m && ones <= n {
            maxlen = max(maxlen, length)
        }
    }
    return maxlen
}

func (s *Solution) countZeroesOnes(str string) [2]int {
    count := [2]int{}
    for _, char := range str {
        count[char-'0']++
    }
    return count
}

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

func main() {
    sol := Solution{}
    fmt.Println(sol.findMaxForm([]string{"10", "0001", "111001", "1", "0"}, 5, 3))
}

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

#medium
Задача: 229. Majority Element II

Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.

Пример:

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

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

1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика.

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

3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат.

😎 Решение:

package main

func majorityElement(nums []int) []int {
    count1, count2 := 0, 0
    var candidate1, candidate2 *int
    
    for _, n := range nums {
        if candidate1 != nil && *candidate1 == n {
            count1++
        } else if candidate2 != nil && *candidate2 == n {
            count2++
        } else if count1 == 0 {
            candidate1 = &n
            count1 = 1
        } else if count2 == 0 {
            candidate2 = &n

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

#hard
Задача: 329. Longest Increasing Path in a Matrix

Дана матрица целых чисел размером m x n. Верните длину самого длинного возрастающего пути в матрице.
Из каждой ячейки можно перемещаться в четырех направлениях: влево, вправо, вверх или вниз. Перемещение по диагонали или выход за границы матрицы (т.е. замкнутые переходы) не допускается.

Пример:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

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

1⃣Инициализация и создание матрицы:
Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке.
Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree.

2⃣Поиск начальных листьев:
Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления".

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

😎 Решение:

var dir = [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

func longestIncreasingPath(matrix [][]int) int {
    m := len(matrix)
    if m == 0 {
        return 0
    }
    n := len(matrix[0])
    outdegree := make([][]int, m+2)
    newMatrix := make([][]int, m+2)
    for i := range outdegree {
        outdegree[i] = make([]int, n+2)
        newMatrix[i] = make([]int, n+2)
    }

    for i := 0; i < m; i++ {
        copy(newMatrix[i+1][1:], matrix[i])
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            for _, d := range dir {
                if newMatrix[i][j] < newMatrix[i+d[0]][j+d[1]] {
                    outdegree[i][j]++
                }
            }
        }
    }

    var leaves [][]int
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if outdegree[i][j] == 0 {
                leaves = append(leaves, []int{i, j})
            }
        }
    }

    height := 0
    for len(leaves) > 0 {
        height++
        var newLeaves [][]int
        for _, node := range leaves {
            for _, d := range dir {
                x, y := node[0]+d[0], node[1]+d[1]
                if newMatrix[node[0]][node[1]] > newMatrix[x][y] {
                    outdegree[x][y]--
                    if outdegree[x][y] == 0 {
                        newLeaves = append(newLeaves, []int{x, y})
                    }
                }
            }
        }
        leaves = newLeaves
    }

    return height
}

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

#medium
Задача: 230. Kth Smallest Element in a BST

Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.

Пример:

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

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

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

2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение.

3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение.

😎 Решение:

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    
    for {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        k--
        if k == 0 {
            return root.Val
        }
        root = root.Right
    }
}

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

#easy
Задача: 231. Power of Two

Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.

Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.

Пример:

Input: n = 1
Output: true
Explanation: 2^0 = 1

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

1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки.

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

3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x.

😎 Решение:

func isPowerOfTwo(n int) bool {
    if n == 0 {
        return false
    }
    x := int64(n)
    return (x & -x) == x
}

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

#easy
Задача: 232. Implement Queue using Stacks

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

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

void push(int x) добавляет элемент x в конец очереди.
int pop() удаляет элемент из начала очереди и возвращает его.
int peek() возвращает элемент из начала очереди.
boolean empty() возвращает true, если очередь пуста, и false в противном случае.

Пример:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

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

1⃣Добавление элемента: Для метода push(int x) переместите все элементы из стека s1 в стек s2. Добавьте элемент x в стек s2. Затем переместите все элементы обратно из стека s2 в стек s1. Если стек s1 пуст, обновите переменную front значением x.

2⃣Удаление и проверка первого элемента: Для метода pop() удалите элемент из начала очереди, извлекая верхний элемент из стека s1. Обновите переменную front на новый верхний элемент стека s1, если он не пуст. Для метода peek() верните значение переменной front, так как она всегда хранит первый элемент очереди.

3⃣Проверка на пустоту: Для метода empty() верните результат проверки, является ли стек s1 пустым.

😎 Решение:

type MyQueue struct {
    s1, s2 []int
    front  int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (this *MyQueue) Push(x int) {
    if len(this.s1) == 0 {
        this.front = x
    }
    for len(this.s1) > 0 {
        this.s2 = append(this.s2, this.s1[len(this.s1)-1])
        this.s1 = this.s1[:len(this.s1)-1]
    }
    this.s2 = append(this.s2, x)
    for len(this.s2) > 0 {
        this.s1 = append(this.s1, this.s2[len(this.s2)-1])
        this.s2 = this.s2[:len(this.s2)-1]
    }
}

func (this *MyQueue) Pop() int {
    res := this.s1[len(this.s1)-1]
    this.s1 = this.s1[:len(this.s1)-1]
    if len(this.s1) > 0 {
        this.front = this.s1[len(this.s1)-1]
    }
    return res
}

func (this *MyQueue) Empty() bool {
    return len(this.s1) == 0
}

func (this *MyQueue) Peek() int {
    return this.front
}

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

#easy
Задача: 476. Number Complement

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.

Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

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

1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1.

3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask.

😎 Решение:

package main

func findComplement(num int) int {
    bitmask := num
    bitmask |= (bitmask >> 1)
    bitmask |= (bitmask >> 2)
    bitmask |= (bitmask >> 4)
    bitmask |= (bitmask >> 8)
    bitmask |= (bitmask >> 16)
    return bitmask ^ num
}

func main() {}

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

#hard
Задача: 233. Number of Digit One

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

Пример:

Input: n = 13
Output: 6

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

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

func countDigitOne(n int) int {
    countr := 0
    for i := int64(1); i <= int64(n); i *= 10 {
        divider := i * 10
        countr += int(int64(n)/divider)*int(i) + int(min(max(int64(n)%divider-i+1, 0), i))
    }
    return countr
}

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

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

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