#medium
Задача: 930. Binary Subarrays With Sum

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

Пример:

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

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

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

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

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

😎 Решение:

package main

import "fmt"

func numSubarraysWithSum(nums []int, goal int) int {
    prefixSumCount := make(map[int]int)
    prefixSumCount[0] = 1

    currentSum, count := 0, 0

    for _, num := range nums {
        currentSum += num

        if val, exists := prefixSumCount[currentSum-goal]; exists {
            count += val
        }

        prefixSumCount[currentSum]++
    }

    return count
}

func main() {
    nums := []int{1, 0, 1, 0, 1}
    goal := 2
    fmt.Println(numSubarraysWithSum(nums, goal))
}

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

#medium
Задача: 750. Number Of Corner Rectangles

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

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

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

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

😎 Решение:

package main

func countCornerRectangles(grid [][]int) int {
    count := 0
    for i := 0; i < len(grid); i++ {
        for j := i + 1; j < len(grid); j++ {
            numPairs := 0
            for k := 0; k < len(grid[0]); k++ {
                if grid[i][k] == 1 && grid[j][k] == 1 {
                    numPairs++
                }
            }
            if numPairs > 1 {
                count += numPairs * (numPairs - 1) / 2
            }
        }
    }
    return count
}

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

#medium
Задача: 751. IP to CIDR

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func ipToInt(ip string) int {
    parts := strings.Split(ip, ".")
    p1, _ := strconv.Atoi(parts[0])
    p2, _ := strconv.Atoi(parts[1])
    p3, _ := strconv.Atoi(parts[2])
    p4, _ := strconv.Atoi(parts[3])
    return (p1 << 24) + (p2 << 16) + (p3 << 8) + p4
}

func intToIp(num int) string {
    return fmt.Sprintf("%d.%d.%d.%d", (num>>24)&255, (num>>16)&255, (num>>8)&255, num&255)
}

func cidr(ip string, prefixLength int) string {
    return fmt.Sprintf("%s/%d", ip, prefixLength)
}

func findCidrBlocks(startIp string, n int) []string {
    start := ipToInt(startIp)
    var result []string
    
    for n > 0 {
        maxSize := 1
        for maxSize <= start && maxSize <= n {
            maxSize <<= 1
        }
        maxSize >>= 1
        
        for start%maxSize != 0 {
            maxSize >>= 1
        }
        
        result = append(result, cidr(intToIp(start), 32-log2(maxSize)+1))
        start += maxSize
        n -= maxSize
    }
    
    return result
}

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

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

#medium
Задача: 752. Open the Lock

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

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

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

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

package main

import (
    "fmt"
)

func openLock(deadends []string, target string) int {
    neighbors := func(node string) []string {
        res := []string{}
        for i := 0; i < 4; i++ {
            x := node[i] - '0'
            for _, d := range []int{-1, 1} {
                y := (x + byte(d) + 10) % 10
                res = append(res, node[:i]+string(y+'0')+node[i+1:])
            }
        }
        return res
    }

    dead := make(map[string]bool)
    for _, d := range deadends {
        dead[d] = true
    }

    queue := []string{"0000"}
    steps := 0
    visited := make(map[string]bool)
    visited["0000"] = true

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if node == target {
                return steps
            }
            if dead[node] {
                continue
            }
            for _, neighbor := range neighbors(node) {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }
        steps++
    }

    return -1
}

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

#medium
Задача: 753. Cracking the Safe

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

func crackSafe(n int, k int) string {
    seen := make(map[string]bool)
    var result []byte

    startNode := strings.Repeat("0", n-1)
    dfs(startNode, k, seen, &result)

    result = append(result, startNode...)
    return string(result)
}

func dfs(node string, k int, seen map[string]bool, result *[]byte) {
    for x := 0; x < k; x++ {
        neighbor := node + fmt.Sprint(x)
        if !seen[neighbor] {
            seen[neighbor] = true
            dfs(neighbor[1:], k, seen, result)
            *result = append(*result, byte(x+'0'))
        }
    }
}

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

#medium
Задача: 754. Reach a Number

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

package main

import (
    "fmt"
    "math"
)

func reachTarget(target int) int {
    target = int(math.Abs(float64(target)))
    position := 0
    steps := 0
    for position < target || (position - target) % 2 != 0 {
        steps++
        position += steps
    }
    return steps
}

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