目录

一、练习题

二、小结

一、练习题

1. 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

package Algorithm.stack
import std.collection.*
 
public func isValid(string: String) {
    let stack = ArrayStack<String>()
 
    for (i in 0..string.toRuneArray().size) {
        let c = string.toRuneArray()[i].toString() 
        // 如果是左括号，压入栈中
        if (c == "(" || c == "{" || c == "[") {
            stack.add(c)
        } else {
        // 如果是右括号，检查栈是否为空
        if (stack.isEmpty()) {
            return false
        }   
        // 弹出栈顶元素并检查是否匹配
        let top = stack.remove().getOrThrow()
        if (!isMatchingPair(top, c)) {
            return false
        }
    }
}
    // 检查栈是否为空（所有左括号都已匹配）
    return stack.isEmpty()
}
    
func isMatchingPair(left: String, right: String): Bool {
    return (left == "(" && right == ")") ||
        (left == "{" && right == "}") ||
        (left == "[" && right == "]")
}

注意：这里使用的栈，是前面我们自己实现的顺序栈。 

测试代码

package Algorithm

main(): Int64 {
    println(isValid("()"))
    println(isValid("()[]{}"))
    println(isValid("(]"))
    println(isValid("([)]"))
    println(isValid("{[]}"))
    return 0
}

 2. 给定一个数组和滑动窗口的大小，找出所有滑动窗口里的最大值。

例如，如果输入数组是[1,3,-1,-3,5,3,6,7]，窗口大小为3，那么：

• 第一个窗口[1,3,-1]的最大值是3
• 第二个窗口[3,-1,-3]的最大值是3
• 第三个窗口[-1,-3,5]的最大值是5
• 以此类推，输出结果为[3,3,5,5,6,7]

package Algorithm.queue
import std.collection.*

public func maxSlidingWindow(nums: Array<Int64>, k: Int64): Array<Int64> { 
    let n = nums.size
    var result = Array<Int64>(n - k + 1, repeat: 0)
    let queue = ArrayQueue<Int64>()
    for (i in 0..n) {
        while (!queue.isEmpty() && queue.peek().getOrThrow() < i - k + 1) {
            queue.remove()
        }
        // 移除队列中所有小于当前元素的元素，保持队列递减
        while (!queue.isEmpty() && nums[queue.peek().getOrThrow()] < nums[i]) {
            queue.remove()
        }
        queue.add(i)
        // 当窗口形成时，记录最大值
        if (i >= k - 1) {
            result[i - k + 1] = nums[queue.peek().getOrThrow()]
        }
    }
    return result
}

测试代码

package Algorithm

main(): Int64 {
    let nums = [1, 3, -1, -3, 5, 3, 6, 7]
    let k = 3
    let result = maxSlidingWindow(nums, k)
        
    for (num in result) {
        print("${num} ")
    }
    return 0
}

二、小结

本章为大家详细的介绍了仓颉数据结构与算法中栈和队列练习题的内容，下一章，为大家带来二叉树的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！