w***y
发帖数: 6251 | 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*****2
发帖数: 21240 | 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***y
发帖数: 6251 | 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***y
发帖数: 6251 | 4 好像很难把我的问题说清楚, 我知道对一个方案, 肯定是either 从前往后长, OR从后
往前长
那是不是可以认为, 在做下面这种计算的时候
if( 前两位 excellent)
2+f(num.substring(2));
f(num.substring(2))已经考虑了把最后两个group的情况 | p*****2
发帖数: 21240 | 5
DP就是把问题缩小话。你看每一步都可以得到最佳答案。因此substring(2)的结果也必
是最佳答案。这就够了。不需要考虑其他的。
【在 w***y 的大作中提到】
: 好像很难把我的问题说清楚, 我知道对一个方案, 肯定是either 从前往后长, OR从后
: 往前长
: 那是不是可以认为, 在做下面这种计算的时候
: if( 前两位 excellent)
: 2+f(num.substring(2));
: f(num.substring(2))已经考虑了把最后两个group的情况
| b******t
发帖数: 965 | 6 他似乎是想问边界条件？
【在 p*****2 的大作中提到】
:
: DP就是把问题缩小话。你看每一步都可以得到最佳答案。因此substring(2)的结果也必
: 是最佳答案。这就够了。不需要考虑其他的。
| p*****2
发帖数: 21240 | 7
边界条件i就是如果String只有3个数字就不分2了，如果只有两个数字就不分3了。
【在 b******t 的大作中提到】
: 他似乎是想问边界条件？
| w***y
发帖数: 6251 | 8 睡了一觉想通了, 果然晚上脑子糊涂的时候不适合做题//汗 | S****h
发帖数: 115 | 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***n
发帖数: 2154 | 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*********8
发帖数: 4642 | 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; i
a[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*******e
发帖数: 91 | 12 看各位做题这么疯狂，俺的心凉了一截。要是被问到恐怕就完了。可是要我去疯狂做题
也做不到阿。
,
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
| S****h
发帖数: 115 | 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*********8
发帖数: 4642 | 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*****2
发帖数: 21240 | 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****h
发帖数: 115 | 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*****2
发帖数: 21240 | 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 的大作中提到】
: 霸气！
|
|
