近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2479|回复: 1
收起左侧

OA1 12.11Due OA2 12.18Due

[复制链接] |试试Instant~ |关注本帖
xiaobao9 发表于 2015-12-13 12:40:46 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Amazon - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
从地里学了很多,来造福地里
OA1 12.11 due. debug 和逻辑题如地里所说,没什么新的。Coding题是merge 2 sorted lists。 OA1 结束后23~24 hrs 后收到OA2 邀。
. 1point3acres.com/bbs
work simulation还是地里的老题,但不知道正确答案。随便选了选。Coding题是 minimal path sum 和 LRU cache。Minimum sum of the path in a tree 这道题里所有节点的值都是非负的。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
看地里的很多代码是Java的,这里用C++实现一下,回报地里,鄙人的代码都是优化后的,性能应该有保障。
. more info on 1point3acres.com
1)
class Solution {
        ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
                ListNode* dummy = new ListNode(0);.1point3acres缃
                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;
        }
}

. 1point 3acres 璁哄潧
2)这道题下面的解法是高度优化的解法,鄙人考试时也没有想全。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
int pathSum(TreeNode* root) {. From 1point 3acres bbs
        if (!root){.1point3acres缃
                return 0;
        }
        stack<TreeNode*> st;. from: 1point3acres.com/bbs
        stack<int> 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);
                }. from: 1point3acres.com/bbs
                if (top->left && val + top->left->val < minS) {
. more info on 1point3acres.com                        st.push_back(top->left);-google 1point3acres
                        stVal.push_back(val + top->left->val);. visit 1point3acres.com for more.
                }
        }
        return minS;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}.鐣欏璁哄潧-涓浜-涓夊垎鍦


3)这道题也是用map记录存储位置,从而优化性能。
int cacheMiss(int array[], int len, int size) {
        list<int> store; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        map<int, list<int>::iterator> m;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        int count = 0;
        for (int i = 0; i < len; i++) {. more info on 1point3acres.com
                int val = array[i];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                // hit. Waral 鍗氬鏈夋洿澶氭枃绔,
                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/  ,上面有多种方法的介绍。

强烈求大米
水逼一枚 发表于 2015-12-15 00:28:46 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主你发的link那个min path sum的递归解法是有BUG的。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-26 01:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表