返回信息流1. 给一个数组，一个target。数组里面元素或操作得到target。问至少拿掉哪几个元素使得永远得不到target
e.g:
int[] elements
int target
4 0100
5 0101
7 0111
8 1000
10 1010
13 1101
- -
13 1101
5 | 8 = 13, 4 | 5 | 8 = 13, 13 = 13
7 ~ 13, 5 ~ 13, 4 ~ 13
0 | 0 => 0
0 | 1 => 1
1 | 0 => 1
1 | 1 => 1
2.有一个grid，grid当中有大写字母和小写字母（大写字母为门，小写字母为锁，只有拥有了对用的小写字母比如a，才能打开大写字母比如A并通行，两者均最多26个），还有障碍物（不能走到障碍物上），有一个起点一个终点，求起点到终点的最短路径，要求需要收集到所有的锁，但是不需要开启所有的门
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #97845同步于 2019/3/30
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】请教两道面试题
hyforever
2019/3/30镜像同步13 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
第二题感觉leetcode有很类似的原题
第一题应该就是根据target的二进制表示中为1的位置，数一下数组里面有相应1且与（～target）进行与为0的数字
13为1101，就把1000，0100，0001分别进行考虑，以1000为例，8（1000）以及10（1010）有1000，但是10（1010）&0111（～target） > 0，所以1000有一个数字，之后在考虑别的数字
Integer32位，复杂度O(n)
1.因为 target为0的位上，如果数组中的元素在该位是1，那肯定不用去掉， 过滤掉这些元素。
- 再对剩余的元素的各个为1的位进行累加计数，出现次数最少的位就是要去掉的数量。
2.bfs
第一题这思路有点强，想请教下怎么想出来这种方法的，还是说有所套路可寻呢？
第二题我去找找，
谢谢了！
【 在 w350053002 的大作中提到: 】
: 第二题感觉leetcode有很类似的原题
: 第一题应该就是根据target的二进制表示中为1的位置，数一下数组里面有相应1且与（～target）进行与为0的数字
: 13为1101，就把1000，0100，0001分别进行考虑，以1000为例，8（1000）以及10（1010）有1000，但是10（1010）&0111（～target） > 0，所以1000有一个数字，之后在考虑别的数字
: ...................
第二题感觉单纯用dfs的话会造成时间和空间的极大消耗，感觉需要一些剪枝算法或者对路径算分？
【 在 lanvent 的大作中提到: 】
: 1.因为 target为0的位上，如果数组中的元素在该位是1，那肯定不用去掉， 过滤掉这些元素。
: 对剩余的元素的各个位进行累加计数，出现次数最少的位就是要去掉的数量。
: 2.bfs
微软苏州实习三面
北美某自动驾驶公司二面，签了nda，不能细说
【 在 vivian0907 的大作中提到: 】
: 只想问问这是哪里的面试题。。。
第二小 最小的为0
【 在 lanvent (lanvent) 的大作中提到: 】
: 1.因为 target为0的位上，如果数组中的元素在该位是1，那肯定不用去掉， 过滤掉这些元素。
: 对剩余的元素的各个位进行累加计数，出现次数最少的位就是要去掉的数量。
: 2.bfs