菜鸡滴滴三面还是挂了
部门:橙心优选
算法题:
比如说爬山,一次往上、往下或者不走,求到达的最大高度
第一行输入分别是 总天数 和 接下来的几个位置
第2行之后的输入是 天数 和 当天的高度
8 2
2 0
7 0
输出 2
8 2
2 0
7 0
输出 2
大意就是第二天的时候位置是0,然后你可以往上走,在第4天达到2的最大位置,然后才可能第7天返回0这个位置。
如果第五天走了三步,走到了3的高度,那么就不能在第7天回到0这个位置。
8 3
2 0
7 0
8 3
输出 impossible
8 3
2 0
7 0
8 3
输出 impossible
同理,这个在第7天走到了0的位置,在第8天走到了3的位置,显然是不可能的,就直接输出impossible
大佬们有思路吗,我是用DFS+数组,但是面试官很想让我构造一个树,其实我没太get到