火车票 查询问题 针对12306设计一个快速的查询系统
题目
火车票 查询问题 针对12306设计一个快速的查询系统
这个网上看到的，好像是百度的一道面试题
解析
思想就是将火车票区间的每个站按位映射，然后通过位操作法来查询，这种方式应该比较快，并且存储比较小
比如宁波到上海的高铁G7518有7个站：宁波->余姚北->绍兴北->杭州东->桐乡->嘉善南->上海虹桥
那么这趟车的一张票可以用0X7F来存储：01111111，低位表示出发，高位表示终止
那么我如果需要查询的话：查宁波到杭州东就为:00000111（第4站杭州东站只作为达到之用，不会占用其他票，所以置0即可），然后这两个数做一个与操作就可以，如果与操作之后的值还是00000111的话，就表示有票
还有购买的话 只需要做抑或操作即可,01111111^00000111=01111000，这样就表示余票就只有杭州东到上海虹桥的票了
有了，有这种思路之后，可以简单的看几个代码片段
查询票的构建
1 | /** |
查票的时候往往是一个起始站，还有一个到达站，这里我们就要构建乘车区间的位置为1
注意：到达站只做到达之用，并不是经过它，为了顺利让到达站还可以作为其他票的起始点，所以这里达到站不置1
同时为了方法无法找到对应的区间，所以这里要先判断一下
查询
查询只需要进行一个与操作即可，并且不需要改变原数据1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
* 查询是否有票
* @param start
* @param end
* @return
*/
public State query(String start,String end)
{
return this.query(this.buildTicket(start, end));
}
private State query(int qTicket)
{
if(qTicket==-1)
return State.ERROR;
return (rTicket&qTicket)==qTicket?State.SUCCESS:State.FAILED;//如果进行与操作之后值还是查询票的数据 就表示有票
}
购买
购买时需要改变原存储数据，这里只需要进行异或操作即可，将购买区间的位置01
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
* 买票操作
* @param start
* @param end
* @return
*/
public State buy(String start,String end)
{
int qTicket=this.buildTicket(start, end);
State state=this.query(qTicket);
if(state==State.SUCCESS)
{
this.rTicket^=qTicket;//进行异或操作 将票买了
}
return state;
}
退票
退票操作起始也需要进行或运算，将原来置0的的位置置1即可，不过为了安全，在或运算之前先判断要退的票是否是该票区间的位都已经置01
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* 退票操作
* @param start
* @param end
* @return
*/
public State refund(String start,String end)
{
int qTicket=this.buildTicket(start, end);
/**
* 1100010
* 0011100
* 这里是为了判断退票的区间在余票中是否被正好买掉
*/
if((this.rTicket|qTicket)-this.rTicket==qTicket)
{
this.rTicket|=qTicket;//将票归还
return State.SUCCESS;
}else{
return State.ERROR;//发生意外错误了
}
}
全部贴上来
全部的代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187/**
* 火车票 查询问题 针对12306设计一个快速的查询系统
* 思想就是将火车票区间的每个站按位映射，然后通过位操作法来查询
* 注：本代码只是演示了查询的流程 关于同步方面并未考虑
* @author yanyl
*
*/
public class TrainTickets {
/**
* 一个宁波到上海的高铁为例
* 每一个元素都是表示停靠站点
*/
private final HashMap<String,Integer> STATION_MAP;
/**
* 和STATION_MAP一样的信息
*/
private final String[] STATION_ARRAY={"宁波","余姚北","绍兴北","杭州东","桐乡","嘉善南","上海虹桥"};
public TrainTickets(){
//初始化一下站点信息
STATION_MAP=new HashMap<String,Integer>(){
{
for(int i=0;i<STATION_ARRAY.length;i++)
{
put(STATION_ARRAY[i],i);
}
}
};
}
/**
* 01111111 低位表示起始 高位表示终止 一共7站
*/
private int rTicket=0x7F;
public enum State{
/**
* 成功标志 有票 或者购买成功
*/
SUCCESS,
/**
* 失败标志 无票 或者购买失败
*/
FAILED,
/**
* 错误标志 可能使两个站点不存在
*/
ERROR;
}
/**
* 查询是否有票
* @param start
* @param end
* @return
*/
public State query(String start,String end)
{
return this.query(this.buildTicket(start, end));
}
private State query(int qTicket)
{
if(qTicket==-1)
return State.ERROR;
return (rTicket&qTicket)==qTicket?State.SUCCESS:State.FAILED;//如果进行与操作之后值还是查询票的数据 就表示有票
}
/**
* 买票操作
* @param start
* @param end
* @return
*/
public State buy(String start,String end)
{
int qTicket=this.buildTicket(start, end);
State state=this.query(qTicket);
if(state==State.SUCCESS)
{
this.rTicket^=qTicket;//进行异或操作 将票买了
}
return state;
}
/**
* 退票操作
* @param start
* @param end
* @return
*/
public State refund(String start,String end)
{
int qTicket=this.buildTicket(start, end);
/**
* 1100010
* 0011100
* 这里是为了判断退票的区间在余票中是否被正好买掉
*/
if((this.rTicket|qTicket)-this.rTicket==qTicket)
{
this.rTicket|=qTicket;//将票归还
return State.SUCCESS;
}else{
return State.ERROR;//发生意外错误了
}
}
/**
* 根据出发和达到站构建票
* @param start
* @param end
* @return -1表示没有这些站点
*/
private int buildTicket(String start,String end)
{
if(!STATION_MAP.containsKey(start) || !STATION_MAP.containsKey(end))
{
return -1;//表示没有这些站点 或者站点名字出错
}
int si=STATION_MAP.get(start),ei=STATION_MAP.get(end);
int qTicket=0;
while(si<ei)
{
qTicket|=0x1<<si;//在相应的位置上置1 注意 达到站是不置1
si++;
}
return qTicket;
}
/**
* 获取余票状态
* @return
*/
public String remaining()
{
StringBuilder sb=new StringBuilder();
boolean cc=false;//false 表示前一站已经被买了
sb.append("余票状态：");
for(int i=0;i<STATION_ARRAY.length;i++)
{
int mark=0x1<<i;
if((this.rTicket&mark)==mark)
{
if(cc)
{
sb.append("->");
}else{
sb.append(" ");
}
sb.append(STATION_ARRAY[i]);
cc=true;
}
else
cc=false;
}
return sb.toString().trim();
}
public static void main(String[] args) {
TrainTickets tt=new TrainTickets();
System.out.println(tt.remaining());
System.out.println("查询 宁波->杭州南:"+tt.query("宁波","杭州南"));
System.out.println("查询 宁波->杭州东:"+tt.query("宁波","杭州东"));
System.out.println("购买 宁波->杭州东:"+tt.buy("宁波","杭州东"));
System.out.println(tt.remaining());
System.out.println("购买 宁波->杭州东:"+tt.buy("宁波","杭州东"));
System.out.println("购买 宁波->绍兴北:"+tt.buy("宁波","绍兴北"));
System.out.println("购买 绍兴北->桐乡:"+tt.buy("绍兴北","桐乡"));
System.out.println("购买 杭州东->桐乡:"+tt.buy("杭州东","桐乡"));
System.out.println(tt.remaining());
System.out.println("退票 宁波->杭州东:"+tt.refund("宁波","杭州东"));
System.out.println(tt.remaining());
System.out.println("购买 宁波->杭州东:"+tt.buy("宁波","杭州东"));
}
}
最后的测试运算结果为：
余票状态： 宁波->余姚北->绍兴北->杭州东->桐乡->嘉善南->上海虹桥
查询 宁波->杭州南:ERROR
查询 宁波->杭州东:SUCCESS
购买 宁波->杭州东:SUCCESS
余票状态： 杭州东->桐乡->嘉善南->上海虹桥
购买 宁波->杭州东:FAILED
购买 宁波->绍兴北:FAILED
购买 绍兴北->桐乡:FAILED
购买 杭州东->桐乡:SUCCESS
余票状态： 桐乡->嘉善南->上海虹桥
退票 宁波->杭州东:SUCCESS
余票状态： 宁波->余姚北->绍兴北 桐乡->嘉善南->上海虹桥
购买 宁波->杭州东:SUCCESS
心细的小伙伴可以发现最后一次余票查询有bug，是的，应该有绍兴北到杭州东的票，不过这里只是显示问题而已，修改remaining()方法即可，因为看最后一条记录也的确都是可以购买到得
本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权
