Redian新闻
>
jumbo size pamper的code值多少点?
avatar
jumbo size pamper的code值多少点?# PennySaver - 省钱一族
b*n
1
做了这道题,被accepted, 但觉得代码很罗嗦冗长。
怎么改进呢?
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class ListNodeWrapper {
ListNode start;
ListNode end;
}
public class Solution {
private ListNode partionList(ListNode start, ListNode end) {
ListNode end1 = start;
ListNode fast = start;
while (fast != end) {
fast = fast.next;
if (fast != end) {
fast = fast.next;
end1 = end1.next;
}
}
return end1;
}
private ListNodeWrapper merge(ListNode start1, ListNode end1, ListNode
start2, ListNode end2) {
ListNode ln1 = start1;
ListNode ln2 = start2;
ListNode ln;
ListNodeWrapper lnw = new ListNodeWrapper();
if (ln1.val <= ln2.val) {
ln = ln1;
ln1 = ln1.next;
} else {
ln = ln2;
ln2 = ln2.next;
}
lnw.start = ln;
while (ln != end1 && ln != end2) {
if (ln1.val <= ln2.val) {
ln.next = ln1;
ln = ln.next;
ln1 = ln1.next;
} else {
ln.next = ln2;
ln = ln.next;
ln2 = ln2.next;
}
}
if (ln == end1) {
ln.next = ln2;
lnw.end = end2;
} else {
ln.next = ln1;
lnw.end = end1;
}
lnw.end.next = null;
return lnw;
}
private ListNodeWrapper mergeSort(ListNode start, ListNode end) {
ListNodeWrapper lnw = new ListNodeWrapper();
if (start == end) {
lnw.start = start;
lnw.end = end;
return lnw;
}
ListNode end1 = partionList(start, end);
ListNode start2 = end1.next;
ListNodeWrapper lnw1 = mergeSort(start, end1);
ListNodeWrapper lnw2 = mergeSort(start2, end);
lnw = merge(lnw1.start, lnw1.end, lnw2.start, lnw2.end);
return lnw;
}

public ListNode sortList(ListNode head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if (head == null) return null;
ListNode end = head;
while(end.next != null) end = end.next;
ListNodeWrapper lnw = mergeSort(head, end);
return lnw.start;
}
}
avatar
d*w
2
amazon买的大箱子的呢?
avatar
w*t
3
use a array to hold the intermediate results, merge them whenever a new
entry come and move it to next empty slot

【在 b*******n 的大作中提到】
: 做了这道题,被accepted, 但觉得代码很罗嗦冗长。
: 怎么改进呢?
: /**
: * Definition for singly-linked list.
: * class ListNode {
: * int val;
: * ListNode next;
: * ListNode(int x) {
: * val = x;
: * next = null;

avatar
i*y
4
jumbo size cruisers and swaddlers 36
amazon didn't buy and don't know

【在 d**w 的大作中提到】
: amazon买的大箱子的呢?
avatar
h*z
5
C++ looks shorter.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
if (!head || !head->next) return head;

ListNode *slow = head;
ListNode *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}

ListNode *p = slow->next;
slow->next = nullptr;
return merge(sortList(head), sortList(p));
}

private:
ListNode *merge(ListNode *p, ListNode *q) {
ListNode sentil(0);
ListNode *r = &sentil;
while (p && q) {
if (p->val > q->val) {
r->next = q;
q = q->next;
} else {
r->next = p;
p = p->next;
}
r = r->next;
}
if (p) r->next = p;
if (q) r->next = q;
return sentil.next;
}
};
avatar
M*8
6
baby dry 好象是20点
cruiser貌似30点
大箱里有几个code,合起来大概100左右吧,跟系列有关

【在 d**w 的大作中提到】
: amazon买的大箱子的呢?
avatar
g*e
7
我的也很长,但不用每个recursion都寻找中间node的位置。
class Solution {
public:
ListNode *merge(ListNode *a, ListNode *b, ListNode *&last) {
ListNode *res=NULL;
ListNode *prev=NULL;
while(a && b) {
if(res==NULL)
res=(a->val < b->val) ? a:b;
if(a->val < b->val) {
if(prev)
prev->next=a;
prev=a;
a=a->next;
} else {
if(prev)
prev->next=b;
prev=b;
b=b->next;
}
}
while(a) {
prev->next=a;
prev=prev->next;
last=prev;
a=a->next;
}
while(b) {
prev->next=b;
prev=prev->next;
last=prev;
b=b->next;
}
return res;
}
ListNode *mySortList(ListNode *&head, ListNode *&prev, int len) {
if(len==1) {
//if(prev)
// prev->next=head;
prev=head;
head=head->next;
return prev;
}
int lena=len/2;
int lenb=len-lena;
ListNode *aPrev=prev;
ListNode *left=mySortList(head, prev, lena);
ListNode *aTail=prev;
ListNode *right=mySortList(head, prev, lenb);
ListNode *bTail=prev;
aTail->next=NULL; bTail->next=NULL;
ListNode *last=NULL;
ListNode *merged=merge(left, right, last);
if(aPrev)
aPrev->next=merged;
last->next=head;
prev=last;
return merged;
}
ListNode *sortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ListNode *prev=NULL;
int cnt=0;
ListNode *t=head;
while(t) {
t=t->next; cnt++;
}
if(cnt==0)
return NULL;
return mySortList(head, prev, cnt);
}
};
avatar
d*w
8
还挺多的呢啊。可是要都拆开才能用呢。

【在 M*********8 的大作中提到】
: baby dry 好象是20点
: cruiser貌似30点
: 大箱里有几个code,合起来大概100左右吧,跟系列有关

avatar
m*n
9
使用插入排序是不是要好点。。。
avatar
b*9
10
那你啥时候拆开呢?

【在 d**w 的大作中提到】
: 还挺多的呢啊。可是要都拆开才能用呢。
avatar
m*n
11
偶没有看过leetcode,楼上几位都用merge sort是有什么原因吗?
avatar
M*8
12
大箱的里面有好几个小包,code 都贴在小包外面
所以只要拆开那个纸盒子,code就都可以用了

【在 d**w 的大作中提到】
: 还挺多的呢啊。可是要都拆开才能用呢。
avatar
d*x
13
nlogn

【在 m*******n 的大作中提到】
: 偶没有看过leetcode,楼上几位都用merge sort是有什么原因吗?
avatar
i*4
14
有了?cong~~
avatar
m*c
15
写了一个iterative method,参考了这个 http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
ListNode *sortList(ListNode *head) {
if (head == NULL)
return head;
int width = 1, firstSize, secondSize;
ListNode *tail;
while (true) {
ListNode *first = head;
ListNode *curr;
int nmerge = 0;
tail = NULL;
while (first) {
ListNode *second = first;
firstSize = 0;
nmerge++;
for (int i=0; isecond = second->next;
firstSize++;
if (second == NULL)
break;
}

secondSize = width;
while (firstSize > 0 || (secondSize > 0 && second)) {
if (first == 0) {
curr = second;
second = second->next;
secondSize--;
}
else if (secondSize == 0 || second == NULL) {
curr = first;
first = first->next;
firstSize--;
}
else if (first->val <= second->val) {
curr = first;
first = first->next;
firstSize--;
}
else {
curr = second;
second = second->next;
secondSize--;
}
if (tail == NULL) {
head = curr;
tail = head;
}
else {
taill->next = curr;
tail = tail->next;
}
} // end of merge lists
first = second;
} // end of this width
tail->next = NULL;
if (nmerge <= 1)
return head;
width *= 2;
}
}
avatar
d*w
16
我不拆,就屯着。。。。。

【在 b*******9 的大作中提到】
: 那你啥时候拆开呢?
avatar
c*w
17
我po个我的
public class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null)
return head;

ListNode slow=head;
ListNode fast=head.next;
while(fast!=null){
fast=fast.next;
if(fast!=null){
fast=fast.next;
slow=slow.next;
}
}

ListNode h1=head;
ListNode h2=slow.next;
slow.next=null;

h1=sortList(h1);
h2=sortList(h2);
return merge(h1, h2);
}

private ListNode merge(ListNode h1, ListNode h2){
ListNode dummy=new ListNode(-1);
dummy.next=h1;
ListNode d=dummy;

while(h1!=null&&h2!=null){
if(h1.val>=h2.val){
ListNode t=h2;
h2=h2.next;
while(d.next!=h1)
d=d.next;
t.next=h1;
d.next=t;
}
else
h1=h1.next;
}
if(h2!=null){
while(d.next!=null)
d=d.next;
d.next=h2;
}
return dummy.next;
}
}
avatar
s*x
18
better split into more functions like geeksforgeeks
http://www.geeksforgeeks.org/merge-sort-for-linked-list/
also, I do not think we really need to split the list to half and half first
, need to a similar way for converting single linked list to BST,
from bottom up, move the list accordingly.
still nlogn though.
avatar
b*e
19
这个题不用recursion怎么做?
avatar
d*n
20
Similar to yours but shorter:
ListNode *merge(ListNode *a,ListNode *b) {
ListNode sentil(0);
ListNode *r = &sentil;

while (a && b) {
if (a->val > b->val) {
r->next = b;
b = b->next;
} else {
r->next = a;
a = a->next;
}
r = r->next;
}
if (a) r->next = a;
if (b) r->next = b;
return sentil.next;
}

ListNode *mySortList(ListNode *&head, int len) {
if (len == 1) {
ListNode *tmp = head;
head = head->next;
tmp->next = NULL;
return tmp;
}

int lena=len/2;
int lenb=len-lena;
ListNode *a=mySortList(head, lena);
ListNode *b=mySortList(head, lenb);
ListNode *merged=merge(a, b);
return merged;
}

ListNode *sortList(ListNode *head) {
int cnt=0;
ListNode *t=head;
while(t) {
t=t->next; cnt++;
}
if(cnt <=1)
return head;
return mySortList(head, cnt);
}

【在 g*********e 的大作中提到】
: 我的也很长,但不用每个recursion都寻找中间node的位置。
: class Solution {
: public:
: ListNode *merge(ListNode *a, ListNode *b, ListNode *&last) {
: ListNode *res=NULL;
: ListNode *prev=NULL;
: while(a && b) {
: if(res==NULL)
: res=(a->val < b->val) ? a:b;
: if(a->val < b->val) {

avatar
t*8
21
iterate
for ( step = 1 to lengh/2)
compare and merge
or for ( step = len /2 to 1)
comparre and merge
4 5 2 1 6 8, 3, 7
4,5, 1, 2, 6, 8, 3, 7
1, 2, 4, 5, 3, 7, 6, 8
1, 2, 3, 4, 5, 6, 7, 8
or
4, 5, 2, 1, 6, 8, 3, 7
4, 6, 5, 8, 2, 3, 1, 7
2, 3, 4, 6, 1, 5, 7, 8
1, 2, 3, 4, 5, 6, 7, 8

【在 b*******e 的大作中提到】
: 这个题不用recursion怎么做?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。