您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

12306 售票演算法實戰：Java 位運算實現座位分配與搶票邏輯

編輯：Java 綜合教學

12306 售票演算法實戰：Java 位運算實現座位分配與搶票邏輯

基於前文理論分析，本文提供 Java 程式碼實踐 12306 售票核心演算法，採用位運算（BitMap）高效管理座位狀態。

核心類別設計

Train（列車資訊）

public class Train {
    private String trainNo;           // 車次號
    private int stationNum;           // 車站數量
    private Map<String, Integer> seatTotalNum; // 各座位類型數量
    private String fromDate;          // 發車日期
    // getter/setter 略
}

Ticket（票務實體）

public class Ticket {
    private String ticketFlag;        // 位圖標記（BigInteger 字串）
    private String ticketType;        // 座位類型
    private int saleChannel;          // 銷售渠道
    private String trainNo;           // 車次號
    private String guid;              // 唯一標識
    private String fromDate;          // 發車日期
    // getter/setter 略
}

Order（訂單實體）

public class Order {
    private String orderId;
    private String ticketGuid;        // 關聯票據 ID
    private String ticketFlag;        // 訂票位圖
    private String seatType;
    private String fromDate;
    private String trainNO;
    private int saleChannel;
    // getter/setter 略
}

核心演算法：CommonUtil 工具類

1. 初始化列車票據

public static List<Ticket> initTicketList(Train train) {
    List<Ticket> result = new ArrayList<>();
    Map<String, Integer> seatMap = train.getSeatTotalNum();
    for (Entry<String, Integer> entry : seatMap.entrySet()) {
        int ticketSize = entry.getValue();
        String ticketType = entry.getKey();
        for (int i = 0; i < ticketSize; i++) {
            Ticket ticket = new Ticket();
            ticket.setSaleChannel((int)(Math.random() * 10) % 8);
            ticket.setTicketType(ticketType);
            ticket.setGuid(UUID.randomUUID().toString());
            ticket.setFromDate(train.getFromDate());
            ticket.setTicketFlag(initTicketFlag(train)); // 初始全 0 位圖
            ticket.setTrainNo(train.getTrainNo());
            result.add(ticket);
        }
    }
    return result;
}

2. 建立區間位圖

public static String buildTicket(int startStation, int stationNum) {
    BigInteger temp = BigInteger.ZERO;
    for (int j = startStation; j < stationNum; j++) {
        temp = temp.or(buildSingleStationTicket(j));
    }
    return temp.shiftRight(1).toString(); // 右移 1 位對齊
}

例如 18 站，第 1 站到第 2 站對應位圖 1，第 1 站到第 3 站對應 11（二進制），以此類推。

3. 判斷可否售票（核心邏輯）

private static boolean canTicket(BigInteger fromTicket, BigInteger toTicket) {
    // A = ~(~A | B)  等價於 (A & B) == 0
    // 即：現有佔用位圖 與 請求區間位圖 無交集
    return fromTicket.equals(fromTicket.not().or(toTicket).not());
}

位運算精髓：fromTicket 記錄已售區間（1 表已售），toTicket 為請求區間。若 (fromTicket & toTicket) == 0 則無衝突，可售票。

4. 執行售票（原子更新）

public static Order createOrderByCondition(String ticketStr, List<Ticket> ticketList, Map condition) {
    for (Ticket ticket : ticketList) {
        BigInteger toTicket = new BigInteger(ticketStr);
        BigInteger fromTicket = new BigInteger(ticket.getTicketFlag());
        if (canTicket(fromTicket, toTicket) 
                && ticket.getTicketType().equals(condition.get("ticketType"))) {
            Order order = new Order();
            order.setOrderId(UUID.randomUUID().toString());
            order.setSeatType(ticket.getTicketType());
            order.setTicketFlag(toTicket.toString());
            order.setTrainNO(ticket.getTrainNo());
            order.setFromDate(ticket.getFromDate());
            order.setSaleChannel(ticket.getSaleChannel());
            order.setTicketGuid(ticket.getGuid());
            // 更新票據位圖：A = A | B
            ticket.setTicketFlag(fromTicket.or(toTicket).toString());
            return order;
        }
    }
    return null;
}

主程式測試

public class MainTest {
    public static void main(String[] args) {
        Train train = new Train();
        train.setTrainNo("G1234");
        train.setFromDate("2024-01-15");
        train.setStationNum(18);
        Map<String, Integer> seatMap = new HashMap<>();
        seatMap.put("商務座", 500);
        seatMap.put("一等座", 1000);
        seatMap.put("二等座", 2000);
        train.setSeatTotalNum(seatMap);

        List<Ticket> ticketList = CommonUtil.initTicketList(train);
        List<Order> orderResult = new ArrayList<>();

        long beginTime = System.currentTimeMillis();
        // 模擬逐站購票：第1站→第2站、第2站→第3站...
        for (int j = 0; j < train.getStationNum() - 1; j++) {
            String ticketStr = CommonUtil.buildTicket(j, train.getStationNum());
            List<Order> tempList = CommonUtil.createOrderList(ticketStr, ticketList, train);
            orderResult.addAll(tempList);
        }
        long endTime = System.currentTimeMillis();

        System.out.println("生成訂單 " + orderResult.size() + " 筆，耗時 " + (endTime - beginTime) + " ms");
        System.out.println("每秒處理 " + new BigDecimal(orderResult.size()).multiply(new BigDecimal(1000))
                .divide(new BigDecimal(endTime - beginTime), 0, BigDecimal.ROUND_HALF_DOWN) + " 筆");
    }
}