问一个G家面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个G家面试题

问一个G家面试题# JobHunting - 待字闺中

w*y2012-03-27 07:03

1 楼

http://www.careercup.com/question?id=686684
You are given a String number containing the digits of a
phone number (the number of digits, n, can be any positive integer) . To
help you memorize
the number, you want to divide it into groups of contiguous digits. Each
group must contain
exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example,
000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030
, 229 or 166.
• Usual: A group in which all the digits are distinct. For example,
123 or 90.
The quality of a group assignment is defined as
2 × (number of excellent groups) + (number of good groups)
Divide the number into groups such that the quality is maximized. Design an
efficient
algorithm to return the solution that maximizes the quality.
这个题目应该怎么分解DP呢?
我看有几个人都是建议
F(n) = max{F(n-2) + v({a(n-1), a(n)}), F(n-3) + v({a(n-2), a(n-1), a(n)})}
首先我不知道这种分解是不是正确
其次,如果是这样的话, 我不太明白, 为什么可以分解成F(n-2) + v({a(n-1), a(n)}),
但是不考虑 v({a(0),a(1)})+F({a[2]...a[n-1]})

p*22012-03-27 07:03

2 楼

典型的DP题。
道理很简单。
比如， String num;
int f(String num)
{
if( 前两位 excellent)
2+f(num.substring(2));
else if(first two good)
1+f(num.substring(2));
else
f(num.substring(2));
同样对于前三位
取六个结果的最大值就可以了。

w*y2012-03-27 07:03

3 楼

我最主要的问题是, 为什么只针对前面的, 为什么不是全部考虑前/后 --- 这样就一共
12种情况orz

【在 p*****2 的大作中提到】

: 典型的DP题。
: 道理很简单。
: 比如， String num;
: int f(String num)
: {
: if( 前两位 excellent)
: 2+f(num.substring(2));
: else if(first two good)
: 1+f(num.substring(2));
: else

w*y2012-03-27 07:03

4 楼

好像很难把我的问题说清楚, 我知道对一个方案, 肯定是either 从前往后长, OR从后
往前长
那是不是可以认为, 在做下面这种计算的时候
if( 前两位 excellent)
2+f(num.substring(2));
f(num.substring(2))已经考虑了把最后两个group的情况

p*22012-03-27 07:03

5 楼

DP就是把问题缩小话。你看每一步都可以得到最佳答案。因此substring(2)的结果也必
是最佳答案。这就够了。不需要考虑其他的。

【在 w***y 的大作中提到】

: 好像很难把我的问题说清楚, 我知道对一个方案, 肯定是either 从前往后长, OR从后
: 往前长
: 那是不是可以认为, 在做下面这种计算的时候
: if( 前两位 excellent)
: 2+f(num.substring(2));
: f(num.substring(2))已经考虑了把最后两个group的情况

b*t2012-03-27 07:03

6 楼

他似乎是想问边界条件？

【在 p*****2 的大作中提到】

:
: DP就是把问题缩小话。你看每一步都可以得到最佳答案。因此substring(2)的结果也必
: 是最佳答案。这就够了。不需要考虑其他的。

p*22012-03-27 07:03

7 楼

边界条件i就是如果String只有3个数字就不分2了，如果只有两个数字就不分3了。

【在 b******t 的大作中提到】

: 他似乎是想问边界条件？

w*y2012-03-27 07:03

8 楼

睡了一觉想通了, 果然晚上脑子糊涂的时候不适合做题//汗

S*h2012-03-27 07:03

9 楼

贴下自己的代码供参考，大家有兴趣的话给挑挑ug,thanks！
import java.util.List;
class Solution {
List groups;
int score;
public Solution() {
groups = new ArrayList();
}
}
public class StringNumberGroup {
public Solution getOptimalGroup(String phone) {
if (phone.length() <= 3) {
Solution s = new Solution();
s.groups.add(phone);
s.score = getScore(phone);
return s;
} else if (phone.length() == 4) {
Solution s = new Solution();
s.groups.add(phone.substring(0, 2));
s.groups.add(phone.substring(2, 4));
s.score += getScore(phone.substring(0, 2));
s.score += getScore(phone.substring(2, 4));
}
Solution s1 = getOptimalGroup(phone.substring(2));
int g1 = getScore(phone.substring(0, 2));
Solution s2 = getOptimalGroup(phone.substring(3));
int g2 = getScore(phone.substring(0, 3));
if (s1.score + g1 > s2.score + g2) {
s1.groups.add(phone.substring(0, 2));
s1.score += g1;
return s1;
} else {
s2.groups.add(phone.substring(0, 3));
s2.score += g2;
return s2;
}
}
private int getScore(String phone) {
if (phone.length() == 2) {
if (phone.charAt(0) == phone.charAt(1))
return 2;
else
return 0;
} else if (phone.length() == 3) {
char a = phone.charAt(0);
char b = phone.charAt(1);
char c = phone.charAt(2);
if (a == b && b == c)
return 2;
else if (a == b || b == c || a == c)
return 1;
else
return 0;
}
return Integer.MIN_VALUE;
}
/**
* @param args
*/
public static void main(String[] args) {
StringNumberGroup p = new StringNumberGroup();
Solution s = p.getOptimalGroup("9958881499");
System.out.printf("total score: %1$d\n", s.score);
for (String str : s.groups) {
System.out.printf("%1$4s", str);
}
}
}

,
030

【在 w***y 的大作中提到】

: http://www.careercup.com/question?id=686684
: You are given a String number containing the digits of a
: phone number (the number of digits, n, can be any positive integer) . To
: help you memorize
: the number, you want to divide it into groups of contiguous digits. Each
: group must contain
: exactly 2 or 3 digits. There are three kinds of groups:
: • Excellent: A group that contains only the same digits. For example,
: 000 or 77.
: • Good: A group of 3 digits, 2 of which are the same. For example, 030

m*n2012-03-27 07:03

10 楼

你这个根本不是DP

【在 S****h 的大作中提到】

: 贴下自己的代码供参考，大家有兴趣的话给挑挑ug,thanks！
: import java.util.List;
: class Solution {
: List groups;
: int score;
: public Solution() {
: groups = new ArrayList();
: }
: }
: public class StringNumberGroup {

l*82012-03-27 07:03

11 楼

int bestGrouping(char c[], int n)
{
if (n < 2)
return 0;
if (n<4)
return groupScore(c, n);
int * scores = new int[n];
a[0] = 0;
a[1] = groupScore(c, 2)
a[2] = groupScore(c, 3)
a[3] = groupScore(c, 2) = groupScore(c+2, 2);
for (int i=4; ia[i] = groupScore(c+i-2, 3) + a[i-3];
a[i] = max(a[i], groupScore(c+i-1, 2) + a[i-2]);
}
int result = scores[n-1];
delete [] scores;
return result;
}
int groupScore(char c[], int n)
{
if (n < 2 || n > 3)
return 0;
if (n==2)
{
if (c[0] == c[1])
return 2;
else
return 0;
}
if (n==3)
{
int score = (c[0] == c[1]);
score += (c[1]==c[2]);
score += (c[0]==c[2]);
if (score >= 2)
return 2;
else
return score;
}
}

【在 p*****2 的大作中提到】

: 典型的DP题。
: 道理很简单。
: 比如， String num;
: int f(String num)
: {
: if( 前两位 excellent)
: 2+f(num.substring(2));
: else if(first two good)
: 1+f(num.substring(2));
: else

g*e2012-03-27 07:03

12 楼

看各位做题这么疯狂，俺的心凉了一截。要是被问到恐怕就完了。可是要我去疯狂做题
也做不到阿。

,
030

【在 w***y 的大作中提到】

S*h2012-03-27 07:03

13 楼

请指教~ //我觉得自己写的是DP呀
思路大概就是 S(n) = max( S(n-2), S(n-3) ）；
Solution s1 = getOptimalGroup(phone.substring(2));
int g1 = getScore(phone.substring(0, 2));
Solution s2 = getOptimalGroup(phone.substring(3));
int g2 = getScore(phone.substring(0, 3));

【在 m***n 的大作中提到】

: 你这个根本不是DP

l*82012-03-27 07:03

14 楼

你这个是递归。

【在 S****h 的大作中提到】

: 请指教~ //我觉得自己写的是DP呀
: 思路大概就是 S(n) = max( S(n-2), S(n-3) ）；
: Solution s1 = getOptimalGroup(phone.substring(2));
: int g1 = getScore(phone.substring(0, 2));
: Solution s2 = getOptimalGroup(phone.substring(3));
: int g2 = getScore(phone.substring(0, 3));

p*22012-03-27 07:03

15 楼

我来写一个标准的吧。也练练手。
public class test
{
public static void main(String[] args)
{
new test().run();
}
PrintWriter out = null;
int score(String str, int start, int len)
{
if (len == 2)
{
if (str.charAt(start) == str.charAt(start + 1))
return 2;
}
else if (len == 3)
{
char[] a = str.substring(start, start + 3).toCharArray();
if (a[0] == a[1] && a[1] == a[2])
return 2;
else if (a[0] == a[1] || a[0] == a[2] || a[1] == a[2])
return 1;
}
return 0;
}
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
String str = in.next();
int n = str.length();
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++)
{
int max = 0;
if (i >= 3 && i - 3 != 1)
max = Math.max(max, score(str, n - i, 3) + dp[i - 3]);
if (i >= 2 && i - 2 != 1)
max = Math.max(max, score(str, n - i, 2) + dp[i - 2]);
dp[i] = max;
}
out.println(dp[n]);
out.close();
}
}

S*h2012-03-27 07:03

16 楼

霸气！

【在 p*****2 的大作中提到】

: 我来写一个标准的吧。也练练手。
: public class test
: {
: public static void main(String[] args)
: {
: new test().run();
: }
: PrintWriter out = null;
: int score(String str, int start, int len)
: {

p*22012-03-27 07:03

17 楼

不好意思。刚才写的太滥了。没有优化。这次这个应该才是标准的。
import java.io.*;
import java.util.*;
public class test
{
public static void main(String[] args)
{
new test().run();
}
PrintWriter out = null;
int score(String str, int start, int len)
{
if (len == 2)
{
if (str.charAt(start) == str.charAt(start + 1))
return 2;
}
else if (len == 3)
{
char[] a = str.substring(start, start + 3).toCharArray();
if (a[0] == a[1] && a[1] == a[2])
return 2;
else if (a[0] == a[1] || a[0] == a[2] || a[1] == a[2])
return 1;
}
return 0;
}
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
String str = in.next();
int n = str.length();
int[] dp = new int[3];
for (int i = 2; i <= n; i++)
{
int max = 0;
if (i >= 3 && i - 3 != 1)
max = Math.max(max, score(str, n - i, 3) + dp[(i - 3) % 3]);
if (i >= 2 && i - 2 != 1)
max = Math.max(max, score(str, n - i, 2) + dp[(i - 2) % 3]);
dp[i % 3] = max;
}
out.println(dp[n % 3]);
out.close();
}
}

【在 S****h 的大作中提到】

: 霸气！