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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

    return result.Next
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

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

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

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

    return maxCount
}

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

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

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

    return enemyCount
}

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

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


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

Пример:

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

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

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

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

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

😎 Решение:

import (
    "math/bits"
)

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

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

    return len(seen)
}

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

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

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

Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

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

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

😎 Решение:

package main

import "strings"

func search(L, n int, S string) int {
    seen := make(map[string]bool)
    for start := 0; start <= n-L; start++ {
        tmp := S[start : start+L]
        if seen[tmp] {
            return start
        }
        seen[tmp] = true
    }
    return -1
}

func longestRepeatingSubstring(S string) int {
    n := len(S)
    left, right := 1, n
    for left <= right {
        L := left + (right-left)/2
        if search(L, n, S) != -1 {
            left = L + 1
        } else {
            right = L - 1
        }
    }
    return left - 1
}

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

Задача: 859. Buddy Strings
Сложность: easy

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

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

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

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

func buddyStrings(s string, goal string) bool {
    if len(s) != len(goal) {
        return false
    }
    if s == goal {
        freq := make(map[rune]int)
        for _, ch := range s {
            freq[ch]++
            if freq[ch] > 1 {
                return true
            }
        }
        return false
    }

    firstIndex, secondIndex := -1, -1
    for i := range s {
        if s[i] != goal[i] {
            if firstIndex == -1 {
                firstIndex = i
            } else if secondIndex == -1 {
                secondIndex = i
            } else {
                return false
            }
        }
    }

    return secondIndex != -1 &&
           s[firstIndex] == goal[secondIndex] &&
           s[secondIndex] == goal[firstIndex]
}

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

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

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

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

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

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

3⃣Результирующий алгоритм прост:
1. Установите два указателя, один на каждом конце входной строки.
2. Если ввод является палиндромом, оба указателя должны указывать на эквивалентные символы в любой момент времени.
3. Если это условие не выполняется в какой-либо момент времени, мы прерываемся и возвращаемся раньше.
4. Мы можем просто игнорировать неалфавитно-цифровые символы, продолжая двигаться дальше.
5. Продолжайте перемещение внутрь, пока указатели не встретятся в середине.

😎 Решение:

func isPalindrome(s string) bool {
    i := 0
    j := len(s) - 1
    for i < j {
        for i < j && !isalnum(s[i]) {
            i++
        }
        for i < j && !isalnum(s[j]) {
            j--
        }
        if tolower(s[i]) != tolower(s[j]) {
            return false
        }
        i++
        j--
    }
    return true
}

func isalnum(c byte) bool {
    return ('0' <= c && c <= '9') || ('a' <= c && c <= 'z') ||
        ('A' <= c && c <= 'Z')
}

func tolower(c byte) byte {
    if 'A' <= c && c <= 'Z' {
        return c - 'A' + 'a'
    }
    return c
}

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

Задача: 819. Most Common Word
Сложность: easy

Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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

1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

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

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

func mostCommonWord(paragraph string, banned []string) string {
    normalizedStr := strings.Map(func(r rune) rune {
        if unicode.IsLetter(r) || unicode.IsDigit(r) {
            return unicode.ToLower(r)
        }
        return ' '
    }, paragraph)

    words := strings.Fields(normalizedStr)
    wordCount := make(map[string]int)
    bannedWords := make(map[string]bool)

    for _, word := range banned {
        bannedWords[word] = true
    }

    for _, word := range words {
        if !bannedWords[word] {
            wordCount[word]++
        }
    }

    maxWord := ""
    maxCount := 0
    for word, count := range wordCount {
        if count > maxCount {
            maxWord = word
            maxCount = count
        }
    }

    return maxWord
}

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

Задача: 541. Reverse String II
Сложность: easy

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

Если осталось меньше k символов — переверните все.
Если осталось от k до 2k — переверните первые k, остальные оставьте как есть.

Пример:

Input: s = "abcdefg", k = 2 
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов. Начинаем с индексов, кратных 2k: 0, 2k, 4k и т.д.

2⃣Если до конца строки осталось < k символов — разворачиваем все оставшиеся.

3⃣Разворот делаем в диапазоне [i, j], меняя символы местами: i++, j--.

😎 Решение:

func reverseStr(s string, k int) string {
    a := []rune(s)
    for start := 0; start < len(a); start += 2 * k {
        i, j := start, min(start+k-1, len(a)-1)
        for i < j {
            a[i], a[j] = a[j], a[i]
            i++
            j--
        }
    }
    return string(a)
}

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

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

Задача: 468. Validate IP Address
Сложность: medium

Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "[email protected]" являются недопустимыми IPv4-адресами.

Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7
", где:
1 <= xi.length <= 4
xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F').
Ведущие нули в xi допускаются.

Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

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

1⃣Для проверки адреса IPv4:
Разделить IP на четыре части по разделителю ".".
Проверить каждую подстроку:
Является ли она целым числом между 0 и 255.
Не содержит ли она ведущих нулей (исключение — число "0").

2⃣Для проверки адреса IPv6:
Разделить IP на восемь частей по разделителю ":".
Проверить каждую подстроку:
Является ли она шестнадцатеричным числом длиной от 1 до 4 символов.

3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither".

😎 Решение:

package main

import (
    "strconv"
    "strings"
    "unicode"
)

func validateIPv4(IP string) string {
    nums := strings.Split(IP, ".")
    if len(nums) != 4 {
        return "Neither"
    }
    for _, x := range nums {
        if len(x) == 0 || len(x) > 3 {
            return "Neither"
        }
        if x[0] == '0' && len(x) != 1 {
            return "Neither"
        }
        for _, ch := range x {
            if !unicode.IsDigit(ch) {
                return "Neither"
            }
        }
        num, err := strconv.Atoi(x)
        if err != nil || num > 255 {
            return "Neither"
        }
    }
    return "IPv4"
}

func validateIPv6(IP string) string {
    nums := strings.Split(IP, ":")
    hexdigits := "0123456789abcdefABCDEF"
    if len(nums) != 8 {
        return "Neither"
    }
    for _, x := range nums {
        if len(x) == 0 || len(x) > 4 {
            return "Neither"
        }
        for _, ch := range x {
            if !strings.ContainsRune(hexdigits, ch) {
                return "Neither"
            }
        }
    }
    return "IPv6"
}

func validIPAddress(IP string) string {
    if strings.Count(IP, ".") == 3 {
        return validateIPv4(IP)
    } else if strings.Count(IP, ":") == 7 {
        return validateIPv6(IP)
    } else {
        return "Neither"
    }
}

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

Задача: 850. Rectangle Area II
Сложность: hard

Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.

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

Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

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

1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.

2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

import (
    "sort"
)

func rectangleArea(rectangles [][]int) int {
    const MOD int = 1_000_000_007

    Xvals := make(map[int]struct{})
    Yvals := make(map[int]struct{})

    for _, rec := range rectangles {
        Xvals[rec[0]] = struct{}{}
        Xvals[rec[2]] = struct{}{}
        Yvals[rec[1]] = struct{}{}
        Yvals[rec[3]] = struct{}{}
    }

    var imapx []int
    for x := range Xvals {
        imapx = append(imapx, x)
    }
    sort.Ints(imapx)

    var imapy []int
    for y := range Yvals {
        imapy = append(imapy, y)
    }
    sort.Ints(imapy)

    mapx := make(map[int]int)
    for i, x := range imapx {
        mapx[x] = i
    }

    mapy := make(map[int]int)
    for i, y := range imapy {
        mapy[y] = i
    }

    grid := make([][]bool, len(imapx))
    for i := range grid {
        grid[i] = make([]bool, len(imapy))
    }

    for _, rec := range rectangles {
        for x := mapx[rec[0]]; x < mapx[rec[2]]; x++ {
            for y := mapy[rec[1]]; y < mapy[rec[3]]; y++ {
                grid[x][y] = true
            }
        }
    }

    ans := int64(0)
    for x := 0; x < len(grid); x++ {
        for y := 0; y < len(grid[0]); y++ {
            if grid[x][y] {
                ans += int64(imapx[x+1]-imapx[x]) * int64(imapy[y+1]-imapy[y])
            }
        }
    }

    ans %= MOD
    return int(ans)
}

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

Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee
Сложность: medium

Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.

Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

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

1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций.

2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию.

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

😎 Решение:

package main

func maxProfit(prices []int, fee int) int {
    cash, hold := 0, -prices[0]
    for _, price := range prices {
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    }
    return cash
}

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

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