HOT Target.com: Graco Melbourne Travel System AND Graco Me (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PennySaver - 省钱一族

HOT Target.com: Graco Melbourne Travel System AND Graco Me (转载)

HOT Target.com: Graco Melbourne Travel System AND Graco Me (转载)# PennySaver - 省钱一族

a*d2011-12-10 08:12

1 楼

Merge List
Given two lists of items (list1 and list2), each list is sorted based on
the
weight in ascending order. Now merge list1 and list2.
return a sorted merged list.
条件:
If one item in list1 has the same id as an item in list2, combine these two
items into one item and the weight is sum of the two previous weights.
Class Item{
int id;
float weight;
}
剩的时间太少, 想了一会没想出来, 感觉应该有个O(n)的解法. 感觉应该是个merge
sort 的变形
请大家指教了, 谢谢

x*g2011-12-10 08:12

2 楼

现在有chase 的普通checking和saving账户。打算升级成Chase sapphire checking拿
60k points或$750。
如果upgrade现有的checking，必须去店里面找人弄吗？
条款里说开户或升级后45天内转$75000进去，那这前1个月的balance就不到$75000，会
收月费吗？

l*j2011-12-10 08:12

3 楼

【以下文字转载自 NextGeneration 讨论区】
发信人: laomamj (老马虎), 信区: NextGeneration
标题: HOT Target.com: Graco Melbourne Travel System AND Graco Me
发信站: BBS 未名空间站 (Sat Dec 10 05:50:19 2011, 美东)
Target has Graco Melbourne Travel System (Regular $199.99) AND the Graco
Silhouette Melbourne Swing (Regularly $109) for just $149.99 plus tax and
they ship FREE!
go to Target.com
search Graco Travel System – Melbourne and add it to your cart. It is on
Price Cut for $149.99
Now enter the code TGTXBAP5 which will automatically add the swing in your
order for FREE!
3% cashback if u buy thru ebates, 苍蝇也是肉啊
open another browser window
google target 7 off 70 will give u additional $7 off（大苍蝇）
go back to initial browser window(ebates) refresh and check out to get 3% CB
给个包子吧

d*e2011-12-10 08:12

4 楼

要O（n）的话要用extra space吧
求大神给出 O（n） in place 解法

s*c2011-12-10 08:12

5 楼

相同的weight就挪到连成第三个list，这样不需要额外空间，三个list一起merge，还
是O(n)

two

【在 a******d 的大作中提到】

: Merge List
: Given two lists of items (list1 and list2), each list is sorted based on
: the
: weight in ascending order. Now merge list1 and list2.
: return a sorted merged list.
: 条件:
: If one item in list1 has the same id as an item in list2, combine these two
: items into one item and the weight is sum of the two previous weights.
: Class Item{
: int id;

b*e2011-12-10 08:12

6 楼

没有O(n)的解法。可以把排序问题归结到这个问题上。即如果这个问题有O(n)的解则排
序有O(n)的解。

two

【在 a******d 的大作中提到】

y*r2011-12-10 08:12

7 楼

感觉你这个不能保证递增啊，比如说你先碰到2，和它配对的是10，然后碰到3，和它配
对的是4，那按你的办法就是12，7了

k*u2011-12-10 08:12

8 楼

请问用extra space的话，如何做到O(n)? 请问可以稍微讲一讲吗？

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

: 要O（n）的话要用extra space吧
: 求大神给出 O（n） in place 解法

C*72011-12-10 08:12

9 楼

恩，条件理解错了。。

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

:
: 感觉你这个不能保证递增啊，比如说你先碰到2，和它配对的是10，然后碰到3，和它配
: 对的是4，那按你的办法就是12，7了

c*t2011-12-10 08:12

10 楼

用extra space的话，那太简单了。
按weight merge, 顺便加入
unordered_map map;
如果以前已经有这个id了，直接用指针去修改。

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

: 请问用extra space的话，如何做到O(n)? 请问可以稍微讲一讲吗？

b*52011-12-10 08:12

11 楼

return a sorted merged list.
你这个好像不return sorted merged list

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

: 用extra space的话，那太简单了。
: 按weight merge, 顺便加入
: unordered_map map;
: 如果以前已经有这个id了，直接用指针去修改。

j*y2011-12-10 08:12

12 楼

最近看到一个湾区大弓有个面试算法的班，我刚才还发帖问，不知道有用没有？求大牛
推荐，求指点。

m*g2011-12-10 08:12

13 楼

ListNode
{
int id; //assuming be non-negative
float weight;
ListNode* next;
}
merge(ListNode* l1, ListNode* l2)
{
ListNode l1head, h2head, l3head;
l1head->next = l1;
l2head->next = l2;
ListNode* l3 = &h3head;

//use hashtable to keep track of the id->weight pair.
unordered_map m;

// populate with l1 list
while(l1 != NULL)
{
m.insert(pair(l1->id, l1->weight));
l1 = l1->next;
}
//check l2 list
while(l2 != NULL)
{
auto it = m.find(l2->id);
if(it != m.end())
{
// add it to l3
ListNode* temp = new ListNode(l1->id, l1->weight+l2->weight);
l3->next = temp;
l3 = l3->next;
//mark node from both l1 and l2
it->id = -1;
l2->id = -1;
}
l2 = l2->next;
}
// merge three List. skip ones with "-1" id.

}

a*d2011-12-10 08:12

14 楼

这个不能保证第三个链表也是递增吧, 这样merge 三个链表结果就不是递增啊.

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

: ListNode
: {
: int id; //assuming be non-negative
: float weight;
: ListNode* next;
: }
: merge(ListNode* l1, ListNode* l2)
: {
: ListNode l1head, h2head, l3head;
: l1head->next = l1;

n*s2011-12-10 08:12

15 楼

Veli good, 是把相同ID的weight相加组成一个排好序的list再merge吧。

【在 s***c 的大作中提到】

: 相同的weight就挪到连成第三个list，这样不需要额外空间，三个list一起merge，还
: 是O(n)
:
: two

l*n2011-12-10 08:12

16 楼

re这个。
具体原因在于类似这样的case：(a2, b4)跟(b5, a6)的merge。假设可以线性处理，拿
到(a2, b9)的结果后，遇到a6了需要跟a2组合，可结果a8小于b9，需要通过比较插入到
非末位位置，于是不可能做到O(n)。

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

: 没有O(n)的解法。可以把排序问题归结到这个问题上。即如果这个问题有O(n)的解则排
: 序有O(n)的解。
:
: two