导读

置信大家应该都有抢火车票的教训，每年年底，这都是一场盛宴。然而你有没有想过抢火车票这个算法是怎么实现的呢？应该没有吧，咱们明天就来一一探讨。其实并没有你想的那么难

bitmap 与位运算

redis 的 bitmap 根本应用咱们之前曾经介绍过了，如果不是很相熟的敌人能够看看这里
redis bitmap 的基本操作和利用

明天在这里咱们次要是先回顾一下位运算

12306 抢票算法详解

咱们以北京到西安这趟高铁为例，比方我的路线就是从北京到西安，车上如果只剩最初一张票了，那么如果有其他人，在北京到西安这条路线之间买任何一站，那么我都是买不了票的，换句话说，对于单个座位来说，必须是终点到目的地之间的所有站，都没有人买的话，那么能力被算是有票状态。

所以咱们能够尝试用 bitmap 联合上位操作来实现这种场景，以上述北京到西安为例，咱们把问题简化

• 比方一个火车上只有 4 个座位
• 北京到西安，一共是 4 站，其实是三个区间的，别离为北京 -> 石家庄，石家庄 -> 郑州，郑州 -> 西安

首先咱们给每个区间构建一个空位图(0 为有票，1 为无票)

接下来，比方有人买了一张从北京到西安的票

买票这个动作，比方被调配到的座位是编号为 1 的座位，那么咱们间接把北京到西安的所有站，1 号座位全副设置为 1，如下图

接下来又有人买了一张从石家庄到西安的票

比方这次调配的是座位 2，那么咱们把石家庄到西安的所有票全副设置为 1 就行了，如下图

如何晓得还剩几张票？

其实解决这个问题很简略，咱们间接把上述位图做一个或操作就能够了

或操作后果有几个 0，则阐明还剩几张票。

总结

其实解决这个问题次要在于位图的构建，因为火车票对于某一个座位来说，只有终点到起点两头某一个区间被占用了 (置为 1)，那么整个座位都是有效的这个特点，很容易想到用或操作的后果来判断买票后果，咱们这里只用了 4 位是为了不便阐明问题，理论中应该是火车上有多少座位，位图的长度就应该是多少。
好了，对于抢票算法咱们就介绍到这里，你有没有 Get 到呢？或者你有没有更好的实现办法呢？