首先實現(xiàn)一個順序存儲的棧。
struct MyStack<T> {
/// 聲明一個泛型數(shù)組，用于存儲棧中的元素(棧結(jié)構(gòu)的后備存儲器)
private var elements = [T]()
/// 返回棧結(jié)構(gòu)中元素的個數(shù)
public var count: Int {
// 返回數(shù)組elements中的元素個數(shù)
return elements.count
}
/// 獲取或者設(shè)置棧的存儲容量
public var capacity: Int {
// 獲取棧的存儲容量
get {
// 返回數(shù)組elements的容量
return elements.capacity
}
// 設(shè)置棧的最小容量
set {
// 設(shè)置數(shù)組elements的最小容量
elements.reserveCapacity(newValue)
}
}
/// 初始化方法(創(chuàng)建棧實例)
public init() {}
/// 使用push方法執(zhí)行入棧操作
public mutating func push(element: T) {
// 判斷棧是否已滿
if count == capacity {
fatalError("棧已滿，不能再執(zhí)行入棧操作！")
}
// 使用數(shù)組的append()方法將元素添加到數(shù)組elements中
self.elements.append(element)
}
/// 使用pop方法執(zhí)行出棧操作
@discardableResult
public mutating func pop() -> T? {
// 判斷棧是否已空
if count == 0 {
fatalError("棧已空，不能再執(zhí)行出棧操作！")
}
// 移除數(shù)組elements的最后一個元素
return elements.popLast()
}
/// 返回棧頂元素
public func top() -> T? {
// 返回數(shù)組elements的最后一個元素(但是不移除該元素)
return elements.last
}
/// 清空棧中所有的元素
public mutating func clear() {
// 清空數(shù)組elements中所有的元素
elements.removeAll()
}
/// 判斷棧是否為空
public func isEmpty() -> Bool {
// 判斷數(shù)組elements是否為空
return elements.isEmpty
}
/// 判斷棧是否已滿
public func isFull() -> Bool {
// 對數(shù)組的存儲情況進行判斷
if count == 0 {
// 如果數(shù)組為空，則表示棧還未存儲數(shù)據(jù)元素
return false
} else {
// 如果數(shù)組不為空，則返回數(shù)組的存儲容量
// 然后再根據(jù)實際存儲情況判斷棧是否已滿
return count == elements.capacity
}
}
}
一。括號匹配檢驗
假設(shè)表達式中允許包含兩種括號：圓括號和方括號，其嵌套順序隨意，即()或者[([][])]都是正確的，而這[(]或者(()])或者([())都是不正確的格式，檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述，例如，考慮以下括號的判斷：[([][])]
func checkSymbol(orgStr:String) -> Bool {
let leftArr = ["(", "["]
let rightArr = [")", "]"]
let pairValue = ["(":")", "[":"]"]
var stack:MyStack = MyStack<String>()
stack.capacity = orgStr.count
for char in orgStr {
let s = String(char)
if leftArr.contains(s) {
//左邊的括號
stack.push(element: s)
}else if rightArr.contains(s) {
//右邊的括號
if stack.isEmpty() {
//判斷棧是否為空
return false
}else {
let targetValue = pairValue[stack.top()!]
if s == targetValue {
return true
}else {
return false
}
}
}
}
return stack.isEmpty()
}
二。每日氣溫
根據(jù)每日氣溫列表，請重新生成一個列表，對應(yīng)位置的輸入時你需要再等待多久溫度才會升高超過該日的天數(shù)。如果之后都不會升高，請在該位置0來代替。例如，給定一個列表temperatures = [73,74,75,71,69,72,76,73]，你的輸出應(yīng)該是[1,1,4,2,1,1,0,0]。提示：氣溫列表長度的范圍是[1,30000]。每個氣溫的值的均為華氏度，都是在[30,100]范圍內(nèi)的整數(shù)
func temperature(orgTemArr:[Int]) -> [Int] {
var stack = MyStack<Int>()
stack.capacity = orgTemArr.count
var resultArr:[Int] = Array.init(repeating: 0, count: orgTemArr.count)
for (index, value) in orgTemArr.enumerated() {
if stack.isEmpty() {
//當(dāng)棧為空
stack.push(element: index)
}else {
//當(dāng)當(dāng)前值小于等于棧頂
if value <= orgTemArr[stack.top()!] {
stack.push(element: index)
}else {
while !stack.isEmpty(){
//如果當(dāng)前值始終大于棧頂，進行對結(jié)果數(shù)組的賦值。
if value > orgTemArr[stack.top()!] {
let top = stack.top()!
resultArr[top] = index - top
stack.pop()
}else {
break
}
}
}
}
stack.push(element: index)
}
return resultArr
}
print("temper ==== \(temperature(orgTemArr: [73,74,75,71,69,72,76,73]))")
運行結(jié)果
image.png
三。爬樓梯
假設(shè)你正在爬樓梯。需要n階你才能到達樓頂。每次你可以爬1或2個臺階。你有多少種不同的方法可以爬到樓頂呢？注意：給定n是一個正整數(shù)
func climbStairs(n:Int) -> Int {
if n == 0 {
return 0
}else if n == 1 {
return 1
}else if n == 2 {
return 2
}
return climbStairs(n: n-1)+climbStairs(n: n-2)
}
