美文网首页Aha! Algorithms
Aha! Algorithms - Stack

Aha! Algorithms - Stack

作者: su3 | 来源:发表于2017-03-17 06:51 被阅读0次

    《啊哈!算法》第 2 章第 2 节,栈的 Swift 实现。

    问题

    判断字符串是否回文

    解决

    将字符串前半部分入栈,然后依次出栈,与后半部分字符一一比对。

    var stk = ""
    let str = "xybyx"
    let len = str.characters.count
    let mid = len / 2 - 1 //字符串中点索引值
    
    var next: Int
    
    var top = 0 //栈的初始化,0表示栈中为空
    
    //将 mid 前的字符依次入栈
    for i in 0...mid {
        let c = str[str.index(str.startIndex, offsetBy: i)]
        stk = stk + String(c)
        top += 1 //每添加一个字符串 top + 1
    }
    print("\(stk)")
    
    //判断字符串长度是奇数还是偶数,找出mid之后进行匹配的起始索引值
    next = (len % 2 == 0) ? mid + 1 : mid + 2
    
    //依次出栈,逐一对比 mid 后的字符
    for i in next...(len - 1) {
        let s = stk[stk.index(stk.startIndex, offsetBy: top-1)]
        let a = str[str.index(str.startIndex, offsetBy: i)]
        print("s:\(s), a:\(a)")
        if s != a {
            break
        }
        top -= 1
    }
    
    //如果 top 为 0 说明栈内所有字符都被一一匹配了
    print("\(top==0)")
    

    代码在 GitHub

    相关文章

      网友评论

        本文标题:Aha! Algorithms - Stack

        本文链接:https://www.haomeiwen.com/subject/wlwsnttx.html