Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

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

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

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

package main

import (
    "math"
    "strconv"
)

func countPrimeSetBits(left int, right int) int {
    count := 0
    for num := left; num <= right; num++ {
        if isPrime(bitCount(num)) {
            count++
        }
    }
    return count
}

func bitCount(x int) int {
    return strconv.FormatInt(int64(x), 2)
}

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    for i := 2; i <= int(math.Sqrt(float64(x))); i++ {
        if x % i == 0 {
            return false
        }
    }
    return true
}

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

Задача: №25. Reverse Nodes in k-Group
Сложность: hard

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

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

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

2⃣Использовать итеративный метод для переворота узлов в каждой группе k.

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

😎 Решение:

func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || k == 1 {
        return head
    }

    dummy := &ListNode{Next: head}
    prev, curr := dummy, head

    count := 0
    for curr != nil {
        count++
        curr = curr.Next
    }

    for count >= k {
        curr = prev.Next
        next := curr.Next

        for i := 1; i < k; i++ {
            curr.Next = next.Next
            next.Next = prev.Next
            prev.Next = next
            next = curr.Next
        }

        prev = curr
        count -= k
    }

    return dummy.Next
}

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

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

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

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

😎 Решение:

func longestMountain(arr []int) int {
    n := len(arr)
    ans := 0
    base := 0

    for base < n {
        end := base
        if end+1 < n && arr[end] < arr[end+1] {
            for end+1 < n && arr[end] < arr[end+1] {
                end++
            }
            if end+1 < n && arr[end] > arr[end+1] {
                for end+1 < n && arr[end] > arr[end+1] {
                    end++
                }
                ans = max(ans, end-base+1)
            }
        }
        base = max(end, base+1)
    }

    return ans
}

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

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

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

Вам дана бинарная матрица grid размером m x n.

Ход состоит из выбора любой строки или столбца и переключения каждого значения в этой строке или столбце (т.е. изменение всех 0 на 1, и всех 1 на 0).

Каждая строка матрицы интерпретируется как двоичное число, и счёт матрицы — это сумма этих чисел.

Верните наивысший возможный счёт после выполнения любого количества ходов (включая ноль ходов).

Пример:

Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

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

1⃣Инициализируйте переменные: m и n для количества строк и столбцов в grid, score для хранения максимального счёта матрицы. Пройдитесь по первому столбцу матрицы. Если элемент равен 0, переверните всю строку.

2⃣Пройдитесь по матрице от второго до последнего столбца. Для каждого столбца посчитайте количество нулей (countZero). Если количество нулей больше, переверните весь столбец.

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

😎 Решение:

func matrixScore(grid [][]int) int {
    m, n := len(grid), len(grid[0])

    for i := 0; i < m; i++ {
        if grid[i][0] == 0 {
            for j := 0; j < n; j++ {
                grid[i][j] ^= 1
            }
        }
    }

    for j := 1; j < n; j++ {
        countZero := 0
        for i := 0; i < m; i++ {
            if grid[i][j] == 0 {
                countZero++
            }
        }
        if countZero > m/2 {
            for i := 0; i < m; i++ {
                grid[i][j] ^= 1
            }
        }
    }

    score := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                score += 1 << (n - j - 1)
            }
        }
    }

    return score
}

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

Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.

Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.

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

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

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

😎 Решение:

package main

import (
    "strings"
)

type Solution struct{}

func (s Solution) dfs(word string, length int, visited []bool, dictionary map[string]bool) bool {
    if length == len(word) {
        return true
    }
    if visited[length] {
        return false
    }
    visited[length] = true
    for i := len(word) - 1; i > length; i-- {
        if dictionary[word[length:i]] && s.dfs(word, i, visited, dictionary) {
            return true
        }
    }
    return false
}

func (s Solution) findAllConcatenatedWordsInADict(words []string) []string {
    dictionary := make(map[string]bool)
    for _, word := range words {
        dictionary[word] = true
    }
    var answer []string
    for _, word := range words {
        visited := make([]bool, len(word))
        if s.dfs(word, 0, visited, dictionary) {
            answer = append(answer, word)
        }
    }
    return answer
}

func main() {
    solution := Solution{}
    words := []string{"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"}
    result := solution.findAllConcatenatedWordsInADict(words)
    for _, word := range result {
        println(word)
    }
}

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

Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:
Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

1⃣Создайте функцию для вычисления оценки слова.

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

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

😎 Решение:

func maxScoreWords(words []string, letters []byte, score []int) int {
    letterCount := make(map[byte]int)
    for _, ch := range letters {
        letterCount[ch]++
    }

    wordScore := func(word string) int {
        total := 0
        for i := 0; i < len(word); i++ {
            total += score[word[i] - 'a']
        }
        return total
    }

    canFormWord := func(word string, letterCount map[byte]int) bool {
        count := make(map[byte]int)
        for i := 0; i < len(word); i++ {
            count[word[i]]++
            if count[word[i]] > letterCount[word[i]] {
                return false
            }
        }
        return true
    }

    maxScore := 0
    n := len(words)
    for i := 1; i < (1 << n); i++ {
        currScore := 0
        usedLetters := make(map[byte]int)
        valid := true
        for j := 0; j < n; j++ {
            if i & (1 << j) != 0 {
                word := words[j]
                if canFormWord(word, letterCount) {
                    currScore += wordScore(word)
                    for k := 0; k < len(word); k++ {
                        usedLetters[word[k]]++
                    }
                } else {
                    valid = false
                    break
                }
            }
        }
        if valid {
            if currScore > maxScore {
                maxScore = currScore
            }
        }
    }

    return maxScore
}

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

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

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

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

3⃣Просуммировать все значения площадей для получения итоговой площади поверхности.

😎 Решение:

func surfaceArea(grid [][]int) int {
    n := len(grid)
    area := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] > 0 {
                area += (grid[i][j] * 4) + 2
            }
            if i > 0 {
                area -= min(grid[i][j], grid[i-1][j]) * 2
            }
            if j > 0 {
                area -= min(grid[i][j], grid[i][j-1]) * 2
            }
        }
    }
    return area
}

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

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

Задача: 370. Range Addition
Сложность: medium

Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].

У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.

Верните arr после применения всех обновлений.

Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

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

1⃣Для каждого обновления (start, end, val) выполните две операции:
Увеличьте значение в позиции start на val: arr[start] = arr[start] + val.
Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val.

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

3⃣Верните обновленный массив arr.

😎 Решение:

fun getModifiedArray(length: Int, updates: Array<IntArray>): IntArray {
    val result = IntArray(length)

    for (update in updates) {
        val start = update[0]
        val end = update[1]
        val `val` = update[2]
        result[start] += `val`
        if (end + 1 < length) {
            result[end + 1] -= `val`
        }
    }

    for (i in 1 until length) {
        result[i] += result[i - 1]
    }

    return result
}

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

Задача: №26. Remove Duplicates from Sorted Array
Сложность: easy

Учитывая целочисленный массив nums, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз.
Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов.

Пример:

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

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

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

2⃣Если nums[j] не равен nums[i], записать nums[j] на nums[i+1] и сдвинуть i.

3⃣По завершении вернуть i+1 как количество уникальных элементов.

😎 Решение:

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    i := 0
    for j := 1; j < len(nums); j++ {
        if nums[j] != nums[i] {
            i++
            nums[i] = nums[j]
        }
    }
    return i + 1
}

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

Задача: 441. Arranging Coins
Сложность: easy

У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.

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

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций.

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

import "math"

func arrangeCoins(n int) int {
    return int(math.Sqrt(float64(2 * n) + 0.25) - 0.5)
}

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

Задача: 1036. Escape a Large Maze
Сложность: hard

Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.

Пример:

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

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

1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.

2⃣Проверка простого случая:
Если список blocked пуст, верните true, так как путь не будет заблокирован.
Проверка начальной или целевой клетки:
Если исходная или целевая клетка заблокированы, верните false.

3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.

😎 Решение:

func isEscapePossible(blocked [][]int, source []int, target []int) bool {
    blockedSet := make(map[[2]int]struct{})
    for _, b := range blocked {
        blockedSet[[2]int{b[0], b[1]}] = struct{}{}
    }
    src := [2]int{source[0], source[1]}
    tgt := [2]int{target[0], target[1]}
    
    if _, found := blockedSet[src]; found || _, found := blockedSet[tgt]; found {
        return false
    }

    directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
    maxArea := len(blocked) * (len(blocked) - 1) / 2
    
    bfs := func(start, end [2]int) bool {
        queue := [][2]int{start}
        visited := map[[2]int]struct{}{start: {}}
        
        for len(queue) > 0 {
            if len(visited) > maxArea {
                return true
            }
            cur := queue[0]
            queue = queue[1:]
            for _, dir := range directions {
                next := [2]int{cur[0] + dir[0], cur[1] + dir[1]}
                if next[0] >= 0 && next[0] < 1_000_000 && next[1] >= 0 && next[1] < 1_000_000 {
                    if _, found := visited[next]; !found {
                        if _, found := blockedSet[next]; !found {
                            if next == end {
                                return true
                            }
                            queue = append(queue, next)
                            visited[next] = struct{}{}
                        }
                    }
                }
            }
        }
        return false
    }
    
    return bfs(src, tgt) && bfs(tgt, src)
}

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

Задача: 930. Binary Subarrays With Sum
Сложность: medium

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

1⃣Использовать словарь для хранения количества встреченных сумм префиксов.
Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями.

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

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

😎 Решение:

package main

func numSubarraysWithSum(nums []int, goal int) int {
    prefixSumCount := map[int]int{0: 1}
    currentSum := 0
    count := 0
    
    for _, num := range nums {
        currentSum += num
        count += prefixSumCount[currentSum - goal]
        prefixSumCount[currentSum]++
    }
    
    return count
}

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

Задача: 219. Contains Duplicate II
Сложность: easy

Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k.

Пример:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

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

1⃣Создайте пустое множество set.

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

3⃣Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false.

😎 Решение:

func containsNearbyDuplicate(nums []int, k int) bool {
    set := make(map[int]struct{})
    for i, num := range nums {
        if _, exists := set[num]; exists {
            return true
        }
        set[num] = struct{}{}
        if len(set) > k {
            delete(set, nums[i-k])
        }
    }
    return false
}

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

1⃣Отсортируйте массив слов по длине и лексикографическому порядку.

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

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

😎 Решение:

package main

import (
    "sort"
)

func longestWord(words []string) string {
    sort.Strings(words)
    validWords := map[string]struct{}{ "": {} }
    longest := ""
    for _, word := range words {
        if _, ok := validWords[word[:len(word)-1]]; ok {
            validWords[word] = struct{}{}
            if len(word) > len(longest) {
                longest = word
            }
        }
    }
    return longest
}

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

Задача: 477. Total Hamming Distance
Сложность: medium

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

Пример:

Input: nums = [4,14,2] 
Output: 6

Explanation:

4  = 0100  
14 = 1110  
2  = 0010  

(4,14): 2 различия  
(4,2):  2 различия  
(14,2): 2 различия  
Итого: 2+2+2 = 6

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

1⃣Перебираем все уникальные пары чисел из массива.

2⃣Для каждой пары считаем XOR, чтобы выявить, на каких позициях биты различаются. Затем считаем количество единиц в этом числе — это и есть Хэммингово расстояние.

3⃣Суммируем результат по всем парам и возвращаем общую сумму.

😎 Решение:

package main

func totalHammingDistance(nums []int) int {
    ans := 0
    if len(nums) == 0 {
        return ans
    }
    for i := 0; i < len(nums)-1; i++ {
        for j := i + 1; j < len(nums); j++ {
            ans += countBits(nums[i] ^ nums[j])
        }
    }
    return ans
}

func countBits(n int) int {
    count := 0
    for n > 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

func main() {}

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

Задача: №24. Swap Nodes in Pairs
Сложность: medium

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

Пример:

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

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

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

2⃣Использовать указатели prev, first и second для перестановки пары узлов.

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

😎 Решение:

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy

    for head != nil && head.Next != nil {
        first, second := head, head.Next

        prev.Next = second
        first.Next = second.Next
        second.Next = first

        prev = first
        head = first.Next
    }

    return dummy.Next
}

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

Задача: 1426. Counting Elements
Сложность: easy

Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно.

Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

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

1⃣Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве.

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

3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика.

😎 Решение:

package main

func countElements(arr []int) int {
    count := 0
    for _, x := range arr {
        if integerInArray(arr, x+1) {
            count++
        }
    }
    return count
}

func integerInArray(arr []int, target int) bool {
    for _, x := range arr {
        if x == target {
            return true
        }
    }
    return false
}

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

Задача: №65. Valid Number
Сложность: hard

Учитывая строку s, определите, является ли s валидным числом.

Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".

Формально, валидное число определяется с использованием одного из следующих определений:

Целое число с необязательным показателем степени.
Десятичное число с необязательным показателем степени.
Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры.

Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений:

Цифры, за которыми следует точка '.'.
Цифры, за которыми следует точка '.', за которой следуют цифры.
Точка '.', за которой следуют цифры.
Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число.

Цифры определяются как одна или более цифр.

Пример:

Input: s = "0"

Output: true

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

1⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true.

2⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число.

3⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры.

😎 Решение:

func isNumber(s string) bool {
    seenDigit := false
    seenExponent := false
    seenDot := false
    for i := 0; i < len(s); i++ {
        curr := s[i]
        if '0' <= curr && curr <= '9' {
            seenDigit = true
        } else if curr == '+' || curr == '-' {
            if i > 0 && s[i-1] != 'e' && s[i-1] != 'E' {
                return false
            }
        } else if curr == 'e' || curr == 'E' {
            if seenExponent || !seenDigit {
                return false
            }
            seenExponent = true
            seenDigit = false
        } else if curr == '.' {
            if seenDot || seenExponent {
                return false
            }
            seenDot = true
        } else {
            return false
        }
    }
    return seenDigit
}

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

Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy

Дан неотсортированный массив nums. Нужно найти длину самой длинной непрерывной строго возрастающей подпоследовательности (подмассива).

Пример:

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

Пояснение: [1,3,5] — самая длинная возрастающая подпоследовательность подряд. [1,3,5,7] — не считается, потому что 4 нарушает последовательность.

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

1⃣Инициализация
Заводим переменные ans для хранения максимальной длины и anchor — начало текущей подпоследовательности.

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

3⃣Обновление результата
На каждом шаге считаем длину текущей последовательности как i - anchor + 1 и обновляем ans, если она больше текущего значения.

😎 Решение:

func findLengthOfLCIS(nums []int) int {
    ans, anchor := 0, 0
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i-1] >= nums[i] {
            anchor = i
        }
        if i-anchor+1 > ans {
            ans = i - anchor + 1
        }
    }
    return ans
}

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

Задача: 258. Add Digits
Сложность: easy

Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1⃣Инициализируйте переменную digital_root значением 0.

2⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3⃣Верните значение digital_root.

😎 Решение:

func addDigits(num int) int {
    digital_root := 0
    for num > 0 {
        digital_root += num % 10
        num /= 10
        if num == 0 && digital_root > 9 {
            num = digital_root
            digital_root = 0
        }
    }
    return digital_root
}

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