求建议，给老爸买生日礼物 - 未名空间MITBBS历史存档

b*u2010-08-25 07:08

1 楼

今天动手做了一下才发现挺复杂
用heap做怎么由value反查到相应的list？用哈希表的话是否需要 >
因为可能有重复value? 这样代码写起来好麻烦啊。
另外两两merge的方法，和heap的时间开销一样对吧，都是（nlogk) 假设k个list，总
共n个数

y*02010-08-25 07:08

2 楼

老爸下个月中过生日。已经和老妈过来照顾我一个月了，我的预产期是下月10号
老爸老妈每天都辛苦都收拾家和yard，给我做很多好吃的。觉得有爸妈在这里就是不一
样。
想给老爸买一个生日礼物，快70岁。我爸不太就讲穿，挺喜欢玩的。但是在这里语言不
通，也就整天在家里。
我可能会买一个好的轻便的相机，（爸爸很喜欢照相）但
是他不喜欢单反，觉得太重了。
PS，前两年回国给老爸随便买一个200多的，觉得一般吧。这次想买个好点的
大家给些意见吧。谢谢！

c*t2010-08-25 07:08

3 楼

要自己写一个 pair{ int index; int value} structure or class

>

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

: 今天动手做了一下才发现挺复杂
: 用heap做怎么由value反查到相应的list？用哈希表的话是否需要 >
: 因为可能有重复value? 这样代码写起来好麻烦啊。
: 另外两两merge的方法，和heap的时间开销一样对吧，都是（nlogk) 假设k个list，总
: 共n个数

l*a2010-08-25 07:08

4 楼

不喜欢单反... then shuang反?

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

: 老爸下个月中过生日。已经和老妈过来照顾我一个月了，我的预产期是下月10号
: 老爸老妈每天都辛苦都收拾家和yard，给我做很多好吃的。觉得有爸妈在这里就是不一
: 样。
: 想给老爸买一个生日礼物，快70岁。我爸不太就讲穿，挺喜欢玩的。但是在这里语言不
: 通，也就整天在家里。
: 我可能会买一个好的轻便的相机，（爸爸很喜欢照相）但
: 是他不喜欢单反，觉得太重了。
: PS，前两年回国给老爸随便买一个200多的，觉得一般吧。这次想买个好点的
: 大家给些意见吧。谢谢！

B*t2010-08-25 07:08

5 楼

为啥要保存value? 保存linked list node pointer不好了？

>

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

: 今天动手做了一下才发现挺复杂
: 用heap做怎么由value反查到相应的list？用哈希表的话是否需要 >
: 因为可能有重复value? 这样代码写起来好麻烦啊。
: 另外两两merge的方法，和heap的时间开销一样对吧，都是（nlogk) 假设k个list，总
: 共n个数

x*c2010-08-25 07:08

6 楼

预算?
整天在家玩相机也没多少拍照的机会啊

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

: 老爸下个月中过生日。已经和老妈过来照顾我一个月了，我的预产期是下月10号
: 老爸老妈每天都辛苦都收拾家和yard，给我做很多好吃的。觉得有爸妈在这里就是不一
: 样。
: 想给老爸买一个生日礼物，快70岁。我爸不太就讲穿，挺喜欢玩的。但是在这里语言不
: 通，也就整天在家里。
: 我可能会买一个好的轻便的相机，（爸爸很喜欢照相）但
: 是他不喜欢单反，觉得太重了。
: PS，前两年回国给老爸随便买一个200多的，觉得一般吧。这次想买个好点的
: 大家给些意见吧。谢谢！

p*p2010-08-25 07:08

7 楼

heap直接放node就行了啊，贴个java的，c++也一样的
public class Solution {
public ListNode mergeKLists(ArrayList lists) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode root = null;
ListNode current = null;
if (lists.isEmpty()) return null;
Queue queue = new PriorityQueue(lists.size(), new
Comparator() {
public int compare(ListNode n1, ListNode n2) {
return n1.val - n2.val;
}
});

for (ListNode node : lists) {
if (node == null) continue;
queue.offer(node);
}

while (queue.size() > 0) {
ListNode node = queue.poll();
if (node.next != null) {
queue.offer(node.next);
}
if (root == null) {
root = node;
current = node;
}
else {
current.next = node;
current = current.next;
}
}

return root;
}
}

>

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

: 今天动手做了一下才发现挺复杂
: 用heap做怎么由value反查到相应的list？用哈希表的话是否需要 >
: 因为可能有重复value? 这样代码写起来好麻烦啊。
: 另外两两merge的方法，和heap的时间开销一样对吧，都是（nlogk) 假设k个list，总
: 共n个数

c*e2010-08-25 07:08

8 楼

我也刚给老爸买了生日礼物，Ipad，够老爷子玩一阵了, hehe

c*t2010-08-25 07:08

9 楼

原题是merge k way linkedlist啊, 做了一遍leetcode, 都忘了，

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

: heap直接放node就行了啊，贴个java的，c++也一样的
: public class Solution {
: public ListNode mergeKLists(ArrayList lists) {
: // Start typing your Java solution below
: // DO NOT write main() function
: ListNode root = null;
: ListNode current = null;
: if (lists.isEmpty()) return null;
: Queue queue = new PriorityQueue(lists.size(), new
: Comparator() {

y*02010-08-25 07:08

10 楼

预算500，600 百吧
买了老爸回国也可以用。就算在这里，有时和我们一切出去玩，或者自己在附近转转也
可以用的呀
ipad也不错，只是老爸眼睛不好，有特别喜欢小游戏。我怕他上瘾

b*u2010-08-25 07:08

11 楼

多谢!
还是平时对priority_queue玩得不够熟，都没试过重载Compare()

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

: heap直接放node就行了啊，贴个java的，c++也一样的
: public class Solution {
: public ListNode mergeKLists(ArrayList lists) {
: // Start typing your Java solution below
: // DO NOT write main() function
: ListNode root = null;
: ListNode current = null;
: if (lists.isEmpty()) return null;
: Queue queue = new PriorityQueue(lists.size(), new
: Comparator() {

q*z2010-08-25 07:08

12 楼

sony nex5吧

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

: 老爸下个月中过生日。已经和老妈过来照顾我一个月了，我的预产期是下月10号
: 老爸老妈每天都辛苦都收拾家和yard，给我做很多好吃的。觉得有爸妈在这里就是不一
: 样。
: 想给老爸买一个生日礼物，快70岁。我爸不太就讲穿，挺喜欢玩的。但是在这里语言不
: 通，也就整天在家里。
: 我可能会买一个好的轻便的相机，（爸爸很喜欢照相）但
: 是他不喜欢单反，觉得太重了。
: PS，前两年回国给老爸随便买一个200多的，觉得一般吧。这次想买个好点的
: 大家给些意见吧。谢谢！

l*52010-08-25 07:08

13 楼

最后的if else是干什么的呀？？

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

: heap直接放node就行了啊，贴个java的，c++也一样的
: public class Solution {
: public ListNode mergeKLists(ArrayList lists) {
: // Start typing your Java solution below
: // DO NOT write main() function
: ListNode root = null;
: ListNode current = null;
: if (lists.isEmpty()) return null;
: Queue queue = new PriorityQueue(lists.size(), new
: Comparator() {

s*y2010-08-25 07:08

14 楼

2nd

【在 q*z 的大作中提到】

: sony nex5吧

a*l2010-08-25 07:08

15 楼

of course, what a no-brainer? hehe

【在 q*z 的大作中提到】

: sony nex5吧

x52010-08-25 07:08

16 楼

3rd

【在 q*z 的大作中提到】

: sony nex5吧