gg onsite

好久之前onsite

1. 给n个城市之间所有两两间的距离，然后你要按照从小到大(大小指的是城市的编号，意思就是一定要从小到大的顺序访问城市)的顺序游遍所有城市，现在你可以选择k的城市不去了，问选择不去哪几个城市可以使得总的旅程最短？返回最短的旅程。第四题题干有点绕，本质上就是从n

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

找所有paths就可以了。
自己写code稍微有点慢，所以每一轮都没有时间问follow up。onsite完十多天之后通知过了hc。

完

透你妈 赶紧来湾区给我当司机 嘻嘻

agraynel 发表于 2017-12-1 13:17
透你妈 赶紧来湾区给我当司机 嘻嘻

才不要   

请问第一题有甚么思路吗?

只想到爆力法, 本来想说考虑dp, 可是好像不太知道怎么切subproblem

谢谢

如果照lz的思路,

是不是 dfs(int cur, int k) 表示从cur 开始, 剩下k个city要走做呢?
memorize 记录  mem[cur][k]

return 从 cur开始, 剩下k city 最小的距离?

int solver(vector<vector<int>>& dist, int k){
        int res = INT_MAX;
        int m = dist.size();
        vector<vector<int>> mem(m, vector<int>(m,-1));
        for (int i = 0 ; i < m ; i++){
                res = min(res, dfs(dist, i, m-k-1, mem));
        }
        return res;
}

int dfs(vector<vector<int>>& dist, int cur, int k, vector<vector<int>>& mem){
        if (mem[cur][k]!= -1)
                return mem[cur][k];
        if (k==0){
                return 0;
        }
        int val = INT_MAX;
        for (int i = cur + 1 ; i < dist.size() ; i++){
                int tmp = dfs(dist, i , k-1);
                if (tmp < INT_MAX)
                        val = min(val,dist[cur][i] + tmp);
        }
        mem[cur][k] = val;
        return val;
}

reliveinfire 发表于 2017-12-1 16:07
如果照lz的思路,

是不是 dfs(int cur, int k) 表示从cur 开始, 剩下k个city要走做呢?

大体思路就是这样，可以加一个剩余城市小于要选的城市来提前跳出递归