Блог

Я столкнулся с вопросом во время генератора вопросов типа timed leetcode и был разочарован, что не смог решить 100% тестовых примеров за пределами некоторых начальных входных данных.

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

Например, тест массива = [[3,5],[4,2][5,2]]’ может быть отсортирован так, чтобы test[0] располагался рядом с test[2], который затем может совпадать с test[1]. Конечный результат — тест = [[3,5],[5,2][2,4]].

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

Ниже приведен пример отправки исходного кода, который не удался для последующих тестовых случаев:

 // base test case
test1 = [[3,5],[5,1],[2,7],[1,4],[4,2],[7,0]]

//starting node shift test case
test2 = [[5,1],[2,7],[1,4],[4,2],[7,0],[3,5]]

//multiple node possibilities test case
test3 = [[3,5],[5,1],[2,7],[1,4],[4,2],[9,5]]



function organizer(arr) {
    let temp = arr.shift()
    let result = [temp[0], temp[1]]
    
    while (arr.length) {
        for (let i = 0; i < arr.length; i  ) {
            let current = arr[i]
            
            if (current[0] === result[result.length - 1]) {
                result.push(current[1])
                arr = arr.slice(0, i).concat(arr.slice(i   1))
            } else if (current[1] === result[result.length - 1]) {
                result.push(current[0])
                arr = arr.slice(0, i).concat(arr.slice(i   1))
            }
        }
    }
    
    return result
}
 

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

Чего мне здесь не хватает?

Представьте себе граф, в котором каждое число является вершиной, а каждый массив — ребром между вершинами, соответствующими его начальному и конечному номерам.

Задача состоит в том, чтобы найти эйлеровский путь через этот граф: https://en.wikipedia.org/wiki/Eulerian_path . Это путь, который пересекает каждое ребро ровно один раз.

Такой путь может существовать только в том случае, если граф связан и в графе ровно 0 или 2 вершины, имеющие нечетную степень. Когда это так, путь может быть найден за линейное время.

В связанной статье есть более подробное объяснение, но в основном:

• Если есть 2 вершины с нечетной степенью, найдите путь между ними.
• Остальная часть графика разлагается на непересекающиеся по краям циклы, которые затем могут быть объединены друг с другом и с путем выше в любых общих вершинах, чтобы создать один длинный путь.