Как найти минимальное количество переходов для достижения конца массива в O (n) времени

Ответ 1

Временная сложность предлагаемого решения на сайте линейна, потому что вы только один раз перебираете массив. Алгоритм позволяет избежать внутренней итерации моего предложенного решения, используя некоторые умные трюки.

Переменная maxReach всегда сохраняет максимальную доступную позицию в массиве. jump хранит количество прыжков, необходимых для достижения этой позиции. step хранит количество шагов, которые мы еще можем предпринять (и инициализируется количеством шагов в первой позиции массива)

Во время итерации вышеуказанные значения обновляются следующим образом:

Сначала мы проверяем, достиг ли мы конца массива, и в этом случае нам просто нужно вернуть переменную jump.

Затем мы обновляем максимальную доступную позицию. Это равно максимуму maxReach и i+A[i] (количество шагов, которые мы можем взять из текущей позиции).

Мы использовали шаг для перехода к текущему индексу, поэтому steps нужно уменьшить.

Если больше шагов не осталось (т.е. steps=0, то мы должны были использовать скачок, поэтому увеличиваем jump. Поскольку мы знаем, что возможно как-то достичь maxReach, мы инициализируем шаги до суммы шагов для достижения maxReach с позиции i.

public class Solution {
    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int maxReach = A[0];
        int step = A[0];
        int jump = 1;
        for (int i = 1; i < A.length; i++) {
           if (i == A.length - 1)
                return jump;
            if (i + A[i] > maxReach)
                maxReach = i + A[i];
            step--;
            if (step == 0) {
                jump++;
                step = maxReach - i;
            } 
        }
        return jump;
    }
}

Пример:

int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
int maxReach = A[0];     // A[0]=1, so the maximum index we can reach at the moment is 1.
int step = A[0];         // A[0] = 1, the amount of steps we can still take is also 1.
int jump = 1;            // we will always need to take at least one jump.

/*************************************
 * First iteration (i=1)
 ************************************/
if (i + A[i] > maxReach) // 1+3 > 1, we can reach further now!
    maxReach = 1 + A[i]  // maxReach = 4, we now know that index 4 is the largest index we can reach.

step--                   // we used a step to get to this index position, so we decrease it
if (step == 0) {
    ++jump;              // we ran out of steps, this means that we have made a jump
                         // this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
                         // but we can continue with the 3 steps received at array position 2.
    steps = maxReach-i   // we know that by some combination of 2 jumps, we can reach  position 4.
                         // therefore in the current situation, we can minimaly take 3
                         // more steps to reach position 4 => step = 3
}

/*************************************
 * Second iteration (i=2)
 ************************************/
if (i + A[i] > maxReach) // 2+5 > 4, we can reach further now!
    maxReach = 1 + A[i]  // maxReach = 7, we now know that index 7 is the largest index we can reach.

step--                   // we used a step so now step = 2
if (step==0){
   // step 
}

/*************************************
 * Second iteration (i=3)
 ************************************/
if (i + A[i] > maxReach) // 3+8 > 7, we can reach further now!
    maxReach = 1 + A[i]  // maxReach = 11, we now know that index 11 is the largest index we can reach.

step--                   // we used a step so now step = 1
if (step==0){
   // step 
}

/*************************************
 * Third iteration (i=4)
 ************************************/
if (i + A[i] > maxReach) // 4+9 > 11, we can reach further now!
    maxReach = 1 + A[i]  // maxReach = 13, we now know that index 13 is the largest index we can reach.

step--                   // we used a step so now step = 0
if (step == 0) {
    ++jump;              // we ran out of steps, this means that we have made a jump.
                         // jump is now equal to 3.
    steps = maxReach-i   // there exists a combination of jumps to reach index 13, so
                         // we still have a budget of 9 steps
}


/************************************
 * remaining iterations
 ***********************************
// nothing much changes now untill we reach the end of the array.

Мой субоптимальный алгоритм, который работает в O(nk) время с n числом элементов в массиве и k самым большим элементом в массиве и использует внутренний цикл над array[i]. Этот цикл избегает описанного ниже алгоритма.

код

public static int minimum_steps(int[] array) {
    int[] min_to_end = new int[array.length];
    for (int i = array.length - 2; i >= 0; --i) {
        if (array[i] <= 0)
            min_to_end[i] = Integer.MAX_VALUE;
        else {
            int minimum = Integer.MAX_VALUE;
            for (int k = 1; k <= array[i]; ++k) {
                if (i + k < array.length)
                    minimum = Math.min(min_to_end[i+k], minimum);
                else
                    break;
            }
            min_to_end[i] = minimum + 1;
        }
    }
    return min_to_end[0];
} 

Ответ 2

Поздно поздно, но вот другое решение O (n), которое имело смысл для меня.

/// <summary>
/// 
/// The actual problem is if it worth not to jump to the rightmost in order to land on a value that pushes us further than if we jumped on the rightmost.
/// 
/// However , if we approach the problem from the end,  we go end to start,always jumping to the leftmost
/// 
/// with this approach , these is no point in not jumping to the leftmost from end to start , because leftmost will always be the index that has the leftmost leftmost :) , so always choosing leftmost is the fastest way to reach start
/// 
/// </summary>
/// <param name="arr"></param>
static void Jumps (int[] arr)
{
    var LeftMostReacher = new int[arr.Length];
    //let see , for each element , how far back can it be reached from 

    LeftMostReacher[0] = -1; //the leftmost reacher of 0 is -1

    var unReachableIndex = 1; //this is the first index that hasn't been reached by anyone yet
    //we use this unReachableIndex var so each index leftmost reacher is  the first that was able to jump to it . Once flagged by the first reacher , new reachers can't be the leftmost anymore so they check starting from unReachableIndex

    // this design insures that the inner loop never flags the same index twice , so the runtime of these two loops together is O(n)

    for (int i = 0; i < arr.Length; i++)
    {
        int maxReach = i + arr[i];

        for (; unReachableIndex <= maxReach && unReachableIndex < arr.Length; unReachableIndex++)
        {

            LeftMostReacher[unReachableIndex] = i;
        }

    }

    // we just go back from the end and then reverse the path

    int index = LeftMostReacher.Length - 1;
    var st = new Stack<int>();

    while (index != -1)
    {
        st.Push(index);
        index = LeftMostReacher[index];
    }

    while (st.Count != 0)
    {
        Console.Write(arr[st.Pop()] + "  ");
    }
    Console.WriteLine();
}
static void Main ()
{
    var nrs = new[] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    Jumps(nrs);
}

Ответ 3

Вот еще одно линейное решение. Код длиннее, чем тот, который предлагается в ссылке на код, но я думаю, что это проще понять. Он основан на двух наблюдениях: количество шагов, необходимых для достижения позиции i + 1, не меньше, чем количество шагов, необходимых для достижения позиции i, и каждый элемент каждый элемент присваивает свое значение от + 1 до i + 1 ... i + a[i] сегмент.

public class Solution {
    public int jump(int[] a) {
        int n = a.length;
        // count[i] is the number of "open" segments with value i
        int[] count = new int[n];
        // the number of steps to reach the i-th position
        int[] dp = new int[n];
        Arrays.fill(dp, n);
        // toDelete[i] is the list of values of segments 
        // that close in the i-th position
        ArrayList<Integer>[] toDelete = new ArrayList[n];
        for (int i = 0; i < n; i++)
            toDelete[i] = new ArrayList<>();
        // Initially, the value is 0(for the first element).
        toDelete[0].add(0);
        int min = 0;
        count[0]++;
        for (int i = 0; i < n; i++) {
            // Finds the new minimum. It uses the fact that it cannot decrease. 
            while (min < n && count[min] == 0)
                min++;
            // If min == n, then there is no path. So we can stop.
            if (min == n)
                break;
            dp[i] = min;
            if (dp[i] + 1 < n) {
                // Creates a new segment from i + 1 to i + a[i] with dp[i] + 1 value
                count[dp[i] + 1]++;
                if (i + a[i] < n)
                    toDelete[i + a[i]].add(dp[i] + 1);
            }
            // Processes closing segments in this position.
            for (int deleted : toDelete[i])
                count[deleted]--;
        }
        return dp[n - 1];
    }
}

Анализ сложности:

• Общее количество элементов в списках toDelete составляет O(n). Это происходит потому, что в каждой позиции i добавляется не более одного элемента. Поэтому для обработки всех элементов во всех списках toDelete требуется линейное время.

• Значение min может только увеличиваться. Поэтому внутренний цикл while делает не более, чем n итераций.

• Внешний цикл for, очевидно, выполняет итерации n. Таким образом, временная сложность линейна.

Ответ 4

Вот основная интуиция в отношении вышеупомянутой проблемы: жадный подход и отдых - это требования кода.

Данный массив - Input: a [] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}.

Теперь мы начинаем с 1-го элемента, то есть я = 0 и a [i] = 1. Поэтому, увидев это, мы можем взять максимум скачок размера 1, так как у нас нет другого выбора, поэтому мы делаем это шаг.

В настоящее время мы находимся в я = 1 и a [i] = 3. Поэтому мы в настоящее время можем сделать скачок размера 3, но вместо этого мы рассмотрим все возможные прыжки, которые мы можем сделать из текущего местоположения, и достигнем максимального расстояния, которое находится в пределах (массива). Итак, каковы наши выборы? мы можем сделать скачок 1 шаг, или 2 шага или 3 шага. Итак, мы исследуем текущее местоположение для каждого скачка размера и выбираем тот, который может взять нас дальше в массив.

Как только мы решили, с какими мы придерживаемся, мы берем этот размер прыжка и обновляем наше количество прыжков, сделанное до сих пор, а также где мы можем достичь максимум и сколько шагов у нас есть сейчас, чтобы решить наш следующий шаг. И это так. Вот как мы, наконец, выбираем оптимальный вариант линейного перемещения массива. Итак, это основная идея алго, которую вы, возможно, ищете, а затем - код для работы алгоритма. Ура!

Надеюсь, что кто-то время путешествует и находит полезной интуицию!!:):П "Годы опоздали на вечеринку", - сказал Василеску Андрей. Иногда мне кажется, что мы - путешественники во времени.

Ответ 5

Простой код Python для минимального количества прыжков для достижения конечной проблемы.

ar=[1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
minJumpIdx=0
res=[0]*len(ar)
i=1
while(i<len(ar) and i>minJumpIdx):
    if minJumpIdx+ar[minJumpIdx]>=i:
        res[i]=res[minJumpIdx]+1
        i+=1
    else:
        minJumpIdx+=1
if res[-1]==0:
    print(-1)
else:
    print(res[-1])

Ответ 6

Хорошо, мне понадобилось много времени, чтобы обернуть голову вокруг алгоритма O (n), я попытаюсь объяснить логику в моей самой простой из возможных:

Для каждого "i" в массиве вы знаете с этим значением, какое значение currentFarthest вы можете получить до & также значение currentEnd, когда вы нажимаете значение currentEnd, вы знаете, что пора сделать скачок & обновить currentEnd с currentFarthest.

Картинка ниже может помочь:

Ответ 7

Я сделал это с Python. Менее сложный код с простыми терминами. Это может помочь вам.

def minJump(a):
    end=len(a)
    count=0
    i=a[0]
    tempList1=a
    while(i<=end):
        if(i==0):
            return 0
        tempList1=a[count+1:count+i+1]
        max_index=a.index(max(tempList1))
        count+=1
        i=a[max_index]
        end=end-max_index
    return count+1