БФС, чтобы проверить, если путь от узла начала до конца узел не существует


Я пытаюсь решить проблему с leetcode называемые скачки игры , и это, кажется, довольно простой графической проблемы, где мы должны найти, если существует путь от начального узла к конечному узлу. Я лично всегда борюсь с такими проблемами, как эта, где графики представлены в виде массивов (вместо класса узла связи), поэтому я был бы признателен за комментарий в код, который я написал. Мое текущее решение выглядит следующим образом:

class Solution {

    public boolean canJump(int[] nums) {

        if(nums.length == 1)
            return true;

        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();

        for(Integer i = 0; i < nums.length; i++) {

            ArrayList<Integer> edges = new ArrayList<Integer>();

            int jumps = nums[i];

            if (jumps != 0) {
                for(Integer j = 1; j <= jumps; j++) {
                    edges.add(i+j);
                }
            } else {
                edges.add(-1);
            }

            graph.put(i, edges);
        }

        //we have our graph ready

        Integer target = nums.length - 1;
        System.out.println("target is : " + target);

        HashSet<Integer> visited = new HashSet<Integer>();


        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(0);

        while(!queue.isEmpty()) {
            System.out.println("queue " + queue.peek());
            visited.add(queue.peek());
            ArrayList<Integer> edges = graph.get(queue.poll());

            System.out.println("edges is : " + edges);

            for(Integer edge : edges) {

                if(!visited.contains(edge)){

                    if (edge == target) {
                        return true;
                    }

                    if(!queue.contains(edge) && edge > 0){
                        queue.add(edge);
                    }
                }
            }

        }

        return false;

    }

}

Итак, во-первых, я знаю, что я делаю некоторые избыточные операции. Прямо сейчас я создаю хранилище HashMap для хранения мой график в Node->пар ConnectionsList так просто легче для меня, чтобы визуализировать. Я знаю, что я могу просто пропустить это и просто напрямую использовать входной массив и очереди запустить свой поиск, и я буду оптимизировать этом позже.

Я бы, прежде всего, как кто-то, чтобы пойти за моей БФС реализации логики (в цикле while) и дайте мне знать, если есть что-то логически не так с моим кодом для него.

Как она стоит я прохожу 73/75 тестов на leetcode из-за тайм-аут, но я хотел бы убедиться, что мой БФС логика-это звук прежде чем я продолжу. Там, кажется, другой более простой способ решить эту проблему без БФС, но сейчас я использую это на практике реализовывать алгоритмы поиска график, я был бы признателен за обзор этой части.



Комментарии
1 ответ

Примечания:


  1. Вы должны стремиться держать левую руку типа как общие, как это возможно. Это значит HashMap<Integer, ArrayList<Integer>> graph должно быть
    Map<Integer, List<Integer>> graph.
    Это является предпочтительным для обеспечения простой замены реализаций.
    Для получения более подробной информации, почему это полезно, посмотреть на "принцип подстановки Лисков"

    Те же соображения применяются для edges и visitedхотя интересно не queue.


  2. Это значительно проще для компилятора и JVM для перебора с int счетчик и не Integer счетчик, потому что последнее требует распаковки и бокс на каждую операцию вы выполняете.

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

  4. Вы можете сэкономить кучу времени на реализацию Queue С TreeSet. С помощью Set предотвращает повторяющихся итераций, которое вы в настоящее время нет. Вы должны также быть в состоянии получить много скорости из "взахлеб" поиск, прыгать, как далеко, как вы возможно можете на каждом шагу.

Обратите внимание, что то, что я сказал в 4 тоже должно дать вам подсказку о том, как можно решить проблему без использования граф-поиск.

2
ответ дан 19 февраля 2018 в 06:02 Источник Поделиться