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

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

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

Пример:

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

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

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

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

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

😎 Решение:

import (
    "container/heap"
)

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

type MaxHeap []int

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

    return equal(s1Count, s2Count)
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

        return count;
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение

type ListNode struct {
    Val  int
    Next *ListNode
}

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

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

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

        start = start.Next
    }
    return front.Next
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

import "math"

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

import (
    "container/heap"
)

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

type PriorityQueue []Fraction

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

    return result.Next
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

package main

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

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

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

    return maxCount
}

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

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

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

    return enemyCount
}

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

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


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

Пример:

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

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

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

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

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

😎 Решение:

import (
    "math/bits"
)

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

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

    return len(seen)
}

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

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

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

Задача: 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
}

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