如何在 Swift 的 Direction Array Reduction 挑战中正确实施堆栈

Question

我正在尝试解决 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))

我有 returns 个 ["WEST", "WEST", "WEST"] 的数组，但是，这应该返回 ["WEST", "WEST"]。我不确定如何初始化堆栈以解决此问题。我将不胜感激任何可能采取 look.I 的新眼光我也很好奇这是否是实现堆栈的最佳实践，或者是否有更好的方法来应对这一挑战。感谢任何帮助或建议。

Answer 1

对于列表中的其余元素（方向[1:]），将元素添加到堆栈如果堆栈为空或如果peek 的结果和元素不是相反的方向。否则，弹出堆栈顶部的元素并继续下一个。

size/length 方法对您的堆栈实现很有用。它会在 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))

如何在 Swift 的 Direction Array Reduction 挑战中正确实施堆栈

How to properly implement stack in Direction Array Reduction challenge in Swift

arrays

algorithm

stack

lifo

swift