OA1 12.11Due OA2 12.18Due

原帖地址:一亩三分地

从地里学了很多,来造福地里
OA1 12.11 due. debug 和逻辑题如地里所说,没什么新的。Coding题是merge 2 sorted lists。 OA1 结束后23~24 hrs 后收到OA2 邀。

work simulation还是地里的老题,但不知道正确答案。随便选了选。Coding题是 minimal path sum 和 LRU cache。Minimum sum of the path in a tree 这道题里所有节点的值都是非负的。

看地里的很多代码是Java的,这里用C++实现一下,回报地里,鄙人的代码都是优化后的,性能应该有保障。

1)
class Solution {
ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 != NULL l2 != NULL) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = (l1 == NULL) ? l2 : l1;
return dummy->next;
}
}

2)这道题下面的解法是高度优化的解法,鄙人考试时也没有想全。
int pathSum(TreeNode* root) {
if (!root){
return 0;
}
stack st;
stack stVal;
minS = 1 << 15; st.push_back(root); stVal.push_back(root->val);
while(!st.empty()) {
TreeNode* top = st.top();
int val = stVal.top();
st.pop();
stVal.pop();
if (top->left == NULL top->right == NULL) {
minS = min(minS, val);
}
if (top->right val + top->right->val < minS) { st.push_back(top->right);
stVal.push_back(val + top->right->val);
}
if (top->left val + top->left->val < minS) { st.push_back(top->left);
stVal.push_back(val + top->left->val);
}
}
return minS;
}

3)这道题也是用map记录存储位置,从而优化性能。
int cacheMiss(int array[], int len, int size) {
list store;
map::iterator> m;
int count = 0;
for (int i = 0; i < len; i++) { int val = array[i]; // hit if (m.count(val)) { store.erase(m[val]); } else { //miss count++; if (store.size() == size) { m.erase(store.back()); store.pop_back(); } } store.push_front(val); m[val] = store.begin(); } return count; } 可以关注http://codingmelon.com/2015/12/12/minimal-path-sum-from-root-to-leaves/,上面有多种方法的介绍。 强烈求大米!