七.Deque的应用案例-回文检查

逃离我推掉我的手 2023-02-17 14:53 85阅读 0赞

原文链接：https://www.cnblogs.com/bobo-zhang/p/10525545.html

#  #

[ 7.Deque的应用案例-回文检查 ][7.Deque_-_]

</h1>
            <div class="clear"></div>
            <div class="postBody">

\- 回文检测：设计程序，检测一个字符串是否为回文。

\- 回文：回文是一个字符串，读取首尾相同的字符，例如，`radar toot madam`。

\- 分析：该问题的解决方案将使用 deque 来存储字符串的字符。我们从左到右处理字符串，并将每个字符添加到 deque 的尾部。在这一点上，deque 像一个普通的队列。然而，我们现在可以利用 deque 的双重功能。 deque 的首部保存字符串的第一个字符，deque 的尾部保存最后一个字符。我们可以直接删除并比较首尾字符，只有当它们匹配时才继续。如果可以持续匹配首尾字符，我们最终要么用完字符，要么留出大小为 1 的deque，取决于原始字符串的长度是偶数还是奇数。在任一情况下，字符串都是回文。

![1489694-20190313192503327-1359022105.png][]

![复制代码][Image 1]

from basic.deque import Deque

def palchecker(aString):  
chardeque = Deque()

</span><span style="color: #0000ff;">for</span> ch <span style="color: #0000ff;">in</span><span style="color: #000000;"> aString:
        chardeque.addRear(ch)
    
    stillEqual </span>=<span style="color: #000000;"> True
    
    </span><span style="color: #0000ff;">while</span> chardeque.size() > 1 <span style="color: #0000ff;">and</span><span style="color: #000000;"> stillEqual:
        first </span>=<span style="color: #000000;"> chardeque.removeFront()
        last </span>=<span style="color: #000000;"> chardeque.removeRear()
        </span><span style="color: #0000ff;">if</span> first !=<span style="color: #000000;"> last:
            stillEqual </span>=<span style="color: #000000;"> False
    
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> stillEqual

print(palchecker(“lsdkjfskf”))  
print(palchecker(“radar”))

![复制代码][Image 1]

分类: [数据结构+算法][Link 1]

好文要顶 关注我 收藏该文 ![icon_weibo_24.png][] ![wechat.png][]

[![20190729093950.png][]][20190729093950.png 1]

[波晓张][20190729093950.png 1]  
[关注 - 2][- 2]  
[粉丝 - 542][- 542]

\+加关注

<div class="clear"></div>
    <div id="post_next_prev">
    
    <a href="https://www.cnblogs.com/bobo-zhang/p/10525482.html" class="p_n_p_prefix">« </a> 上一篇：    <a href="https://www.cnblogs.com/bobo-zhang/p/10525482.html" title="发布于 2019-03-13 19:14">6.基本数据结构-双端队列（Deque）</a>
    <br>
    <a href="https://www.cnblogs.com/bobo-zhang/p/10529330.html" class="p_n_p_prefix">» </a> 下一篇：    <a href="https://www.cnblogs.com/bobo-zhang/p/10529330.html" title="发布于 2019-03-14 12:18">8.基本数据结构-顺序表和链表</a>

posted @ 2019-03-13 19:26  [波晓张][Link 2]  阅读( 230)  评论( 0)  [编辑][Link 3]  收藏

</div>

刷新评论 刷新页面 返回顶部

注册用户登录后才能发表评论，请 登录 或 注册， [访问][Link 4] 网站首页。

[【推荐】了解你才能更懂你，博客园首发问卷调查，助力社区新升级][Link 5]  
[【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库][50_VC_ _CAD_GIS]  
[【推荐】阿里专家五年方法论总结！技术人如何实现职业突破？][Link 6]

[7.Deque_-_]: https://www.cnblogs.com/bobo-zhang/p/10525545.html
[1489694-20190313192503327-1359022105.png]: https://img2018.cnblogs.com/blog/1489694/201903/1489694-20190313192503327-1359022105.png
[Image 1]: 
[Link 1]: https://www.cnblogs.com/bobo-zhang/category/1417180.html
[icon_weibo_24.png]: https://common.cnblogs.com/images/icon_weibo_24.png
[wechat.png]: https://common.cnblogs.com/images/wechat.png
[20190729093950.png]: https://pic.cnblogs.com/face/1489694/20190729093950.png
[20190729093950.png 1]: https://home.cnblogs.com/u/bobo-zhang/
[- 2]: https://home.cnblogs.com/u/bobo-zhang/followees/
[- 542]: https://home.cnblogs.com/u/bobo-zhang/followers/
[Link 2]: https://www.cnblogs.com/bobo-zhang/
[Link 3]: https://i.cnblogs.com/EditPosts.aspx?postid=10525545
[Link 4]: https://www.cnblogs.com/
[Link 5]: https://www.wenjuan.com/s/3uIjeq0/
[50_VC_ _CAD_GIS]: http://www.ucancode.com/index.htm
[Link 6]: https://developer.aliyun.com/article/714139?utm_content=g_1000088940