當(dāng)前位置:首頁 > 公眾號(hào)精選 > CPP開發(fā)者
[導(dǎo)讀]導(dǎo)讀相信大家應(yīng)該都有搶火車票的經(jīng)驗(yàn),每年年底,這都是一場盛宴。然而你有沒有想過搶火車票這個(gè)算法是怎么實(shí)現(xiàn)的呢?其實(shí)并沒有你想的那么難。位運(yùn)算先回顧一下位運(yùn)算:12306搶票算法詳解我們以北京到西安這趟高鐵為例,比如我的路線就是從北京到西安,車上如果只剩最后一張票了,那么如果有其他...

導(dǎo)讀相信大家應(yīng)該都有搶火車票的經(jīng)驗(yàn),每年年底,這都是一場盛宴。然而你有沒有想過搶火車票這個(gè)算法是怎么實(shí)現(xiàn)的呢?其實(shí)并沒有你想的那么難。


位運(yùn)算

先回顧一下位運(yùn)算:



12306搶票算法詳解

我們以北京到西安這趟高鐵為例,比如我的路線就是從北京到西安,車上如果只剩最后一張票了,那么如果有其他人,在北京到西安這條路線之間買任何一站,那么我都是買不了票的,換句話說,對(duì)于單個(gè)座位來說,必須是起點(diǎn)到終點(diǎn)之間的所有站都沒有人買的話,那么才能被算是有票狀態(tài)。


所以我們可以嘗試用redis的bitmap結(jié)合上位操作來實(shí)現(xiàn)這種場景,以上述北京到西安為例,我們把問題簡化:


  • 比如一個(gè)火車上只有4個(gè)座位;
  • 北京到西安,一共是4站,其實(shí)是三個(gè)區(qū)間的,分別為北京->石家莊,石家莊->鄭州,鄭州->西安。

首先我們給每個(gè)區(qū)間構(gòu)建一個(gè)空位圖(0為有票,1為無票)。

接下來,比如有人買了一張從北京到西安的票。

買票這個(gè)動(dòng)作,比如被分配到的座位是編號(hào)為1的座位,那么我們直接把北京到西安的所有站,1號(hào)座位全部設(shè)置為1,如下圖:


接下來又有人買了一張從石家莊到西安的票。

比如這次分配的是座位2,那么我們把石家莊到西安的所有票全部設(shè)置為1就行了,如下圖:


如何知道還剩幾張票?

其實(shí)解決這個(gè)問題很簡單,我們直接把上述位圖做一個(gè)或操作就可以了,因?yàn)榛虿僮魇潜仨毴慷紴?,才為0。


或操作結(jié)果有幾個(gè)0,則說明還剩幾張票。


總結(jié)

其實(shí)解決這個(gè)問題主要在于位圖的構(gòu)建,因?yàn)榛疖嚻睂?duì)于某一個(gè)座位來說,只要起點(diǎn)到終點(diǎn)中間某一個(gè)區(qū)間被占用了(置為1),那么整個(gè)座位都是無效的這個(gè)特點(diǎn),很容易想到用或操作的結(jié)果來判斷買票結(jié)果,我們這里只用了4位是為了方便說明問題,實(shí)際中應(yīng)該是火車上有多少座位,位圖的長度就應(yīng)該是多少。


好了,關(guān)于搶票算法我們就介紹到這里,你有沒有g(shù)et到呢?或者你有沒有更好的實(shí)現(xiàn)方法呢?


- EOF -


本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時(shí)聯(lián)系本站刪除。

CPP開發(fā)者

234 篇文章

關(guān)注

發(fā)布文章

編輯精選

技術(shù)子站

關(guān)閉