闲的蛋疼想到火车票余票算法,假设一条线有32个站,有800个位置,现用32位的无符号数表示一条线中的一个座位,数中每个位表示某个站点,为1即表示此座位当前站已经有人坐了,0即相反,如11111000...0表示当前座位前5个站有人
现有新用户进来购买区间3到5站的票,即00111000...0,只要将此数与上面位置11111000...0做&操作,若结果大于1,即说明座位已被占用,无票可售,等于0即有票可售。
操作小于800次循环,单次时间复杂度为n,用数据3.2KB即可表示一条线路,当然实际应用中还需要考虑不同类型的票,换乘业务,座位选择,但这些都可以根据拓展。