Можно ли посадить цветы?

Всем привет!
Долго думал, какую задачку запостить перед новым годом 🙂 Сперва хотел найти что-нибудь интересное и хитрое, но в итоге решил, что думать перед новогодними каникулами не хочется. Поэтому можно просто расслабиться и решить что-нибудь простое и тривиальное.

P.S. Всех с наступающим и счастливого Нового Года!
Мы тоже уйдем на небольшие каникулы и вернемся к каналу после 9го января. Оставайтесь с нами, в новом году мы продолжим решать алгоритмические задачки, а также попробуем запустить еще один или несколько новых форматов 🙂

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дан целочисленный массив flowerbed и число n.

Массив описывает цветочную клумбу, каждый элемент массива может принимать значение 1 (на этом месте посажен цветок) и 0 (пустое место). Существует ограничение - цветы не могут быть посажены на соседних местах.

Необходимо написать функцию, которая определит, можем ли мы посадить в нашу клумбу n новых цветов.

⚠️ Ограничения

- Длина клумбы лежит в диапазоне от 1 до 20000
- Значение каждого элемента массива может равняться либо 0, либо 1
- В исходном массиве не может быть двух цветков на соседних местах (то есть, исходно мы имеем валидный массив)
- n лежит в диапазоне от 0 до длины массива flowerbed (то есть, не превышает размер клумбы)

1️⃣Пример

Входящие данные

flowerbed = [1,0,0,0,1], n = 1

Ответ

true

2️⃣ Пример

Входящие данные

[1,0,0,0,1], n = 2

Ответ

false

✅ Решение

Посмотреть подробное объяснение решения

#array #easy

Неповторяющееся число

Привет, друзья!

Новогодние праздники прошли и пришла пора возвращаться к задачам. Я понимаю, что эта рабочая почти неделя многим далась тяжело, поэтому мы начнем с простой задачи, но на ту тему, которую еще не разбирали. Будет интересно!

Сложность: 🟢 Легкая

ℹ️ Описание

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

Вы должны реализовать решение с линейной сложностью по времени и константной по памяти.

⚠️ Ограничения

- В массиве может быть от 1 до 30 000 элементов
- Каждый элемент массива имеет значение в диапазоне от -30 000 до 30 000
- Каждый элемент массива встречается дважды, за исключением одного элемента

1️⃣ Пример

Входящие данные

[2, 2, 1]

Ответ

1

2️⃣ Пример

Входящие данные

[4, 1, 2, 1, 2]

Ответ

4

✅ Решение

Я знаю, что первая идея, которая может прийти вам в голову — это реализовать классический обход массива с подсчетом частоты каждого числа. Для этого для каждого числа в хеш-таблице мы будем хранить пару, в которой ключом является само число, а значением — сколько раз оно встречается в массиве. В конце нужно будет лишь просмотреть всю таблицу и выбрать то число, у которого счетчик равен 1.

В результате мы получим такое решиние.

export const singleNumberMap = (nums: number[]): number => {
    const countMap: Record<number, number> = {}

    nums.forEach((num) => {
        const curr = countMap[num] ?? 0
        countMap[num] = curr + 1
    })

    const entries = Object.entries(countMap)

    for (let i = 0; i < entries.length; i++) {
        const [num, count] = entries[i]
        if (count === 1) {
            return Number(num)
        }
    }

    return 0
}

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

На самом деле задача очень легкая, но надо знать хитрость, а именно — как работает операция XOR.

Посмотреть разбор решения в блоге

#array #easy #bit_manipulation