求助－唐筛高危 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>NextGeneration - 我爱宝宝

求助－唐筛高危

求助－唐筛高危# NextGeneration - 我爱宝宝

x*e2010-07-16 07:07

1 楼

题目是decode ways
但是input String可以包含 *
比如 1*2，可以有 102 （1），112 （3）， 122（3），132(2), 142(2), 152(2),
162(2), 172(2) 182(2) 192 (2) 一共 21种解法。
返回多少解, 刚开始想还挺简单的，写起来并不简单，比如 1**1 ，两个*都要判断。。

p*n2010-07-16 07:07

2 楼

我嫂子刚做血检出结果说是唐氏高危然后人很着急她们下周要来美国准备再这里待产
得请问这个情况要再国内做羊水穿刺进一步检察还是来美国做？
如果准备自己出钱得话这个检查需要大概多少钱我再硅谷湾区／bow

W*o2010-07-16 07:07

3 楼

关注一下，我也想知道

。。

【在 x***e 的大作中提到】

: 题目是decode ways
: 但是input String可以包含 *
: 比如 1*2，可以有 102 （1），112 （3）， 122（3），132(2), 142(2), 152(2),
: 162(2), 172(2) 182(2) 192 (2) 一共 21种解法。
: 返回多少解, 刚开始想还挺简单的，写起来并不简单，比如 1**1 ，两个*都要判断。。

N*u2010-07-16 07:07

4 楼

就在国内做呗。国内做肯定比这里便宜呀。

G*O2010-07-16 07:07

5 楼

我赶脚，就是对每个*枚举咯。

。。

【在 x***e 的大作中提到】

p*n2010-07-16 07:07

6 楼

问题是来不及了呀她们下周末的飞机这个需要时间？而且这是个简单的手术嘛？

【在 N******u 的大作中提到】

: 就在国内做呗。国内做肯定比这里便宜呀。

c*w2010-07-16 07:07

7 楼

Let A be the input array of digits or *
Let I(n, 1) = count of valid values (between 1 and 26) can be obtained by A[
n].
If A[n] == 0, then I(n, 1) = 0;
else if A[n] == *, then I(n, 1) = 9; // 1~9
else A[n] = 1~9, then I(n, 1) = 1.
Let I(n, 2) = count of valid values can be obtained by A[n-1] * 10 A[n].
If A[n-1] == 1, then I(n, 2) = (A[n] == * ? 10 : 1); // 10~19
else if A[n-1] == 2, then I(n, 2) = (A[n] == * ? 7 : (A[n] <= 6 ? 1 : 0))
; // 20~26
else if A[n-1] == *, then I(n, 2) = (A[n] == * ? 17 : (A[n] <= 6 ? 2 : 1)
); // 10~26
else I(n, 2) = 0. // A[n-1] == 0 or A[n-1] > 2
For both basic version and follow-up version:
D[n] = D[n-1] * I(n, 1) D[n-2] * I(n, 2)

N*u2010-07-16 07:07

8 楼

不是。主要是流产的可能性和感染的可能性，虽然非常小。据说各诊所的数据都不一样
。你不如问问附近的几个医院，问下她们做这个如果没有保险是多少钱，因为有保险和
没有保险，价格是不一样的。而且她们过来生孩子，如果没有保险，难道到教会医院去
生？
她们还有一周的时间啊，那玩意结果出来很快的。

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

: 问题是来不及了呀她们下周末的飞机这个需要时间？而且这是个简单的手术嘛？

j*12010-07-16 07:07

9 楼

不知道对不对大概跑了几个test case貌似没啥问题
public static int decodeWays(String s) {
if (s == null || s.length() == 0) return 0;
int[] dp = new int[s.length() + 1];
dp[s.length()] = 1;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '0') dp[i] = 0;
else if (s.charAt(i) != '*') {
dp[i] += dp[i + 1];
if (i + 1 < s.length()) {
if (s.charAt(i + 1) != '*') {
int num = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1
) - '0');
if (num >= 10 && num <= 26) dp[i] += dp[i + 2];
}
else if (s.charAt(i) == '1') dp[i] += dp[i + 2] * 10;
else if (s.charAt(i) == '2') dp[i] += dp[i + 2] * 7;
}
} else {
dp[i] += dp[i + 1] * 9;
if (i + 1 < s.length()) {
if (s.charAt(i + 1) != '*') {
if (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '6'
) dp[i] += dp[i + 2] * 2;
else dp[i] += dp[i + 2];
} else {
dp[i] += dp[i + 2] * 17;
}
}
}
}
return dp[0];
}

p*n2010-07-16 07:07

10 楼

自己出钱生呀

【在 N******u 的大作中提到】

: 不是。主要是流产的可能性和感染的可能性，虽然非常小。据说各诊所的数据都不一样
: 。你不如问问附近的几个医院，问下她们做这个如果没有保险是多少钱，因为有保险和
: 没有保险，价格是不一样的。而且她们过来生孩子，如果没有保险，难道到教会医院去
: 生？
: 她们还有一周的时间啊，那玩意结果出来很快的。

i*h2010-07-16 07:07

11 楼

112 （3）括号里的3是什么意思？

。。

【在 x***e 的大作中提到】

h*n2010-07-16 07:07

12 楼

好像是$2000左右。

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

: 自己出钱生呀

m*e2010-07-16 07:07

13 楼

112->[1,1,2], [11,2], [1,12]
楼上的方法应该是对的

N*u2010-07-16 07:07

14 楼

跟生孩子的费用比起来，羊川费用就算小case了吧，要是b超简直就成零头了。

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

: 自己出钱生呀

G*O2010-07-16 07:07

15 楼

这是对的。

【在 j**********1 的大作中提到】

: 不知道对不对大概跑了几个test case貌似没啥问题
: public static int decodeWays(String s) {
: if (s == null || s.length() == 0) return 0;
: int[] dp = new int[s.length() + 1];
: dp[s.length()] = 1;
: for (int i = s.length() - 1; i >= 0; i--) {
: if (s.charAt(i) == '0') dp[i] = 0;
: else if (s.charAt(i) != '*') {
: dp[i] += dp[i + 1];
: if (i + 1 < s.length()) {

p*n2010-07-16 07:07

16 楼

我就问问多少钱呵呵

【在 N******u 的大作中提到】

: 跟生孩子的费用比起来，羊川费用就算小case了吧，要是b超简直就成零头了。

G*O2010-07-16 07:07

17 楼

还有个followup
我decode不是按照1-26
而是有MAP，比如 A -> 50, B -> 2, C = 200
怎么办

d*s2010-07-16 07:07

18 楼

这个一般的医院都是要预约的，你还是马上给她预约吧，羊穿好像只能在一定的周数
之内作。

f*42010-07-16 07:07

19 楼

说说思路？最后那里乘以17是怎么来的？

【在 G**O 的大作中提到】

: 这是对的。

w*t2010-07-16 07:07

20 楼

According to the web,
Amniocentesis (done w15 to w18) ranges from 1100 to 2000,
Chorionic Villus Sampling (cvs) can be done before 3 mos. range from 1200 to
>2000. I did CVS 2 years ago, and my insurance cover 80%, and I remeber I
paid 200s out of pocket. so the info on the web is kind of accurate.
if you are paying out of your own pocket, you can negotiate with the lab and
paying lower fees.
I would not cancel air ticket. after all US has the best medical equipment
and technology.

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

: 我嫂子刚做血检出结果说是唐氏高危然后人很着急她们下周要来美国准备再这里待产
: 得请问这个情况要再国内做羊水穿刺进一步检察还是来美国做？
: 如果准备自己出钱得话这个检查需要大概多少钱我再硅谷湾区／bow

m*e2010-07-16 07:07

21 楼

**
10...19
20...26

【在 f******4 的大作中提到】

:
: 说说思路？最后那里乘以17是怎么来的？

w*t2010-07-16 07:07

22 楼

G*O2010-07-16 07:07

23 楼

这广告做的有点。。。。
又要关注，又要转发，才能看个答案。上面都贴出对的了。

s*x2010-07-16 07:07

24 楼

那个解法有bug吧

【在 G**O 的大作中提到】

: 这广告做的有点。。。。
: 又要关注，又要转发，才能看个答案。上面都贴出对的了。

h*n2010-07-16 07:07

25 楼

我有解题答案，发邮件到 [email protected] 跟我要

z*n2010-07-16 07:07

26 楼

直接上干货, leetcode已经有这题了 (* 代表1~9 而非0~9)，这是我过了的一个解:
class Solution {
int base = 1000000007;
public:
int numDecodings(string s) {
//last1: decode ways of s ending at i-1, last2 decode ways of s
ending at i-2, nlast1 : next last1.
long long last1 = 1, last2 = 1, nlast1 = 0; //there is only 1 way to
decode "", so initialized with 1.
for (int i = 0; i < s.size(); ++ i)
{
//Just look at current character
if (s[i] == '*')
nlast1 = last1 * 9 % base;
else if (s[i] == '0')
nlast1 = 0;
else
nlast1 = last1;
//All three if below: look at last two characters.
if (i > 0 && s[i - 1] == '1')
if (s[i] == '*')
nlast1 = (nlast1 + last2 * 9) % base;
else
nlast1 = (nlast1 + last2) % base;
if (i > 0 && s[i - 1] == '2')
if (s[i] == '*')
nlast1 = (nlast1 + last2 * 6) % base;
else if (s[i] <= '6')
nlast1 = (nlast1 + last2) % base;
if (i > 0 && s[i - 1] == '*')
if (s[i] == '*')
nlast1 = (nlast1 + last2 * 15) % base; //1* + 2* = 15
else if (s[i] <= '6')
nlast1 = (nlast1 + last2 * 2) % base; //1a + 2a = 2, a
is one fixed number.
else
nlast1 = (nlast1 + last2) % base; //1a = 1 case
last2 = last1;
last1 = nlast1;
}
return last1;
}
};

u*u2010-07-16 07:07

27 楼

这题已经上lc了自己去刷