【Max】今天接还是明天接，请小咪妈土拨鼠来看update - 未名空间MITBBS历史存档

【Max】今天接还是明天接，请小咪妈土拨鼠来看update# pets - 心有所宠

h*o2012-08-30 07:08

1 楼

Given a string s, partition s such that every substring of the partition is
a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab", Return
[
["aa","b"],
["a","a","b"]
]
知道是用backtracking + DP. 但只知道判断是否Palindrome 可以DP. 不知道为何有贴
说有两个地方可以DP？
复杂度如何求？
time: 每个node 分成 n 支，有n 层树，难道是 time = n^n?
space: n (recursive)+ n^2 (存 isPalindrome 的结果） = n^2?

C*l2012-08-30 07:08

2 楼

【以下文字转载自 Military 讨论区】
发信人: Closingbell (玩笑别太过，要不都是祸), 信区: Military
标题: 成都妹子不要这样风情万千好不好
发信站: BBS 未名空间站 (Thu Jul 11 00:12:45 2013, 美东)
哈哈

x*o2012-08-30 07:08

3 楼

早上医院发信说radiation level够低，今天可以接了
我想他啊，恨不得马上就去
他弟弟（littermate)想他啊，每天都要跟我说很多遍，真的是说话，如泣如诉的说
（猫妈，大猫妈们，你们都懂的）。再拖我都怕他要抑郁了
可是我怕残余的radiation会对另外两个有影响
虽然隔离，我准备给他一个full bathroom，可是他弟弟一定一定整天守在他门口，
两个里应外合的想办法开门。实在开不了会隔着门挨着躺的。木头门根本就隔不了伽
马ray的啊
哎~纠结死了！！
大家说我是今天接还是明天接呢
==========================================================
7楼有我的research结果， 8楼是宠物医院给的instruction
美国甲状腺协会给做了I131治疗的人的隔离instruction
最近还看了很多这方面的paper，这个还算是相当严格和详细的instruction了
还有做完就放病人走的医生
猫的看似比人的要严格很多啊。为什么啊~~

S*J2012-08-30 07:08

4 楼

两个dp是求最小palindrome切割数的，这道题recursive地往回找就行了，和subsets的
思路差不多。
class Solution {
public:
bool isPalindrome(string s, int start, int end)
{

while(start{
if(s[start]!=s[end])
return false;

start++;
end--;
}
return true;
}

void DFS(string &s, int start, vector &temp, vectorstring>> &res)
{
if(start==s.size())
{
res.push_back(temp);
return;
}

for(int i=start; i{
if(isPalindrome(s, start, i))
{
temp.push_back(s.substr(start, i-start+1));
DFS(s, i+1, temp, res);
temp.pop_back();
}
}
}
vector> partition(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector> res;
vector temp;

DFS(s, 0, temp, res);

return res;
}
};

H*g2012-08-30 07:08

5 楼

背袜子过河，万元一次

t*u2012-08-30 07:08

6 楼

如果max情绪可以，就明天

h*o2012-08-30 07:08

7 楼

请问你哪里用到DP了？
我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
array 里，省得老算老算的，我觉得这叫DP.

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

: 两个dp是求最小palindrome切割数的，这道题recursive地往回找就行了，和subsets的
: 思路差不多。
: class Solution {
: public:
: bool isPalindrome(string s, int start, int end)
: {
:
: while(start: {
: if(s[start]!=s[end])

t*t2012-08-30 07:08

8 楼

第二张不错

【在 C*********l 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: Closingbell (玩笑别太过，要不都是祸), 信区: Military
: 标题: 成都妹子不要这样风情万千好不好
: 发信站: BBS 未名空间站 (Thu Jul 11 00:12:45 2013, 美东)
: 哈哈

x*o2012-08-30 07:08

9 楼

问题是他情绪好像也不好啊。
医院说他前面两天吃的好。
昨天就躲着不吃饭，不见人了。
我送他去的时候给带的干粮他不爱吃，罐头忘在车上没给他们。
那个specialist很好的，昨天给喂了罐头
可是我还是想让他回家啊，想吃啥给啥
我觉得他在医院好可怜啊。见不到人，活动空间又小

S*J2012-08-30 07:08

10 楼

我表达有这么差劲咩＝。＝？
我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
，这个就是直接往回找就行了。

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

: 请问你哪里用到DP了？
: 我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
: 我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
: array 里，省得老算老算的，我觉得这叫DP.

r*x2012-08-30 07:08

11 楼

5元一次

【在 H********g 的大作中提到】

: 背袜子过河，万元一次

t*u2012-08-30 07:08

12 楼

那就接回来吧
我会接回来
然后想办法围追堵截家里二货

h*o2012-08-30 07:08

13 楼

明白了。谢谢。：-）
请问我说的 Palindrome Partitioning 这道题 time 复杂度是 n^n 吗？如果不是
，那是什么那？

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

: 我表达有这么差劲咩＝。＝？
: 我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
: ，这个就是直接往回找就行了。

t*32012-08-30 07:08

14 楼

漂亮的背过河不要钱，丑的两倍价格

x*o2012-08-30 07:08

15 楼

好的
谢谢
等下老板走了我就去接他
希望路上traffic不要太糟糕。今天开的车后排座没有专门的空调

h*o2012-08-30 07:08

16 楼

明白了。谢谢。：-）
请问我说的 Palindrome Partitioning 这道题 time 复杂度是 n^n 吗？如果不是
，那是什么那？

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

: 我表达有这么差劲咩＝。＝？
: 我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
: ，这个就是直接往回找就行了。

o*12012-08-30 07:08

17 楼

不错，赞曰：江南原多雨，秦淮岂无姝；若问花常处，骑鹤入成都；气清尘飞少，楼明
戏可无？偶目涉水女，客牌停未胡。

【在 C*********l 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: Closingbell (玩笑别太过，要不都是祸), 信区: Military
: 标题: 成都妹子不要这样风情万千好不好
: 发信站: BBS 未名空间站 (Thu Jul 11 00:12:45 2013, 美东)
: 哈哈

W*e2012-08-30 07:08

18 楼

接回来吧，听着怪心疼得。

h*o2012-08-30 07:08

19 楼

Given a string s, partition s such that every substring of the partition is
a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab", Return
[
["aa","b"],
["a","a","b"]
]
知道是用backtracking + DP. 但只知道判断是否Palindrome 可以DP. 不知道为何有贴
说有两个地方可以DP？
复杂度如何求？
time: 每个node 分成 n 支，有n 层树，难道是 time = n^n?
space: n (recursive)+ n^2 (存 isPalindrome 的结果） = n^2?

l*32012-08-30 07:08

20 楼

是倒贴５元背妹子过河吧

x*o2012-08-30 07:08

21 楼

美国甲状腺协会给做了I131治疗的人的隔离instruction
最近还看了很多这方面的paper，这个还算是相当严格和详细的instruction了
还有做完就放病人走的医生
猫的看似比人的要严格很多啊。为什么啊~~

S*J2012-08-30 07:08

22 楼

两个dp是求最小palindrome切割数的，这道题recursive地往回找就行了，和subsets的
思路差不多。
class Solution {
public:
bool isPalindrome(string s, int start, int end)
{

while(start{
if(s[start]!=s[end])
return false;

start++;
end--;
}
return true;
}

void DFS(string &s, int start, vector &temp, vectorstring>> &res)
{
if(start==s.size())
{
res.push_back(temp);
return;
}

for(int i=start; i{
if(isPalindrome(s, start, i))
{
temp.push_back(s.substr(start, i-start+1));
DFS(s, i+1, temp, res);
temp.pop_back();
}
}
}
vector> partition(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector> res;
vector temp;

DFS(s, 0, temp, res);

return res;
}
};

P*e2012-08-30 07:08

23 楼

丑的背过河5块，漂亮的抱过河倒贴

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

: 漂亮的背过河不要钱，丑的两倍价格

x*o2012-08-30 07:08

24 楼

For the next two weeks you must:
1. Not hold your cat or allow it to sit in your lap for an extended time (>
15minutes).
Do not allow you cat to sleep in the room with you.
2. Provide a litter pan for your cat’s urination and defecation. This
litter should be
disposed daily in a garbage bag lined outside receptacle. Wear disposable
gloves
when handling the litter.
3. Always wash your hands immediately after contact with your cat or cat’s
litter.
4. Confine your cat in your home at all times.
5. Not allow any person less than 18 years of age to have contact with your
cat.
6. Not allow any pregnant person to have contact with your cat.
7. If you have any questions regarding radiation safety measures concerning
your
cat, please call Sugar Land Veterinary Specialists at (281) 491-7800 to
obtain
help from the appropriate person.
IMPROTANT: Should you be unable to abide by the preceding condition, your
cat must
be hospitalized for 2 additional weeks.

h*o2012-08-30 07:08

25 楼

请问你哪里用到DP了？
我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
array 里，省得老算老算的，我觉得这叫DP.

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

: 两个dp是求最小palindrome切割数的，这道题recursive地往回找就行了，和subsets的
: 思路差不多。
: class Solution {
: public:
: bool isPalindrome(string s, int start, int end)
: {
:
: while(start: {
: if(s[start]!=s[end])

M*92012-08-30 07:08

26 楼

好像都挺好看的。。
你们介些倒贴的家伙。。
★ 发自iPhone App: ChineseWeb 7.8

d*o2012-08-30 07:08

27 楼

祝一切顺利！

S*J2012-08-30 07:08

28 楼

我表达有这么差劲咩＝。＝？
我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
，这个就是直接往回找就行了。

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

: 请问你哪里用到DP了？
: 我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
: 我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
: array 里，省得老算老算的，我觉得这叫DP.

f*e2012-08-30 07:08

29 楼

好诗

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

: 不错，赞曰：江南原多雨，秦淮岂无姝；若问花常处，骑鹤入成都；气清尘飞少，楼明
: 戏可无？偶目涉水女，客牌停未胡。

z*e2012-08-30 07:08

30 楼

太不容易了！
pat pat both!!

h*o2012-08-30 07:08

31 楼

明白了。谢谢。：-）
请问我说的 Palindrome Partitioning 这道题 time 复杂度是 n^n 吗？如果不是
，那是什么那？

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

: 我表达有这么差劲咩＝。＝？
: 我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
: ，这个就是直接往回找就行了。

b*d2012-08-30 07:08

32 楼

小伙子有两种服务啊。

t*u2012-08-30 07:08

33 楼

刚才看到了
可能是因为猫不如人听话吧，而且生命力强些
人回来肯定累到床上不动了
猫要是稍微恢复点就会到处转悠
而且回来肯定比较stress会想办法到处藏啊什么的，容易受到惊吓
自然要求多些
这几周还挺难熬的，不过回家就好回家就好。什么时候复诊啊？

h*o2012-08-30 07:08

34 楼

明白了。谢谢。：-）
请问我说的 Palindrome Partitioning 这道题 time 复杂度是 n^n 吗？如果不是
，那是什么那？

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

: 我表达有这么差劲咩＝。＝？
: 我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
: ，这个就是直接往回找就行了。

x*o2012-08-30 07:08

35 楼

谢谢，谢谢
一个月以后复诊
刚才又看了一篇paper， I131会在口水里面出现的比较多，时间比较长，最长是7天
而且I131 的半衰期只有8.02天
BTW，猫给I131的剂量只有4~5mCi，人最低的好像是给30mCi, paper 里面有讨论的最
低剂量是10mCi，限制已经非常少了
我在想，是不是只要注射I131之后的10天严格控制猫之间的接触就没有问题了
长时间separate他们，我觉得太残忍了

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

: 刚才看到了
: 可能是因为猫不如人听话吧，而且生命力强些
: 人回来肯定累到床上不动了
: 猫要是稍微恢复点就会到处转悠
: 而且回来肯定比较stress会想办法到处藏啊什么的，容易受到惊吓
: 自然要求多些
: 这几周还挺难熬的，不过回家就好回家就好。什么时候复诊啊？

c*n2012-08-30 07:08

36 楼

同问这题求所有partition的复杂度是什么？

t*u2012-08-30 07:08

37 楼

为了三猫好，忍了吧，不差这两个星期啊

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

: 谢谢，谢谢
: 一个月以后复诊
: 刚才又看了一篇paper， I131会在口水里面出现的比较多，时间比较长，最长是7天
: 而且I131 的半衰期只有8.02天
: BTW，猫给I131的剂量只有4~5mCi，人最低的好像是给30mCi, paper 里面有讨论的最
: 低剂量是10mCi，限制已经非常少了
: 我在想，是不是只要注射I131之后的10天严格控制猫之间的接触就没有问题了
: 长时间separate他们，我觉得太残忍了