✏️ Задача дня: 3Sum

Дан массив целых чисел nums. Требуется найти все уникальные тройки (a, b, c), такие что a + b + c = 0. Порядок элементов в тройке не важен, дубликаты недопустимы.

Идея оптимального решения

1. Сортируем массив (O(n log n)), чтобы упростить поиск и контроль дубликатов.

2. Фиксируем первый элемент i, затем две указки l и r («два указателя») пробегают подмассив справа/слева:

Если сумма < 0 → сдвигаем l++,

Если сумма > 0 → сдвигаем r--,

Если сумма == 0 → сохраняем тройку и пропускаем дубликаты вокруг l и r.

3. Пропускаем дубликаты и для i, чтобы не повторять стартовую точку.

Сложность: O(n^2) по времени и O(1) доп. памяти не считая результата.

Реализация:

package main

import (
  "fmt"
  "sort"
)

func threeSum(nums []int) [][]int {
  sort.Ints(nums)
  n := len(nums)
  res := make([][]int, 0)

  for i := 0; i < n; i++ {
    // Пропускаем одинаковые стартовые значения
    if i > 0 && nums[i] == nums[i-1] {
      continue
    }
    // Ранний выход: дальше только положительные
    if nums[i] > 0 {
      break
    }

    l, r := i+1, n-1
    for l < r {
      sum := nums[i] + nums[l] + nums[r]
      switch {
      case sum < 0:
        l++
      case sum > 0:
        r--
      default:
        res = append(res, []int{nums[i], nums[l], nums[r]})
        // Пропускаем дубликаты для l
        lVal := nums[l]
        for l < r && nums[l] == lVal {
          l++
        }
        // Пропускаем дубликаты для r
        rVal := nums[r]
        for l < r && nums[r] == rVal {
          r--
        }
      }
    }
  }
  return res
}

func main() {
  examples := [][]int{
    {-1, 0, 1, 2, -1, -4},
    {0, 0, 0, 0},
    {-2, 0, 1, 1, 2},
  }

  for _, nums := range examples {
    fmt.Println("Input:", nums)
    fmt.Println("Triplets:", threeSum(append([]int{}, nums...)))
  }
}

🐸Библиотека Go-разработчика

#ReadySetGo

✏️ Задача дня: Partition Labels

Дана строка из маленьких латинских букв. Требуется разбить её на максимальное число частей так, чтобы каждая буква встречалась только в одной части. Вернуть длины частей по порядку.

Как решить:

1. Фиксируем последнее появление каждой буквы

Проходим по строке и для каждой буквы запоминаем последний встреченный индекс в map:

for i, r := range s {
    last[r] = i
}

2. Формируем части строки

Начинаем слева: left — старт текущей части, right — крайний индекс, который должен быть включён.

Для текущей позиции берем руну и смотрим на её последнее вхождение с помощью map. Если оно дальше right, расширяем правую границу:

if last[r] > right {
    right = last[r]
}

Увеличиваем счетчик длины части. Если текущая позиция left == right, значит мы собрали часть, где все буквы ограничены этим диапазоном — больше ни одна буква не убежит в следующий кусок.

Сохраняем длину части, обнуляем счётчик, переходим к сборке следующей части.

Код:

func partitionLabels(s string) []int {
    // Первый проход: фиксируем последний индекс для каждой буквы
    last := make(map[rune]int)
    for i, r := range s {
        last[r] = i
    }

    // Второй проход: формируем части
    var res []int
    left, right := 0, 0
    for i, r := range s {
        if last[r] > right {
            right = last[r]
        }
        if i == right {
            res = append(res, right-left+1)
            left = i + 1
        }
    }
    return res
}

🐸 Библиотека Go-разработчика

#ReadySetGo

🧩 Полуночный вопрос

Есть такой код:

nums := []int{1, 2, 3, 4, 5, 6, 7, 8}

for i, num := range nums[3:] {
    fmt.Printf("i=%d, num=%d\n", i, num)
}

Вопрос: какое значение будет у i на первой итерации? 0 или 3?

Ответ: 0. И вот почему: когда мы используем nums[3:], создаётся новый слайс, который начинается с 4-го элемента исходного массива.

Оператор range всегда возвращает индексы относительно того слайса, по которому он итерируется, а не исходного массива.

🐸 Библиотека Go-разработчика

#ReadySetGo

✏️ Разбираем битовую задачку

Сегодня в ежедневной задаче на литкоде попалась интересная штука — нужно найти наименьшее число, которое не меньше заданного N и состоит только из единиц в двоичной записи.

Вам дают число, например, 10 (в двоичной системе это 1010). Нужно найти ближайшее число >= 10, где все биты — единицы. В данном случае это 15 (двоичная 1111).

Первое решение, которое приходит в голову. Можно просто пройтись по всем битам исходного числа и установить каждый в 1:

func smallestNumber(n int) int {
    result := 0
    bitPosition := 0
    
    for n > 0 {
        result |= (1 << bitPosition)  // устанавливаем бит
        bitPosition++
        n >>= 1  // сдвигаем к следующему биту
    }
    
    return result
}

Работает, но есть способ элегантнее. Решение в одну строчку:

Вспомните, как выглядят числа-степени двойки минус один:

2¹ - 1 = 1 (двоичная: 1)
2² - 1 = 3 (двоичная: 11)
2³ - 1 = 7 (двоичная: 111)
2⁴ - 1 = 15 (двоичная: 1111)

Видите паттерн? Нам нужно найти самый старший бит в исходном числе и взять следующую степень двойки минус один.

Для числа 10 (двоичная 1010) старший бит на позиции 3. Значит, берём 2⁴ - 1 = 15.

func smallestNumber(n int) int {
    x := 1
    for x - 1 < n {
        x <<= 1  // умножаем на 2
    }
    return x - 1
}

Или через битовые операции с помощью bits.Len:

import "math/bits"

func smallestNumber(n int) int {
    bitLength := bits.Len(uint(n))  // находим количество бит
    return (1 << bitLength) - 1
}

Число с N единицами подряд — это всегда 2^N - 1. Мы находим, сколько битов нужно, чтобы вместить наше число, и берём число с таким количеством единиц.

➡️ Решить задачу

Чтобы щёлкать такие задачи не нужно знать, всё, хватит базы. Подтянуть такую базу поможет наш курс по алгоритмам. До конца октября скидка 40%

🐸 Библиотека Go-разработчика

#ReadySetGo

✏️ FizzBuzz — классика собеседований

Задача проста на вид, но открывает много вопросов на интервью. Вот почему её так любят спрашивать.

Дано число n. Нужно вернуть массив строк, где для каждого числа от 1 до n:

• если кратно и 3 и 5 — «FizzBuzz»
• если кратно 3 — «Fizz»
• если кратно 5 — «Buzz»
• иначе — само число как строку

Решение:

func fizzBuzz(n int) []string {
    res := make([]string, n)
    for i := 1; i <= n; i++ {
        res[i-1] = strconv.Itoa(i)
        if i % 3 == 0 { res[i-1] = "Fizz" }
        if i % 5 == 0 { res[i-1] = "Buzz" }
        if i % 15 == 0 { res[i-1] = "FizzBuzz" }
    }
    return res
}

Число 15 — это наименьшее общее кратное чисел 3 и 5. Когда число одновременно делится на 3 и на 5, оно всегда делится на 15.

На собеседовании сначала напишите просто, потом обсудите улучшения. FizzBuzz — не про трюки синтаксиса, а про чистоту мышления и умение общаться с интервьюером.

🐸 Библиотека Go-разработчика

#ReadySetGo

🪙 Выложить монетки в лестницу

Дано n монет. Нужно выложить лестницу, где на i-й ступени ровно i монет. Вернуть количество полных рядов лестницы, которые удастся построить.

Наивный перебор даёт O(n), но попробуем быстрее:

func arrangeCoins(n int) int {
    left, right := 0, n
    for left <= right {
        mid := left + (right-left)/2
        sum := mid * (mid + 1) / 2
        if sum == n {
            return mid
        }
        if sum < n {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
}

Вместо перебора каждого уровня, бинарный поиск за O(log n) найдёт точный ответ.

🐸 Библиотека Go-разработчика

#ReadySetGo

✏️ Как найти максимальную уникальную подстроку

Дана строка из символов. Требуется найти длину самой длинной подстроки, в которой все символы встречаются только один раз подряд. Иными словами — ищем максимально уникальный фрагмент строки.

Пример:

abcabcbb → 3 (abc)
bbbbb → 1 (b)
pwwkew → 3 (wke или kew)

Решение. Используем скользящее окно и мапу для отслеживания последних позиций:

func lengthOfLongestSubstring(s string) int {
    m := make(map[rune]int)
    maxLen, left := 0, 0
    for right, ch := range s {
        if idx, ok := m[ch]; ok && idx >= left {
            left = idx + 1
        }
        m[ch] = right
        if curLen := right - left + 1; curLen > maxLen {
            maxLen = curLen
        }
    }
    return maxLen
}

left — старт окна, right — конец. Если символ “повторился” (уже был в окне), двигаем left — выкидываем всё до текущего повторяющегося символа.

Асимптотика: O(n), где n — длина строки.

🐸 Библиотека Go-разработчика

#ReadySetGo

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

Дан массив нулей и единиц, нужно проверить, что между любыми двумя единицами находится минимум 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
}

Результат: O(n) время, O(1) память.

🐸 Библиотека Go-разработчика

#ReadySetGo

✏️ Проверка двоичных префиксов

В задаче нам дан массив из 0 и 1, который представляет собой двоичное число. Нужно для каждого элемента определить, делится ли число, образованное подмассивом от начала до текущей позиции, на 5.

Алгоритм решения задачи следующий:

Возьмите пустое число и двигаясь по массиву слева направо, добавляйте к этому числу новый бит — 0 или 1. Но чтобы не считать всё число целиком, потому что оно растёт и становится очень большим, мы каждый раз запоминаем только остаток от деления на 5.

Код решения:

func prefixesDivBy5(nums []int) []bool {
    result := make([]bool, len(nums), len(nums))
    var i = 0
    var num int
    for _, d := range nums {
        num = ((num << 1) | d) % 5
        result[i] = num == 0
        i++
    }
    return result
}

🔸 Основы IT для непрограммистов
🔸 Получить консультацию менеджера
🔸 Сайт Академии 🔸 Сайт Proglib

🐸 Библиотека Go-разработчика

#ReadySetGo