38. Количество прыжков для достижения конца массива

Вопрос: Напишите функцию, которая возвращает количество переходов, необходимых для достижения конца целочисленного массива, представляющего количество возможных шагов.

Например, учитывая [2, 3, 1, 0, 4, 1, 5, 1, 0, 2], вы должны вернуть 4,

Например, учитывая [2, 1, 3, 2, 1, 0, 2], вы должны вернуть nil.

Подсказки:

- Вам нужно перебрать массив и для каждого элемента вычислить максимальное достигнутое значение,

- Если ваш текущий элемент больше, чем достигнутый максимум, вы не можете достичь конца.

Решение:

func numberOfJumps(array: [Int]) -> Int? {
    // 1.
    guard array.count > 1 else { return 0 }

    // 2.
    var maxReached = array[0]
    var steps = array[0]
    var jump = 1

    // 3.
    for i in 1..<array.count {
        if i == array.count - 1 {
            // 4.
            return jump
        }

        // 5.
        maxReached = max(maxReached, i + array[i])

        // 6.
        steps -= 1

        if steps == 0 {
            // 7.
            jump += 1
            if i >= maxReached {
                // 8.
                return nil
            }

            // 9.
            steps = maxReached - i
        }
    }

    // 10.
    return nil
}

Пояснения:

1. Если в массиве меньше двух элементов, то переходы в конец не нужны.

guard array.count > 1 else { return 0 }

2. Определим несколько переменных (максимально достигнутый индекс, количество возможных шагов, количество выполненных прыжков).

var maxReached = array[0]
var steps = array[0]
var jump = 1

3. Теперь давайте повторим массив.

for i in 1..<array.count {

4. Если мы достигли последнего элемента массива, вернуть количество сделанных прыжков.

if i == array.count - 1 {
  return jump
}

5. Обновим индекс максимального охвата (максимум между предыдущим максимальным и текущим индексом плюс возможное количество шагов).

maxReached = max(maxReached, i + array[i])

6. Давайте сделаем один шаг и уменьшим количество возможных шагов.

steps -= 1

7. Если количество шагов равно 0, увеличим количество прыжков.

if steps == 0 {
  jump += 1

8. Если текущий индекс равен или больше максимально достигнутого, мы не можем достичь конца, возвращаем nil.

if i >= maxReached {
  return nil
}

9. Обновите количество шагов по разнице между максимальным достигнутым и текущим индексом.

steps = maxReached — i

10. На данный момент мы не достигли и не можем достичь конца массива, возвращаем nil.

return nil

Сложность:

- Временная сложность: как максимум, мы перебираем все элементы массива, временная сложность является линейной O (n),

- Сложность пространства: поскольку нам нужно несколько целочисленных переменных (индексы и счетчик), сложность пространства постоянна O (1).

Тест-кейсы:

public func testNumberOfJumps() {
  assert(numberOfJumps(array: [2, 3, 1, 0, 4, 1, 5, 1, 0, 2]) == 4, "numberOfJumps 1 not equal")
  assert(numberOfJumps(array: [2, 1, 3, 2, 1, 0, 2]) == nil, "numberOfJumps 2 not equal")
}

Следовать за:

Нет дополнительного вопроса.

‹‹ Структуры данных, алгоритмы и вопросы для интервью ››