一亩三分地论坛

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

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

问一道 google 老题

[复制链接] |试试Instant~ |关注本帖
lvvvvv 发表于 2016-8-8 10:48:33 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Google - 内推 - 其他 |Pass在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x

记电话号码
You are given a String numbercontaining the digits of a phone number (the number of digits, n, can be anypositive integer) . To help you memorize the number, you want to divide it intogroups of contiguous digits. Each group must contain exactly 2 or 3 digits.There are three kinds of groups:
• Excellent: A group that containsonly the same digits. For example, 000 or 77.
• Good: A group of 3 digits, 2 ofwhich are the same. For example, 030, 229 or 166.
• Usual: A group in which all thedigits are distinct. For example, 123 or 90.
The quality of a group assignment isdefined as
2 × (number of excellent groups) +(number of good groups)
Divide the number into groups suchthat the quality is maximized. Design an
efficient algorithm to return thesolution that maximizes the quality

.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉上是用  DP,  但是想不出关系式。 从  j-1 到 j  要看前面好几个数字的关系 。
. From 1point 3acres bbs
大牛帮看看。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


muybienw 发表于 2016-8-8 11:19:27 | 显示全部楼层
DP[i][j]记录从坐标i到坐标j的max quality。对于一个区间[start, end],需要查看:.鏈枃鍘熷垱鑷1point3acres璁哄潧
- 不切分,整个区间是一个group。
- 切分,考虑所有切分位置,有tmp = DP[start][i] + DP[i+1][end]。
这样可以算出这个区间的max quality。
最后返回DP[0][length-1]。
.1point3acres缃
可以top-down with memoization或者bottom-up做,有点像Leetcode上的burst balloons。

回复 支持 反对

使用道具 举报

tigercode 发表于 2016-8-8 14:17:32 | 显示全部楼层
1-d dp就行吧,而且因为只depends on前两个值,可以constant space cost
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-8-8 20:03:47 | 显示全部楼层
tigercode 发表于 2016-8-8 14:17
1-d dp就行吧,而且因为只depends on前两个值,可以constant space cost
.1point3acres缃
我觉得constant space不行,
(以下:n是电话位数;省略号是根据数字算该三位或两位的得分)
相当于从头到尾遍历了电话号码两遍。-google 1point3acres
一开始是2, 3;第二轮到4,5,6;第三轮到6,7,8,9;。。。
依次多一个。
dp[2] = ...
dp[3] = ...
for (i = 2; i <= n; i <<= 1) {
    for (j = i; j < i * 2; ++j) {
        dp[j + 2] = max(dp[j + 2], dp[j] + ...)
        dp[j + 3] = max(dp[j + 3], dp[j] + ...)
    }
}

return dp[n]
回复 支持 反对

使用道具 举报

martin5678 发表于 2016-8-8 20:58:59 | 显示全部楼层
DP[i] 表示到位置i可以获得最大分数, DP[i] = max(DP[i - 2] + i- 1 到i所能获得的分数, DP[i - 3] + i - 2到i所能获得的分数)。初始化DP[0] = 0, DP[1] = 0-1所能获得的分数,DP[2] 0 - 2 所能获得的分数, 注意DP[3] 只能是0-1 2-3的划分,然后如楼上所说这个还可以进一步优化成constant space
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-8-8 22:29:41 | 显示全部楼层
应该一维dp就可以吧,然后可以优化
dp[i] = max(dp[i], dp[i-2], dp[i-3]+quality)
回复 支持 反对

使用道具 举报

 楼主| lvvvvv 发表于 2016-8-9 06:32:59 | 显示全部楼层
还是有点不对:  比如说  4, 3, 4, 9
dp[0] = 0,
dp[1] = 0,
4, 9   和 3,4,9 都凑不出啥,  但是 dp[3] = 1;

所以应该是  dp[i] = max(dp[i-1], dp[i-2]+carry1, dp[i-3]+carry2)  , 对不 ?

回复 支持 反对

使用道具 举报

phantom 发表于 2016-8-9 07:12:54 | 显示全部楼层
楼上有人给正解了。。
DP[i] = max(DP[i - 2] + i- 1 到i所能获得的分数, DP[i - 3] + i - 2到i所能获得的分数)
只是base case
DP[0] = 0 DP[1] = 0(因为什么都组不了) DP[2] = 0 或 2 DP[3] = (根据前三个数字定) DP[4] = DP[2] + (第三个和第四个数字)
从头DP[5] 开始就可以用递推公式了

回复 支持 反对

使用道具 举报

 楼主| lvvvvv 发表于 2016-8-9 08:38:10 | 显示全部楼层
还是不对,
2 1 0 5 4 3 4 9

你在倒数第二位上才会得到第一个 dp = 1
按照递推公式,  最后一位 只跟 i-2, i-3 有关, 那也是 0.  所以我觉得要加上 max(dp[i-1] 。。。. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

martin5678 发表于 2016-8-9 09:12:22 | 显示全部楼层
lvvvvv 发表于 2016-8-9 08:38
还是不对,
2 1 0 5 4 3 4 9

题目说的所有切分只能是2或者3, 所以你给的这个例子最后的结果应该就是0
回复 支持 反对

使用道具 举报

 楼主| lvvvvv 发表于 2016-8-9 09:21:22 | 显示全部楼层
Good: A group of 3 digits, 2 ofwhich are the same. For example, 030, 229 or 166.
回复 支持 反对

使用道具 举报

xnature 发表于 2016-8-12 06:01:12 | 显示全部楼层
lvvvvv 发表于 2016-8-9 09:21
Good: A group of 3 digits, 2 ofwhich are the same. For example, 030, 229 or 166.

最后一个9落单了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 22:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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