还没面试,国企HR把我删了?真的绷不住了。
一个网友投了家国企,面试八字还没一撇呢,HR先把微信加上了。上来就开始查户口,本科哪儿的、硕士哪儿的、老家哪里的、家里什么情况,问得比相亲还细。
问完来一句:同学,后续等通知。
结果这一等就是半个月,啥信儿没有。网友想着国企流程慢也正常吧,那我礼貌问一句进度。字都打好了,发送,系统直接弹出来:消息被拒收。
好家伙,面都没见上,人先被删了。
更扎心的是,后面有人说岗位可能早就有人了,加候选人只是走个流程。那这网友算啥?陪跑都算不上,顶多算流程截图里的一个小头像。
HR看完估计都不敢吱声。
面试题:柠檬水找零
收银盒里只有几张零钱,顾客排队递钱。第一个人直接掏 10 块,你不用想,找不开,后面再多钱都没用。
这题叫「柠檬水找零」,看着像模拟,其实坑就在一个地方:收到 20 的时候,到底优先找 10 + 5,还是找 5 + 5 + 5?
我一般不把这种题写复杂。因为每杯柠檬水固定 5 元,顾客只会给 5、10、20。我们手里真正需要维护的,也就两种零钱:
int five = 0;
int ten = 0;
20 不用存,收到 20 以后它不会参与后续找零。这个判断很关键,别把所有面额都塞进数组里,反而绕远了。
完整代码可以这么写:
classSolution{
publicbooleanlemonadeChange(int[] bills){
int five = 0;
int ten = 0;
for (int pay : bills) {
if (pay == 5) {
five++;
continue;
}
if (pay == 10) {
if (five == 0) {
returnfalse;
}
five--;
ten++;
continue;
}
// pay == 20
if (ten > 0 && five > 0) {
ten--;
five--;
} elseif (five >= 3) {
five -= 3;
} else {
returnfalse;
}
}
returntrue;
}
}
这里我第一眼会盯住 pay == 20 这一段。
为什么先用 10 + 5?
因为 5 块钱比 10 块钱更紧缺。
10 块钱只能在找 20 的时候用,而且必须搭配一张 5。 5 块钱就不一样了,找 10 要用它,找 20 也要用它。
所以收到 20 的时候,如果手里有一张 10 和一张 5,就别傻乎乎拿三张 5 出去。三张 5 一旦没了,后面来一个 10 可能直接崩。
拿这个队列走一遍:
int[] bills = {5, 5, 10, 20, 10};
过程大概是这样:
收到 5 :five=1, ten=0
收到 5 :five=2, ten=0
收到 10 :five=1, ten=1
收到 20 :优先找 10+5,five=0, ten=0
收到 10 :没有 5,找不开
所以结果是 false。
有些人写这题,会把每次付款、找零都拆成一个很通用的收银系统,还搞一个 Map<Integer, Integer>。不是不能写,但这题没必要。面额就三个,找零规则也死,写成两个计数器最稳。
再看一个容易误判的:
int[] bills = {5, 5, 5, 10, 20};
跑到 20 的时候,手里是:
five=2, ten=1
这时候能找 10 + 5,找完还剩一张 5,没问题,返回 true。
这题的贪心味道不重,但判断顺序很重要。别想着“反正都是找 15”,15 的组合不一样,后面对队列的影响就不一样。
最后再补一句:这类题不要上来背模板。先把收银盒里有什么钱想清楚,再看哪种钱最稀缺。能保住 5,就尽量保住 5。