Расстояния между единицами: находим нужный паттерн Дан массив нулей и… — Библиотека Go-разработчика

Библиотека Go-разработчика | Golang@goproglib · 24.1K subscribers Open in TelegramOpen

Расстояния между единицами: находим нужный паттерн

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

Массив [1,0,0,0,1,0,0,1] при k=2 валиден: между первой и второй единицей три нуля (достаточно), между второй и третьей — два нуля (достаточно). А вот [1,0,1,0,0,1] при k=2 — нет, потому что первые две единицы разделены только одним нулём.

Запоминаем позицию последней найденной единицы. Когда встречаем новую, проверяем расстояние до неё и сразу обновляем позицию.

Это будет один проход по массиву:


func kLengthApart(nums []int, k int) bool {
    lastPos := -k - 1
    
    for i := 0; i < len(nums); i++ {
        if nums[i] == 1 {
            if i - lastPos - 1 < k {
                return false
            }
            lastPos = i
        }
    }
    return true
}