狗狗加面面经【2016-10-13】

printf_ll · 2016-10-14 23:45:15

hezhifeng850207 发表于 2016-10-14 23:01
第二题只能backtracking，不能用dp或者memorization?

它只要考虑到所有排列的情况就可以了吧，dp要存储什么呢？

黄豆沙君 · 2016-10-14 23:52:11

printf_ll 发表于 2016-10-14 13:15
你怎么会认出我的！

因为！我聪明！

jennyEternal · 2016-10-19 13:37:25

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

xuzonghan66 · 2016-10-19 15:48:47

第二题：

public List<Integer> getNumbers(int[] digits, int maxNumber) {
List<Integer> result = new ArrayList<Integer>();
if(digits.length == 0) return result;
Arrays.sort(digits);
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(0);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
int previous = queue.poll();
for(int j = 0; j < digits.length; j++){
int current = previous * 10 + digits[j];
if(current <= maxNumber && current != 0){
queue.add(current);
result.add(current);
}
}
}
}
if(digits[0] == 0) result.add(0, 0); // corner case when there is 0 in digits array
return result;
}

复制代码

jennyEternal · 2016-10-20 12:17:03

楼主加油！

syjohnson · 2016-10-31 09:14:30

请问bitmap是如何存储达到节省空间的呢

zzgzzm · 2016-10-31 09:51:47

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

zzgzzm · 2016-10-31 10:01:20

第一题：若比较2个hashset是否时间复杂度就成了O(N1*N2)了？我是直接在一个hashset中看每个id是否在另外一个hashset中, O(N1+N2)

vector<unordered_set<int>> getLeavingAndNew(unordered_set<int>& day1, unordered_set<int>& day2) {
vector<unordered_set<int>> res(2); // 0-index list for leaving employee
// 1-index list for new employee
for (int id : day1) if (!day2.count(id)) res[0].insert(id); // O(N1)
for (int id : day2) if (!day1.count(id)) res[1].insert(id); // O(N2)
return res;
}

复制代码

zzgzzm · 2016-10-31 10:39:55

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

syjohnson · 2016-10-31 12:12:56

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式