Google 实习面(gui)经

第二题感觉可以拿两个指针扫？一个扫source一个扫target，如果指向的字符相等就继续，如果不相等就分情况讨论: source指向'L'或者target指向'R'直接返回False; 剩下的情况里，source指向'R'，就递增target的指针看能不能匹配；target指向'L'，就递增source指针看能不能匹配。循环完以后查一下剩下的是不是都是'_'，是的话返回True。不知道这样行不行。。

求楼主的timeline～

第二题的第三个输入，为什么输出是false呢？

请问第二题，可以出现多个R或者L吗？还是说各只有一个？

我也遇到了第一题，其实可以不用排序，O(n)就可以做，用hashmap存，边存边更新最大值，然后返回就行。

感谢楼主分享啊

第二题可不可用两个数组分别记录从左/右边 看 当前位置最多有几个R/L。
比如先把所有L去掉，从前往后遍历
_ _ _ R _ R _ R _ _ R R   
0 0 0 1 1 2 2  2 2 2 3 4  
后面Target当前的R的个数 不能超过 上面 对应R的个数  当然target和source的R数目必须想等
L也是一样的道理

看楼上的讨论有点懵逼，
第一题难道不是O(n)就能搞定嘛？直接loop一遍collection，统计timestamp<target的各个name的个数。

第二题我的想法，定义两个变量num_L. num_R记录L和R出现的个数，同时loop source和target，由于source里的L只能向左，R只能向右，所以同时loop时一定是target里先遇到L（或者同时遇到），且一定是source里先遇到R（或者同时遇到），所以loop时遇到target[i]为L, 则num_L加一， 如果source[i]为L， 则num_L减一，如果source[i]是R，则num_R加一，如果target[i]是R，则num_R减一。若任意时刻出现num_L<0 或num_R<0，说明source走不到target，return False。这样O(n)就搞定了。

求问楼主第二轮啥叫不能jump over，这个R和L的移动范围有限制么？

求问楼主第二轮的思路到底是啥。。楼上提出的算法貌似都不对。不是没有考虑到 'R' ‘L’ 只能向固定位置移动就是没考虑到可能连续的'RR'或者没考虑到‘R’， 'L' 不能 jump over 的情况

请教另外一个同学，他的思路是首先固定L的位置，然后看看可否把R移动到相应的位置，（可以通过两根指针来做，O（N）复杂度），然后再固定R的位置，看看能否把L移到相应的位置。当然这样做起来也是比较复杂，不过至少可以证明是正确的