在线编程--41.神秘消失-阿里云开发者社区

开发者社区> 人工智能> 正文

在线编程--41.神秘消失

简介: 记录并分享自己的做题想法及源码,由于在此之前从没有使用过Java,而在线编程只能用java,因此边学编写,代码比较粗糙,欢迎提出建议,帮助蓬莱松进行改进,在此先谢谢大家啦。。。

题目

在书架上摆着一些书,这些书只有两种颜色,要么是黄色,要么是蓝色,突然某一天这些书被施了魔法,如果一本黄色和一本蓝色的书挨着,这两本书就会消失不见,然后右边的书会往左边移动,直到和左边的书挨着,如果这两本颜色不同,这两本书又会神秘消失。现在给你一个只包含A和B的字符串s(1<=|s|<=100000),其中A表示黄色的书,B表示蓝色的书,问这n本书中最多会消失多少本书。
输入一个字符串s,s中A表示黄色的书,B表示蓝色的书
输出最多会消失多少本书

分析

拿到这个题目后,先想到了最简单的方法
直接遍历: 即先遍历一遍将符合消除,然后遍历第二遍直到符合的全部消除,算了算法时间复杂度,为O(N^2),速度太慢,放弃
随之,想到了先排序,在进行发现复杂度更高。放弃。
遂仔细读题,发现这个问题更适合使用栈来做,算了一下时间复杂度为O(N),遂用之。
使用栈的坑

  • n<2
  • 消除过程中,栈空了:在栈空了,要重新赋值给目标比较变量,同时将该字符进栈。

源码

相关源码请参考:https://code.aliyun.com/xinYe/aliProgrammaCode/blob/master/41-%E7%A5%9E%E7%A7%98%E6%B6%88%E5%A4%B1.txt

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章