12306 抢票算法被曝光了,居然这么简单!

分享于2021年11月16日 算法
导读相信大家应该都有抢火车票的经验,每年年底,这都是一场盛宴。然而你有没有想过抢火车票这个算法是怎么实现的呢?其实并没有你想的那么难。位运算先回顾一下位运算:12306抢票算法详解我们以北京到西安这趟高铁为例,比如我的路线就是从北京到西安,车上如果只剩最后一张票了,那么如果有其他人,在北京到西安这条路线之间买任何一站,那么我都是买不了票的,换句话说,对于单个座位来说,必须是起点到终点之间的所有站都没有人买的话,那么才能被算是有票状态。所以我们可以尝试用redis的bitmap结合上位操作来实现这种场景,以上述北京到西安为例,我们把问题简化:比如一个火车上只有4个座位;北京到西安,一共是4站,其实是三个区间的,分别为北京->石家庄,石家庄->郑州,郑州->西安。首先我们给每个区间构建一个空位图(0为有票,1为无票)。接下来,比如有人买了一张从北京到西安的票。买票这个动作,比如被分配到的座位是编号为1的座位,那么我们直接把北京到西安的所有站,1号座位全部设置为1,如下图:接下来又有人买了一张从石家庄到西安的票。比如这次分配的是座位2,那么我们把石家庄到西安的所有票全部设置为1就行了,如下图:如何知道还剩几张票?其实解决这个问题很简单,我们直接把上述位图做一个或操作就可以了,因为或操作是必须全部都为0,才为0。或操作结果有几个0,则说明还剩几张票。总结其实解决这个问题主要在于位图的构建,因为火车票对于某一个座位来说,只要起点到终点中间某一个区间被占用了(置为1),那么整个座位都是无效的这个特点,很容易想到用或操作的结果来判断买票结果,我们这里只用了4位是为了方便说明问题,实际中应该是火车上有多少座位,位图的长度就应该是多少。好了,关于抢票算法我们就介绍到这里,你有没有get到呢?或者你有没有更好的实现方法呢?- EOF -推荐阅读  点击标题可跳转1、我今年89岁,刚刚拿了个物理学博士学位2、从此明白了卷积神经网络(CNN)3、这才是中国被卡脖子最严重的软件!觉得本文有帮助?请分享给更多人推荐关注「算法爱好者」,修炼编程内功点赞和在看就是最大的支持❤️