Как правильно реализовать стек в вызове Direction Array Reduction в Swift - PullRequest
3 голосов
/ 05 февраля 2020

Я пытаюсь решить проблему кодирования в Swift. Задача состоит в том, чтобы создать функцию, которая принимает массив направлений, например: ["NORTH", "WEST", "EAST", "NORTH", "EAST", "SOUTH"]. Любые противоположные направления, которые находятся рядом друг с другом в массиве, должны быть удалены. Используя приведенный выше пример, второй и третий индексы («WEST» и «EAST») должны быть удалены. Однако последний индекс «SOUTH» должен оставаться, поскольку он не находится непосредственно рядом со значением «NORTH» в массиве.

Я пытаюсь реализовать стек для сравнения значений и не могу получить это работать правильно. Это мой первый опыт реализации стека, и я все еще привыкаю к ​​синтаксису Swift.

Мой код настроен так:

struct StringStack {
    var array: [String] = []

    func peek() -> String {
        guard let topElement = array.first else { fatalError("The Stack is empty.")}
        return topElement
    }

    mutating func pop() -> String {
        return array.removeFirst()
    }

    mutating func push(_ element: String) {
        array.insert(element, at: 0)
    }
}

func directionsReduce(_ directions: [String]) -> [String] {
    var reducedDirs = StringStack()

    reducedDirs.push(directions[1])
    for direction in directions {
        if((direction == "NORTH" && reducedDirs.peek() == "SOUTH")
            || (direction == "SOUTH" && reducedDirs.peek() == "NORTH")
            || (direction == "EAST" && reducedDirs.peek() == "WEST")
            || (direction == "WEST" && reducedDirs.peek() == "EAST")
        ) {
            reducedDirs.pop()
        } else {
            reducedDirs.push(direction)
        }
    }

    return reducedDirs.array
}

let testDirections1 = ["WEST", "WEST", "NORTH", "SOUTH", "EAST", "WEST"]
print(directionsReduce(testDirections1))

То, что у меня есть, возвращает массив из ["WEST", "WEST", "WEST"], однако, это должно возвращать ["WEST", "WEST"]. Я не уверен, как инициализировать стек, чтобы обойти это. Я был бы признателен за любые свободные sh глаза, которые могли бы взглянуть. Мне также любопытно, является ли это наилучшей практикой для реализации стека или есть лучший способ go об этой задаче. Ценю любую помощь или совет.

1 Ответ

1 голос
/ 05 февраля 2020

Для остальных элементов в списке (направления [1:]) добавьте элемент в стек , если стек пуст или , если результат peek и элемент не противоположные направления . В противном случае вытащите элемент в верхней части стека и переходите к следующему.

Метод размера / длины будет полезен для вашей реализации стека. Это обеспечило бы проверку перед peek(), чтобы предотвратить бросок fatalError

func directionsReduce(_ directions: [String]) -> [String] {
    var reducedDirs = StringStack()

    reducedDirs.push(directions[0])
    for direction in directions[1...] {
        if ((reducedDirs.length() == 0) 
             || (!areOppositeDirections(direction, reducedDirs.peek()))
        {
            reducedDirs.push(direction)
        } else {
            reducedDirs.pop()
        }
    }

    return reducedDirs.array
}

let testDirections1 = ["WEST", "WEST", "NORTH", "SOUTH", "EAST", "WEST"]
print(directionsReduce(testDirections1))

...