一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1827|回复: 14
收起左侧

Google電面

[复制链接] |试试Instant~ |关注本帖
头像被屏蔽
sammsiontir 发表于 2016-7-20 05:27:48 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

本帖被以下淘专辑推荐:

readman 发表于 2016-7-20 10:15:46 | 显示全部楼层
int onebit(int x) {. Waral 鍗氬鏈夋洿澶氭枃绔,
    int count = 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
    while(x>0) {
        count ++;
        x = x & (x-1);
    }
    return count;
}
.1point3acres缃
for(i ->[0:12])
for(j ->[0:59]). Waral 鍗氬鏈夋洿澶氭枃绔,
if(onebit(i) > 4)
continue;
if(onebit(j) > 6)
continue;
else
if(onebit(i)+onebit(j) == x)
res.add(i)
res.add(j);
回复 支持 4 反对 0

使用道具 举报

Peripatetic 发表于 2016-7-20 09:54:17 | 显示全部楼层
楼主请问dp是怎么做的?
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-20 10:06:27 | 显示全部楼层
这题dp??? 是不是你backtrack剪枝有问题....
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-7-20 10:13:07 | 显示全部楼层
这道题怎么用DP做?我之前6月初看到过有人po这道题,感觉只会backtracking解法
回复 支持 反对

使用道具 举报

ghost33 发表于 2016-7-20 10:53:01 | 显示全部楼层
能不能直接把先把所有时间遍历一遍计算每个时间点的二进制表示含有多少个1, 然后弄一个 array of ArrayList... .  真有必要用dp 么?
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-20 11:55:48 | 显示全部楼层
ghost33 发表于 2016-7-20 10:53
能不能直接把先把所有时间遍历一遍计算每个时间点的二进制表示含有多少个1, 然后弄一个 array of ArrayList ...

同意,相当于做了倒排索引。
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-20 12:40:46 | 显示全部楼层
贴个c++版本实现吧。
初始化的时候预存0-59中k digit on的数字。这个过程用dp计算每个数字有几个bit on,不过规模这么小不觉得DP是必须的。
输出的时候就是取所有hh位+ mm位 = x的可能性组合一下。需要注意hh取出来的数字不大于12。

class XBitTimes {       
public:
        XBitTimes(): nums(6, vector<int>{}) {
                array<int, 60> nbits{0};
. from: 1point3acres.com/bbs                 nums[0].push_back(0);
                for (int k = 1; k < 60; ++k) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        nbits[k] = nbits[k&(k-1)]+1;
                        nums[nbits[k]].push_back(k); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                }. 1point 3acres 璁哄潧
        }
       
        vector<string> GetTimes(int x) {
                vector<string> result;
                for (int k = max(0, x-5); k <= min(4, x); ++k) {
                        for (int hh : nums[k]) {
                                if (hh > 12) break;
                                for (int mm : nums[x-k]) result.push_back(FormatTime(hh, mm));
                        }. visit 1point3acres.com for more.
                }
                return result;
        }
       
private:
        string FormatTime(int hh, int mm) {
                char buf[6];
                sprintf(buf, "%02d:%02d\0", hh, mm);. 1point3acres.com/bbs
                return string(buf);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

        vector<vector<int>> nums;. from: 1point3acres.com/bbs
};
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| sammsiontir 发表于 2016-7-20 15:41:33 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| sammsiontir 发表于 2016-7-20 15:47:50 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| sammsiontir 发表于 2016-7-20 16:13:59 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-20 21:27:01 | 显示全部楼层
sammsiontir 发表于 2016-7-20 16:13
完整回一下我當時的解法好了,有兩個地方可以讓算法變快的:

1. 首先就像hxtang所說的,找出0-59中 0- ...

nums[y]=nums[y-1]+nums[1]里是指nums[y-1]所有数字加一个bit吗?那么比如插入6,可能是2+4也可能是4+2会插入两次你怎么处理?另外用bitset检查是否插入过吗?还是你连nums[2]也初始化掉了避免这种重复?

以及这个部分就run一次,快真的没啥意义。真要抬杠求快就把结果直接写代码里就好了. more info on 1point3acres.com
static const vector<vector<int>> nums {
{0},. more info on 1point3acres.com
{1,2,4,8,16,32},. more info on 1point3acres.com
{3,5,6,9,10,12,17,18,20,24,33,34,36,40,48},
{7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52,56},
{15,23,27,29,30,39,43,45,46,51,53,54,57,58},
{31,47,55,59} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
};

店面小哥可能是见过leetcode上那个1-n求nbit的题了才想了这么一出,但是自己完全没考虑过在他给的这个语境里这种优化有没有必要。
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| sammsiontir 发表于 2016-7-21 02:06:30 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-21 02:39:20 | 显示全部楼层
sammsiontir 发表于 2016-7-21 02:06
就跟你說的一樣nums[y-1]所有数字加一个bit,然後把y=2也初始化斃掉重複。. more info on 1point3acres.com
關於整個列出來,還有電面小 ...
-google 1point3acres
为什么我觉得你这个方法除了前面初始化的,剩下的其实0-59也走了一遍...只是走的顺序和0-59依次走不一样。
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| sammsiontir 发表于 2016-7-21 07:07:01 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 21:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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