q*****9
发帖数: 85 | 1 1. 找出一个从0到x(x<=10^7)中各个数位上的数相加和相等的最多的那个和是
多少，出现了多少次。
例如 x=10, return 2(1,10和都为1)
x= 50, return 6(5,14,23,32,41,50和都为5)
2. 一个大整数，x<=10^9, 找出两个素数的和是这个数的其中较小的那个素数,如果
答案不唯一,返回最小的那个素数,如果没答案,返回-1.
例如, x=12 返回5(5+7=12)
x=77 返回-1 | c****p
发帖数: 6474 | 2 第一个得建表吧，，根据规律统计0-9,0-99,0-999……数位和，然后从高位到低位一位
位处理。
【在 q*****9 的大作中提到】
: 1. 找出一个从0到x(x<=10^7)中各个数位上的数相加和相等的最多的那个和是
: 多少，出现了多少次。
: 例如 x=10, return 2(1,10和都为1)
: x= 50, return 6(5,14,23,32,41,50和都为5)
: 2. 一个大整数，x<=10^9, 找出两个素数的和是这个数的其中较小的那个素数,如果
: 答案不唯一,返回最小的那个素数,如果没答案,返回-1.
: 例如, x=12 返回5(5+7=12)
: x=77 返回-1
| c****p
发帖数: 6474 | 3 第二题应该是先建素数表？
【在 q*****9 的大作中提到】
: 1. 找出一个从0到x(x<=10^7)中各个数位上的数相加和相等的最多的那个和是
: 多少，出现了多少次。
: 例如 x=10, return 2(1,10和都为1)
: x= 50, return 6(5,14,23,32,41,50和都为5)
: 2. 一个大整数，x<=10^9, 找出两个素数的和是这个数的其中较小的那个素数,如果
: 答案不唯一,返回最小的那个素数,如果没答案,返回-1.
: 例如, x=12 返回5(5+7=12)
: x=77 返回-1
| g**********y
发帖数: 14569 | 4 0. if x<2 return -1;
1. buildSieveTable up to x
2. if x is odd, return x-2 is prime? 2 : -1
3. for ( i in sieveTable ) if x-i is in sieveTable return i (According to
Goldbach conjecture)
【在 c****p 的大作中提到】
: 第二题应该是先建素数表？
| g**********y
发帖数: 14569 | 5 第一个，brutal force:
public class MaxSum {
public int findMax(int x) {
int digits = ("" + x).length();
int max = 0;
for (int sum = 0; sum <= digits*9; sum++) {
max = Math.max(max, totalWaysUpto(x, sum));
}
return max;
}
private int totalWaysUpto(int x, int sum) {
if (sum < 0) return 0;
char[] c = ("" + x).toCharArray();
int N = c.length;
int count = 0;
if (N == 1) return sum<=x? 1 : 0;
int first = c[0] - '0';
for (int i=0; i
count += totalWays(sum-i, N-1);
}
count += totalWaysUpto(Integer.parseInt(new String(c, 1, N-1)), sum-
first);
return count;
}
private int totalWays(int sum, int digits) {
if (sum < 0 || sum > 9*digits) return 0;
if (digits == 1) return 1;
int count = 0;
for (int i=0; i<10; i++) count += totalWays(sum-i, digits-1);
return count;
}
} | b*******8
发帖数: 37364 | 6 第二题，如果是奇数，则必有2，只需要测X-2是不是质数，如是则返回2 | s*****n
发帖数: 5488 | 7 Not sure I understand.
我得理解是要用一个array来记beans.
暗示的很清楚：10^7 max sum is 7*9= 63
【在 g**********y 的大作中提到】
: 第一个，brutal force:
: public class MaxSum {
: public int findMax(int x) {
: int digits = ("" + x).length();
: int max = 0;
: for (int sum = 0; sum <= digits*9; sum++) {
: max = Math.max(max, totalWaysUpto(x, sum));
: }
: return max;
: }
| g**********y
发帖数: 14569 | 8 要是输入小，我就搜sum的小空间了。你说的什么beans? 不太明白。
totalWaysUpto(int x, int sum): 计算从1到x, 数位和为sum的个数
totalWays(int sum, int digits): 计算digits位数，和为sum的个数
【在 s*****n 的大作中提到】
: Not sure I understand.
: 我得理解是要用一个array来记beans.
: 暗示的很清楚：10^7 max sum is 7*9= 63
| s*****n
发帖数: 5488 | 9 我的理解是，
先allocate 64个buckets.清零。
for int i to x
convert to bcd code;
for int j to 8
sum up bcd code
bucket[sum]++;
return max of buckets and its index.
【在 g**********y 的大作中提到】
: 要是输入小，我就搜sum的小空间了。你说的什么beans? 不太明白。
: totalWaysUpto(int x, int sum): 计算从1到x, 数位和为sum的个数
: totalWays(int sum, int digits): 计算digits位数，和为sum的个数
| s*****n
发帖数: 5488 | 10 I see what you are doing.估计我是现场搞不定，只能认栽了。
【在 g**********y 的大作中提到】
: 要是输入小，我就搜sum的小空间了。你说的什么beans? 不太明白。
: totalWaysUpto(int x, int sum): 计算从1到x, 数位和为sum的个数
: totalWays(int sum, int digits): 计算digits位数，和为sum的个数
| | | g**********y
发帖数: 14569 | 11 这个coding很简单，也是正确的。唯一差别是运行时间。
x = 9999999
complex code run 0.265s
simple code run 1.334s
【在 s*****n 的大作中提到】
: 我的理解是，
: 先allocate 64个buckets.清零。
: for int i to x
: convert to bcd code;
: for int j to 8
: sum up bcd code
: bucket[sum]++;
: return max of buckets and its index.
| g**********y
发帖数: 14569 | 12 我现场写边界条件肯定错 :) 但是没办法，interview肯定想看复杂一点的，而不是直
接的brutal force.
没准可能还有效率更高，更简单的解法。
【在 s*****n 的大作中提到】
: I see what you are doing.估计我是现场搞不定，只能认栽了。
| g***s
发帖数: 3811 | 13 we can preProcess using DP to save time;
time is O(logN×logN)
public class MaxSum {
private static final int MAX_DIGIT = 7;
static int dp[][] = new int[MAX_DIGIT+1][MAX_DIGIT*9+1];
public static int findMax(int x){
int digits = ("" + x).length();
int max = 0;
int t;
for (int sum = 0 ; sum <= 9*digits ; sum++){
max = Math.max(max, t = totalWaysUpto(x, sum));
}
return max;
}
private static int totalWaysUpto(int x, int sum) {
if (sum < 0) return 0;
char[] c = ("" + x).toCharArray();
int count=0;
int prefixSum = 0;
int leftDigit = c.length;
for (char d : c){
d -= '0';
leftDigit--;
for (int i = prefixSum; i < prefixSum + d; i++) {
if (sum < i) break;
else count += (leftDigit==0)? (sum==i) ? 1 : 0 : dp[
leftDigit-1][sum - i];
}
prefixSum += d;
}
return prefixSum==sum? count+1 : count;
}
public static void preProcess() {
for (int i=0;i<=9;i++) dp[0][i]=1;
for (int digit = 1 ; digit < MAX_DIGIT; digit++){
for (int sum = 0 ; sum <= 9 * (digit+1); sum++){
for (int i=0;i<=Math.min(9,sum);i++)
dp[digit][sum] += dp[digit-1][sum-i];
}
}
}
public static void main(String[] args) {
preProcess();
System.out.println(findMax(50));
// System.out.println(totalWaysUpto(1000,20));
}
}
【在 g**********y 的大作中提到】
: 我现场写边界条件肯定错 :) 但是没办法，interview肯定想看复杂一点的，而不是直
: 接的brutal force.
: 没准可能还有效率更高，更简单的解法。
| g**********y
发帖数: 14569 | 14 这个应该算得很快。
【在 g***s 的大作中提到】
: we can preProcess using DP to save time;
: time is O(logN×logN)
: public class MaxSum {
: private static final int MAX_DIGIT = 7;
: static int dp[][] = new int[MAX_DIGIT+1][MAX_DIGIT*9+1];
: public static int findMax(int x){
: int digits = ("" + x).length();
: int max = 0;
: int t;
: for (int sum = 0 ; sum <= 9*digits ; sum++){
| q*****9
发帖数: 85 | 15 没错,以10为底的,还可以把sum改成9*(digits-1)+首位数字,
这个非常快，我试了一下20位数的才15ms.
【在 g***s 的大作中提到】
: we can preProcess using DP to save time;
: time is O(logN×logN)
: public class MaxSum {
: private static final int MAX_DIGIT = 7;
: static int dp[][] = new int[MAX_DIGIT+1][MAX_DIGIT*9+1];
: public static int findMax(int x){
: int digits = ("" + x).length();
: int max = 0;
: int t;
: for (int sum = 0 ; sum <= 9*digits ; sum++){
|
|
