r******3
发帖数: 221 | 1 Given a sorted linked list, delete all duplicate numbers, leave only
distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
1->2->5. Given 1->1->1->2->3, return 2->3.
要求扫一遍，O(1) space。 |
p*****2
发帖数: 21240 | 2 import java.io.*;
import java.util.*;
public class test3
{
public static void main(String[] args) throws Exception
{
new test3().run();
}
PrintWriter out = null;
void print(Node head)
{
while (head != null)
{
out.print(head.value + " ");
head = head.next;
}
out.println();
}
Node remove(Node head)
{
Node prev = head;
head = null;
Node pp = null;
while (prev != null)
{
Node next = prev.next;
while (next != null && next.value == prev.value)
next = next.next;
if (next == prev.next)
{
if (head == null)
{
head = prev;
pp = head;
}
else
{
pp.next = prev;
pp = prev;
}
}
prev = next;
}
return head;
}
void run() throws Exception
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
int[][] arr = new int[][]
{
{ 1, 2, 3, 3, 4, 4, 5 },
{ 1, 1, 1, 2, 3 } };
for (int k = 0; k < arr.length; k++)
{
Node head = null;
Node prev = null;
for (int i : arr[k])
{
Node node = new Node(i);
if (head == null)
head = node;
else
prev.next = node;
prev = node;
}
print(head);
head = remove(head);
print(head);
}
out.close();
}
}
class Node
{
int value;
Node next;
public Node(int v)
{
value = v;
}
} |
C***U
发帖数: 2406 | 3 用两个指针就可以了吧
return
【在 r******3 的大作中提到】
: Given a sorted linked list, delete all duplicate numbers, leave only
: distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
: 1->2->5. Given 1->1->1->2->3, return 2->3.
: 要求扫一遍，O(1) space。
|
m*****k
发帖数: 731 | 4 result_head=null;
result_tail=null;
candidate=head;
candidate_good = true;
to-check=head.next;
while(to-check!=null)
{
if(to-check.value==candidate.value)
{
candidate_good = false;
}
else
{
if(candidate_good)
{
append_candiate_to_result();
//reset candiate
candidate = to_check;
candidate_good = true;
}
}
to-check = to-check.next;
}
if(candidate_good )
{
append_candiate_to_result()
}
return result_head ;
------------------------------------------------------
void append_candiate_to_result()
{
if(result_tail==null)
{
result_head = candidate;
result_tail = candidate;
}
else
{
result_tail.next = candidate;
result_tail= candidate;
}
} |
h****e
发帖数: 928 | 5 public static void remove_duplicates(Node head) {
if (head==null || head.next==null) {
return;
}
int data = head.data;
Node previous = head;
Node current = head.next;
while (current!=null) {
if (data==current.data) {
current = current.next;
previous.next = current;
} else {
data = current.data;
previous = current;
current = current.next;
}
}
} |
r****k
发帖数: 21 | 6 顺手写了一下，调试一堆bug，汗...
好多workaround.
Node * deleteDuplicate(Node *head)
{
if (head == NULL) return NULL;
Node *p = head;
Node *q = p->next;
if (q == NULL)
return head;
Node *last = NULL;
head = last;
while (q != NULL)
{
if (p->data != q->data)
{
if (last == NULL)
{
head = last = p;
}
else
{
last->next = p;
last = p;
}
p = p->next;
q = q->next;
}
else
{
while (q->next != NULL && q->next->data == p->data)
q = q->next;
q = q->next;
while (p != q)
{
Node *del = p;
p = p->next;
delete(del);
}
if (q != NULL)
q = q->next;
}
}
if ( q == NULL && p != NULL)
{
if (last == NULL)
{
head = last = p;
}
else
{
last->next = p;
last = p;
}
}
if (last != NULL)
{
last->next = NULL;
}
return head;
} |
n****r
发帖数: 120 | 7 楼上的代码有明显的BUG!
【在 h****e 的大作中提到】
: public static void remove_duplicates(Node head) {
: if (head==null || head.next==null) {
: return;
: }
: int data = head.data;
: Node previous = head;
: Node current = head.next;
: while (current!=null) {
: if (data==current.data) {
: current = current.next;
|
n****r
发帖数: 120 | 8 public static void removeDuplicats(Node x){
if(x == null || x.next == null) return;
Node cur = x;
while(cur != null && cur.next != null){
Node next = cur.next;
while(cur.value == next.value){
next = next.next;
if(next == null)
break;
}
cur.next = next;
cur = next;
}
} |
l*********8
发帖数: 4642 | 9 Node * DeleteDuplicates(Node * head)
{
if (!head) return head;
Node tmpHead;
tmpHead.next = head;
Node *prev, *cur, *p;
prev = &tmpHead;
do {
bool isUnique = true;
cur = prev->next；
p = cur->next；
while(p && p->val == cur->val) {
isUnique = false;
cur->next = p->next;
delete p;
p = cur->next;
}
if (isUnique) {
prev = cur;
} else {
prev->next = cur->next;
delete cur;
}
}while(prev->next);
return tmpHead.next;
} |
m*****g
发帖数: 226 | 10 void removeDuplicated(node* ll)
{
if(!ll) return;
if(!ll->next) return;
node* ptr1, ptr2;
ptr1 = ll;
ptr2 = ptr1->next;
while(1)
{
if(ptr1->v == ptr2->v)
{
while(ptr1->v == ptr2->v)
{
node* ptr3 = ptr2->next;
llDeleteNode(ll,ptr3);
ptr2 = ptr3;
if(!ptr2) break;
}
llDeleteNode(ll, ptr1);
if(!ptr2) return;
if(!ptr2->next) return;
ptr1 = ptr2;
ptr2 = ptr2->next;
}
}
} |
|
|
g**x
发帖数: 373 | 11 What about the case:
->1->2->2->3->3->3->2->1->1->5?
Is the return supposed to be
->5 ?
return
【在 r******3 的大作中提到】
: Given a sorted linked list, delete all duplicate numbers, leave only
: distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
: 1->2->5. Given 1->1->1->2->3, return 2->3.
: 要求扫一遍，O(1) space。
|
l*********8
发帖数: 4642 | 12 the list is already sorted.
【在 g**x 的大作中提到】
: What about the case:
: ->1->2->2->3->3->3->2->1->1->5?
: Is the return supposed to be
: ->5 ?
:
: return
|
g**x
发帖数: 373 | 13 Thanks. My bad.
【在 l*********8 的大作中提到】
: the list is already sorted.
|
l*****a
发帖数: 14598 | 14 一看就是死循环。
细节都不用看
【在 m*****g 的大作中提到】
: void removeDuplicated(node* ll)
: {
: if(!ll) return;
: if(!ll->next) return;
: node* ptr1, ptr2;
: ptr1 = ll;
: ptr2 = ptr1->next;
: while(1)
: {
: if(ptr1->v == ptr2->v)
|
p*****2
发帖数: 21240 | 15
牛。我发现我看别人程序很弱
【在 l*****a 的大作中提到】
: 一看就是死循环。
: 细节都不用看
|
h****e
发帖数: 928 | 16 可以举出反例吗？我试了几种情况都没有错。
我的做法是看到一个重复的结点就跳过去，而不是一批一批地跳。
这样只要用一层while循环就可以了，还减少了需要的边界条件
检查。
【在 n****r 的大作中提到】
: 楼上的代码有明显的BUG!
|
Z*****Z
发帖数: 723 | 17 1,1,2，你会返回1,2，因为你不改head
【在 h****e 的大作中提到】
: 可以举出反例吗？我试了几种情况都没有错。
: 我的做法是看到一个重复的结点就跳过去，而不是一批一批地跳。
: 这样只要用一层while循环就可以了，还减少了需要的边界条件
: 检查。
|
h****e
发帖数: 928 | 18 Sorry，题目理解错了。 :(
【在 Z*****Z 的大作中提到】
: 1,1,2，你会返回1,2，因为你不改head
|
O*******d
发帖数: 20343 | 19 一个指针就可以了。 每走一步，把当前值和前一个值比较，如果相同，把当前值删掉
。 如果不同，把当前值做一个copy，下一步时和这个值比较。
【在 C***U 的大作中提到】
: 用两个指针就可以了吧
:
: return
|
O*******d
发帖数: 20343 | 20 关键词 “sorted”
【在 g**x 的大作中提到】
: What about the case:
: ->1->2->2->3->3->3->2->1->1->5?
: Is the return supposed to be
: ->5 ?
:
: return
|
|
|
p*****2
发帖数: 21240 | 21
are you sure? sounds not right.
【在 O*******d 的大作中提到】
: 一个指针就可以了。 每走一步，把当前值和前一个值比较，如果相同，把当前值删掉
: 。 如果不同，把当前值做一个copy，下一步时和这个值比较。
|
h****e
发帖数: 928 | 22 再试一次。这次给出的是递归的解法。
public static Node remove_all(Node head) {
if (head==null || head.next==null) {
return head;
}
int data = head.data;
Node current = head.next;
if (data==current.data) {
do {
current = current.next;
} while (current!=null && current.data == data);
if (current==null) {
return current;
}
return remove_all(current);
}
Node next = remove_all(current);
head.next = next;
return head;
} |
l*****a
发帖数: 14598 | 23 主要是他这个太明显了。。
【在 p*****2 的大作中提到】
:
: are you sure? sounds not right.
|
Z*****Z
发帖数: 723 | 24 cool,觉得这次对了
【在 h****e 的大作中提到】
: 再试一次。这次给出的是递归的解法。
: public static Node remove_all(Node head) {
: if (head==null || head.next==null) {
: return head;
: }
: int data = head.data;
: Node current = head.next;
: if (data==current.data) {
: do {
: current = current.next;
|
h**l
发帖数: 168 | 25 LinkedListNode* removeDup(LinkedListNode* head)
{
if(head == NULL) return head;
LinkedListNode* prev, *current, *next;
prev = head;
current = head;
next = current->next;
bool FirstUnique = true;
while (next!=NULL)
{
while(next->value == current->value)
{
next = next->next;
if(next == NULL) break;
}
if(next == current->next)
{
if(FirstUnique)
{
head = current;
FirstUnique = false;
}
prev = current;
}
else
{
prev->next = next;
}
current = next;
if(current == NULL) break;
next = current->next;
}
if(FirstUnique) head = current;
return head;
}
return
【在 r******3 的大作中提到】
: Given a sorted linked list, delete all duplicate numbers, leave only
: distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
: 1->2->5. Given 1->1->1->2->3, return 2->3.
: 要求扫一遍，O(1) space。
|
h****e
发帖数: 928 | 26 多谢！
【在 Z*****Z 的大作中提到】
: cool,觉得这次对了
|
p*****2
发帖数: 21240 | 27
这题上了leetcode的OJ，你可以上边再run一下。这样就会很有信心了。
【在 h****e 的大作中提到】
: 多谢！
|
l*********8
发帖数: 4642 | 28 北京二爷，你的程序有bug
try {1, 2, 2}
【在 p*****2 的大作中提到】
: import java.io.*;
: import java.util.*;
: public class test3
: {
: public static void main(String[] args) throws Exception
: {
: new test3().run();
: }
: PrintWriter out = null;
: void print(Node head)
|
p*****2
发帖数: 21240 | 29
多谢。得出去一下。回来调一下。这好像是很多题都容易出的bug。
【在 l*********8 的大作中提到】
: 北京二爷，你的程序有bug
: try {1, 2, 2}
|
p*****2
发帖数: 21240 | 30
更新了一下。确实是个常见的问题。昨天做另外一题也出线这问题了。还是得小心。
【在 p*****2 的大作中提到】
:
: 多谢。得出去一下。回来调一下。这好像是很多题都容易出的bug。
|
|
|
l*********8
发帖数: 4642 | 31 目前，leetcode上这道题目的OJ的expected output还有很多错误的。希望leetcode更新一
下。谢谢！
【在 p*****2 的大作中提到】
:
: 更新了一下。确实是个常见的问题。昨天做另外一题也出线这问题了。还是得小心。
|
m*****k
发帖数: 731 | 32 1 -> 1
so you have 1?
【在 O*******d 的大作中提到】
: 一个指针就可以了。 每走一步，把当前值和前一个值比较，如果相同，把当前值删掉
: 。 如果不同，把当前值做一个copy，下一步时和这个值比较。
|
p*****2
发帖数: 21240 | 33
更新一
是吗？我还没run过。其实不OJ一下真的没有信心。
【在 l*********8 的大作中提到】
: 目前，leetcode上这道题目的OJ的expected output还有很多错误的。希望leetcode更新一
: 下。谢谢！
|
l*********8
发帖数: 4642 | 34 我的意思是， 目前OJ上的答案本身是错的 :-)
你改过后的程序还有一个小bug, 除此之外应该就没问题了：）
【在 p*****2 的大作中提到】
:
: 更新一
: 是吗？我还没run过。其实不OJ一下真的没有信心。
|
h****e
发帖数: 928 | 35 谢谢。LeetCode加得好快。
【在 p*****2 的大作中提到】
:
: 更新一
: 是吗？我还没run过。其实不OJ一下真的没有信心。
|
p*****2
发帖数: 21240 | 36
我知道你的意思。
还有啥bug呢？指点一下吧。OJ能发现吗？我晚上OJ一下。
【在 l*********8 的大作中提到】
: 我的意思是， 目前OJ上的答案本身是错的 :-)
: 你改过后的程序还有一个小bug, 除此之外应该就没问题了：）
|
l*********8
发帖数: 4642 | 37 输入空链表的时候，你的这句会crash.
pp.next = null;
【在 p*****2 的大作中提到】
:
: 我知道你的意思。
: 还有啥bug呢？指点一下吧。OJ能发现吗？我晚上OJ一下。
|
p*****2
发帖数: 21240 | 38
明白了。得加个判断。多谢。刚才有点着急修改。我觉得你可真牛，看别人代码这么仔
细。我一般都不怎么看别人代码。看也只是看个思路。
【在 l*********8 的大作中提到】
: 输入空链表的时候，你的这句会crash.
: pp.next = null;
|
h****e
发帖数: 928 | 39 真的是不上版上来让大牛检查一下，或者到OJ上过一遍，
自己错了都不知道。:) |
l*********8
发帖数: 4642 | 40 我一点儿也不牛。你程序一开始的bug比较隐蔽，我开始没看出来。 后来加了些test
cases跑了之后才发现的。
你后来出现的bug比较容易看出来。你改的急了才出这个错的。
【在 p*****2 的大作中提到】
:
: 明白了。得加个判断。多谢。刚才有点着急修改。我觉得你可真牛，看别人代码这么仔
: 细。我一般都不怎么看别人代码。看也只是看个思路。
|
|
|
i**********e
发帖数: 1145 | 41 我还没加这道题吧，现在正在加。
对了，还有什么题目 test case 你发现有错误的？
【在 l*********8 的大作中提到】
: 我的意思是， 目前OJ上的答案本身是错的 :-)
: 你改过后的程序还有一个小bug, 除此之外应该就没问题了：）
|
l*********8
发帖数: 4642 | 42 我是用Remove Duplicates II 来做online judge的。 （把输入输出转换了一下）
刚才我才发现我想当然地以为， 既然Remove Duplicates是重复的数字只保留一次，那么
Remove Duplicates II 就是把重复的数字全部删除。。。。而实际上，Remove Duplicates
II是说一个数字最多重复两次。 ⊙﹏⊙b汗
【在 i**********e 的大作中提到】
: 我还没加这道题吧，现在正在加。
: 对了，还有什么题目 test case 你发现有错误的？
|
i**********e
发帖数: 1145 | 43 这道题不同，是删除所有出现超过一次的元素，而不是去重。
如果单单只是去重的话会比较容易一些。
北京二爷，你的bug修改了没？
那么
Duplicates
【在 l*********8 的大作中提到】
: 我是用Remove Duplicates II 来做online judge的。 （把输入输出转换了一下）
: 刚才我才发现我想当然地以为， 既然Remove Duplicates是重复的数字只保留一次，那么
: Remove Duplicates II 就是把重复的数字全部删除。。。。而实际上，Remove Duplicates
: II是说一个数字最多重复两次。 ⊙﹏⊙b汗
|
i**********e
发帖数: 1145 | 44 刚加了这道题进 OJ，题目名字叫 “Remove Duplicates from Sorted List II”，大
家可以测一下程序。
只测了 longway2008 和 hackie 的程序，都是正确的。 |
Z*****Z
发帖数: 723 | 45 Orz 赞!
搭车问可不可以请求加上直方图下最大矩形面积这题
【在 i**********e 的大作中提到】
: 刚加了这道题进 OJ，题目名字叫 “Remove Duplicates from Sorted List II”，大
: 家可以测一下程序。
: 只测了 longway2008 和 hackie 的程序，都是正确的。
|
i**********e
发帖数: 1145 | 46 哦，那道题很难啊，我尽量尝试看看能不能今天加上去。
谢谢你的建议！
【在 Z*****Z 的大作中提到】
: Orz 赞!
: 搭车问可不可以请求加上直方图下最大矩形面积这题
|
d**e
发帖数: 6098 | 47 你真是勤快,星期天还工作... :)
【在 i**********e 的大作中提到】
: 哦，那道题很难啊，我尽量尝试看看能不能今天加上去。
: 谢谢你的建议！
|
i**********e
发帖数: 1145 | 48 人生苦短，现在不勤快，老了就勤快不动了。
【在 d**e 的大作中提到】
: 你真是勤快,星期天还工作... :)
|
l*********8
发帖数: 4642 | 49 赞！
动作很快啊
【在 i**********e 的大作中提到】
: 刚加了这道题进 OJ，题目名字叫 “Remove Duplicates from Sorted List II”，大
: 家可以测一下程序。
: 只测了 longway2008 和 hackie 的程序，都是正确的。
|
w**z
发帖数: 8232 | 50 面试的时候，对这样的题会要求写出没bug的程序？是白板coding，面试的人也不一定
读了你的code就能发现bug。
在工作中，遇到这样的东东，会象OJ那样写很多unit test的，一般不会用眼睛debug吧。
那么
Duplicates
【在 l*********8 的大作中提到】
: 我是用Remove Duplicates II 来做online judge的。 （把输入输出转换了一下）
: 刚才我才发现我想当然地以为， 既然Remove Duplicates是重复的数字只保留一次，那么
: Remove Duplicates II 就是把重复的数字全部删除。。。。而实际上，Remove Duplicates
: II是说一个数字最多重复两次。 ⊙﹏⊙b汗
|
|
|
k*****y
发帖数: 744 | 51 ListNode *deleteDuplicate(ListNode *head){
ListNode *newHead = NULL, *newLast = NULL;
ListNode *next;
while(head){
next = head->next;
while(next && next->val == head->val) next = next->next;
if(next == head->next){
if( newLast ){
newLast->next = new ListNode(head->val);
newLast = newLast->next;
}
else
newHead = newLast = new ListNode(head->val);
}
head = next;
}
return newHead;
} |
z****h
发帖数: 164 | 52 public ListNode deleteDuplicates(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
if(head == null || head.next == null) return head;
ListNode curr = head;
ListNode pre = null;
boolean isdup = false;
while(curr.next != null)
{
if(curr.val == curr.next.val){
isdup = true;
curr.next = curr.next.next;
}else
{
if(isdup == true)
{
if(pre == null)
{
head = curr.next;
curr = head;
}else
{
pre.next = curr.next;
curr = pre.next;
}
isdup = false;
}else{
pre = curr;
curr = curr.next;
}
}
}
if(isdup)
{
if(pre != null)
pre.next = null;
else head = null;
}
return head;
} |
s******o
发帖数: 2233 | 53 Node*
GetNextNondupNode(Node* node) {
if (!node || !node->next_ ||
node->data_ != node->next_->data_) {
return node;
}
while (node && node->next_ &&
node->data_ == node->next_->data_) {
Node* tmp = node;
node = node->next_;
delete tmp;
}
node = node->next_;
return GetNextNondupNode(node);
}
Node*
RemoveDup(Node* head) {
head = GetNextNondupNode(head);
if (!head) {
return NULL;
Node* prev = head;
while (Node* node = prev->next_) {
node = GetNextNondupNode(node);
prev->next_ = node;
prev = node;
}
return head;
}
return
【在 r******3 的大作中提到】
: Given a sorted linked list, delete all duplicate numbers, leave only
: distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
: 1->2->5. Given 1->1->1->2->3, return 2->3.
: 要求扫一遍，O(1) space。
|
l*****a
发帖数: 14598 | 54 为什么data member的命名都是最后加个_
这是什么风格？
【在 s******o 的大作中提到】
: Node*
: GetNextNondupNode(Node* node) {
: if (!node || !node->next_ ||
: node->data_ != node->next_->data_) {
: return node;
: }
: while (node && node->next_ &&
: node->data_ == node->next_->data_) {
: Node* tmp = node;
: node = node->next_;
|
s******o
发帖数: 2233 | |
l*y
发帖数: 21010 | |
l*****a
发帖数: 14598 | |
l*****a
发帖数: 14598 | 58 总感觉有些不太简洁。。。。
前面hackie的那个挺好。。。
【在 s******o 的大作中提到】
: Node*
: GetNextNondupNode(Node* node) {
: if (!node || !node->next_ ||
: node->data_ != node->next_->data_) {
: return node;
: }
: while (node && node->next_ &&
: node->data_ == node->next_->data_) {
: Node* tmp = node;
: node = node->next_;
|
d**e
发帖数: 6098 | |
d**e
发帖数: 6098 | 60 人生苦短，不是应该及时行乐吗?
不过写code就是你的快乐源泉 :p
【在 i**********e 的大作中提到】
: 人生苦短，现在不勤快，老了就勤快不动了。
|
|
|
s******o
发帖数: 2233 | 61 每个公司都有自己的style guide，只要自己的code base consistent就好了。。。
【在 d**e 的大作中提到】
: 似乎我们都是习惯写前面的。。。
|
O*******d
发帖数: 20343 | 62 给你一个C＋＋的例子
void removeDuplicates(list& sortedList)
{
if(sortedList.size() > 0)
{
list::iterator it = sortedList.begin();
// Set to a value that is not the first value to prevent deleting
the first value
int previous = *sortedList.begin() + 1;
while(it != sortedList.end())
{
if(*it == previous)
{
it = sortedList.erase(it);
}
else
{
previous = *it;
++it;
}
}
}
}
那个iterator尽管不是真正意义上的指针，但在这里使用，相当于指针。 一个就够用
了。
【在 p*****2 的大作中提到】
:
: 明白了。得加个判断。多谢。刚才有点着急修改。我觉得你可真牛，看别人代码这么仔
: 细。我一般都不怎么看别人代码。看也只是看个思路。
|
s******o
发帖数: 2233 | 63 stl::list is doubly-linked list
【在 O*******d 的大作中提到】
: 给你一个C＋＋的例子
: void removeDuplicates(list& sortedList)
: {
: if(sortedList.size() > 0)
: {
: list::iterator it = sortedList.begin();
: // Set to a value that is not the first value to prevent deleting
: the first value
: int previous = *sortedList.begin() + 1;
: while(it != sortedList.end())
|
O*******d
发帖数: 20343 | 64 在我的码中，那个iterator只往前走，不后退，就跟单链一样。
【在 s******o 的大作中提到】
: stl::list is doubly-linked list
|
s******o
发帖数: 2233 | 65 for std::slist, erase is O(N) operation
【在 O*******d 的大作中提到】
: 在我的码中，那个iterator只往前走，不后退，就跟单链一样。
|
l*****a
发帖数: 14598 | 66 你运行过吗？
what does *sortedList mean?
【在 O*******d 的大作中提到】
: 给你一个C＋＋的例子
: void removeDuplicates(list& sortedList)
: {
: if(sortedList.size() > 0)
: {
: list::iterator it = sortedList.begin();
: // Set to a value that is not the first value to prevent deleting
: the first value
: int previous = *sortedList.begin() + 1;
: while(it != sortedList.end())
|
p*****2
发帖数: 21240 | 67
刚回来。改了，刚刚OJ过了。
【在 i**********e 的大作中提到】
: 这道题不同，是删除所有出现超过一次的元素，而不是去重。
: 如果单单只是去重的话会比较容易一些。
: 北京二爷，你的bug修改了没？
:
: 那么
: Duplicates
|
d**e
发帖数: 6098 | 68 这个好像是将duplicate删成1个
比如1->1->2出来是1->2,而不是将全部1删掉？
但很喜欢你的previous初始化
我想如果用一个指针的话，可能可以用node->next和node->next->next
【在 O*******d 的大作中提到】
: 给你一个C＋＋的例子
: void removeDuplicates(list& sortedList)
: {
: if(sortedList.size() > 0)
: {
: list::iterator it = sortedList.begin();
: // Set to a value that is not the first value to prevent deleting
: the first value
: int previous = *sortedList.begin() + 1;
: while(it != sortedList.end())
|
i**********e
发帖数: 1145 | 69 刚把这题加进 OJ 里了，解法还挺多的。
brute force 的 O(N^2) 应该是过不了 large tests 的。
"Largest Rectangle in Histogram"
Given n non-negative integers representing the histogram's bar height where
the width of each bar is 1, find the area of largest rectangle in the
histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2
,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.
【在 Z*****Z 的大作中提到】
: Orz 赞!
: 搭车问可不可以请求加上直方图下最大矩形面积这题
|
p*****2
发帖数: 21240 | 70 这题想了想还没太好思路 面是肯定挂
刚把这题加进 OJ 里了，解法还挺多的。brute force 的 O(N^2) 应该是过不了 large
tests 的。"Largest Rectangle in Hist........
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
【在 i**********e 的大作中提到】
: 刚把这题加进 OJ 里了，解法还挺多的。
: brute force 的 O(N^2) 应该是过不了 large tests 的。
: "Largest Rectangle in Histogram"
: Given n non-negative integers representing the histogram's bar height where
: the width of each bar is 1, find the area of largest rectangle in the
: histogram.
: Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2
: ,3].
: The largest rectangle is shown in the shaded area, which has area = 10 unit.
: For example,
|
|
|
p*****2
发帖数: 21240 | 71 想了一个nlongn的，过了小数据，大数据runtime error.
int max = 0;
public int largestRectangleArea(int[] height)
{
max = 0;
find(height, 0, height.length - 1);
return max;
}
void find(int[] height, int x, int y)
{
int lowest = Integer.MAX_VALUE;
for (int i = x; i <= y; i++)
lowest = Math.min(lowest, height[i]);
max = Math.max(max, lowest * (y - x + 1));
int prev = x;
int i = x;
while (prev <= y && i <= y)
{
while (prev <= y && height[prev] == lowest)
prev++;
if(prev>y)
break;
i = prev + 1;
while (i <= y && height[i] != lowest)
i++;
find(height, prev, i - 1);
prev = i;
}
}
where
,2
unit.
【在 i**********e 的大作中提到】
: 刚把这题加进 OJ 里了，解法还挺多的。
: brute force 的 O(N^2) 应该是过不了 large tests 的。
: "Largest Rectangle in Histogram"
: Given n non-negative integers representing the histogram's bar height where
: the width of each bar is 1, find the area of largest rectangle in the
: histogram.
: Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2
: ,3].
: The largest rectangle is shown in the shaded area, which has area = 10 unit.
: For example,
|
k*****y
发帖数: 744 | 72 Maintain the increasing subsequence ending at current position. Should run
in O(n) time.
int largestRectangleArea( vector &height ){
stack< pair > st;
st.push( make_pair(-1, 0) );
int ans = 0;
for( int ith=0; ith
int pos = ith;
while(1){
pair &top = st.top();
if(top.second > height[ith] ){
pos = top.first;
ans = max( ans, top.second*(ith - pos) );
st.pop();
}
else{
if(top.second < height[ith])
st.push( make_pair( pos, height[ith] ) );
break;
}
}
}
while( !st.empty() ){
pair &top = st.top();
ans = max( ans, top.second*(int(height.size()) - top.first) );
st.pop();
}
return ans;
}
where
,2
unit.
【在 i**********e 的大作中提到】
: 刚把这题加进 OJ 里了，解法还挺多的。
: brute force 的 O(N^2) 应该是过不了 large tests 的。
: "Largest Rectangle in Histogram"
: Given n non-negative integers representing the histogram's bar height where
: the width of each bar is 1, find the area of largest rectangle in the
: histogram.
: Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2
: ,3].
: The largest rectangle is shown in the shaded area, which has area = 10 unit.
: For example,
|
i**********e
发帖数: 1145 | 73 你的最后第二 large test case stack overflow 了，是递归造成的。
n = 20000,
height = [0, 1, 2, ... 19999]
【在 p*****2 的大作中提到】
: 想了一个nlongn的，过了小数据，大数据runtime error.
: int max = 0;
: public int largestRectangleArea(int[] height)
: {
: max = 0;
: find(height, 0, height.length - 1);
: return max;
: }
: void find(int[] height, int x, int y)
: {
|
Z*****Z
发帖数: 723 | 74 大赞，多谢！
where
,2
unit.
【在 i**********e 的大作中提到】
: 刚把这题加进 OJ 里了，解法还挺多的。
: brute force 的 O(N^2) 应该是过不了 large tests 的。
: "Largest Rectangle in Histogram"
: Given n non-negative integers representing the histogram's bar height where
: the width of each bar is 1, find the area of largest rectangle in the
: histogram.
: Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2
: ,3].
: The largest rectangle is shown in the shaded area, which has area = 10 unit.
: For example,
|
b******u
发帖数: 81 | 75 public static Node RemoveDuplicates(Node node)
{
Node result = null, resultCurrent = null, current = node;
bool skipCurrent = false;
while (current != null )
{
if (current.Next != null && current.Num == current.Next.Num)
{
skipCurrent = true;
}
else
{
if (!skipCurrent)
{
if (result == null)
{
result = current;
resultCurrent = current;
}
else
{
resultCurrent.Next = current;
resultCurrent = resultCurrent.Next;
}
}
skipCurrent = false;
}
current = current.Next;
}
resultCurrent.Next = null;
return result;
} |
p*****2
发帖数: 21240 | 76
这题有O（n）的解是吧？
【在 i**********e 的大作中提到】
: 你的最后第二 large test case stack overflow 了，是递归造成的。
: n = 20000,
: height = [0, 1, 2, ... 19999]
|
i**********e
发帖数: 1145 | 77 是的，用ｓｔａｃｋ解，很隐含。
这道题你真正理解怎么用 ｓｔａｃｋ 做的话，可以解很多类似这种的题目，思路都
是类似：
maximal rectangle of 1's in a binary matrix
直方图盛水
largest distance j-i such that A[i] < A[j].
【在 p*****2 的大作中提到】
:
: 这题有O（n）的解是吧？
|
p*****2
发帖数: 21240 | 78
痛苦呀。手上还有好几道题没有做对。现在脑子全乱了。这两天做题错多，对少。
【在 i**********e 的大作中提到】
: 是的，用ｓｔａｃｋ解，很隐含。
: 这道题你真正理解怎么用 ｓｔａｃｋ 做的话，可以解很多类似这种的题目，思路都
: 是类似：
: maximal rectangle of 1's in a binary matrix
: 直方图盛水
: largest distance j-i such that A[i] < A[j].
|
H*******g
发帖数: 6997 | 79 List inputSet = new List();
inputSet .Add(1);
inputSet .Add(1);
inputSet .Add(2);
inputSet .Add(3);
inputSet .Add(3);
inputSet .Add(5);
var duplicates = inputSet
.GroupBy(i => i)
.Where(g => g.Count() > 1)
.Select(g => g.Key);
var result = inputSet.Except(duplicates).OrderBy(x=>x);
真受不了楼上的。。。这么简单的一个题目，弄的那么多行干嘛啊。。。这都是啥年代的代码了？ |
b******u
发帖数: 81 | 80 真搞不懂奥运会，100 米跑什么跑的，搞部汽车，谁能跑得过？
真受不了楼上的。。。这么简单的一个题目，弄的那么多行干嘛啊。。。这都是啥年代
的代码了？
【在 H*******g 的大作中提到】
: List inputSet = new List();
: inputSet .Add(1);
: inputSet .Add(1);
: inputSet .Add(2);
: inputSet .Add(3);
: inputSet .Add(3);
: inputSet .Add(5);
: var duplicates = inputSet
: .GroupBy(i => i)
: .Where(g => g.Count() > 1)
|
|
|
H*******g
发帖数: 6997 | 81 哈哈，也是，多写几行好忽悠老板。反正我就是一行搞定。截图上2行是为了好看而已。不如您也给个1
行代码的解决方法吧？
【在 b******u 的大作中提到】
: 真搞不懂奥运会，100 米跑什么跑的，搞部汽车，谁能跑得过？
:
: 真受不了楼上的。。。这么简单的一个题目，弄的那么多行干嘛啊。。。这都是啥年代
: 的代码了？
|
i**********e
发帖数: 1145 | 82 你每次以最低点来当 pivot，分成左右两块直方图。
当数组为递升的情况下，每次分的都是左边为空，而右边 n-1 个 bar。
这样的话可是 O(n^2)。
如果数组是递升／递减的情况之下，会导致不断递归 n-1 层深。如果ｎ很大的话就
stack overflow 了。
【在 p*****2 的大作中提到】
: 想了一个nlongn的，过了小数据，大数据runtime error.
: int max = 0;
: public int largestRectangleArea(int[] height)
: {
: max = 0;
: find(height, 0, height.length - 1);
: return max;
: }
: void find(int[] height, int x, int y)
: {
|
t**********h
发帖数: 2273 | 83 public static void main(String[] args){
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(3);
Node n5 = new Node(3);
Node n6 = new Node(4);
Node n7 = new Node(4);
Node n8 = new Node(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
Node result = remove(n1);
while(result != null){
System.out.print(result.value + " -> ");
result = result.next;
}
}
public static Node remove(Node head){
if(head == null) return null;
Stack s = new Stack();
s.push(head);
Node curr = head.next;
head = null;
Node p = null;
while(curr != null){
//
if(s.peek().value != curr.value){
if(head == null){
head = s.pop();
p = head;
}else{
p.next = s.pop();
p = p.next;
}
p.next = null;
s.push(curr);
}else{
while(curr != null && s.peek().value == curr.value){
curr = curr.next;
}
if(curr == null) return head;
s.pop();
s.push(curr);
}
curr = curr.next;
}
if(!s.isEmpty()){
if(head == null){
head = s.pop();
p = head;
}else{
p.next = s.pop();
p = p.next;
}
p.next = null;
}
return head;
}
class Node{
int value;
Node next;
Node(int v){
value = v;
}
} |
b******u
发帖数: 81 | 84 刚刚抄了一个
var items = from i in inputSet
group i by i into g
where g.Count() == 1
select g.Key;
已。不如您也给个1
【在 H*******g 的大作中提到】
: 哈哈，也是，多写几行好忽悠老板。反正我就是一行搞定。截图上2行是为了好看而已。不如您也给个1
: 行代码的解决方法吧？
|
H*******g
发帖数: 6997 | 85 赞一个，这代码利索。再加个AsParallel就真的无敌了。
【在 b******u 的大作中提到】
: 刚刚抄了一个
: var items = from i in inputSet
: group i by i into g
: where g.Count() == 1
: select g.Key;
:
: 已。不如您也给个1
|
b******u
发帖数: 81 | 86 Where where, 这不是让您给逼出来的么。AsParallel 我还真是头一回听说。
【在 H*******g 的大作中提到】
: 赞一个，这代码利索。再加个AsParallel就真的无敌了。
|
H*******g
发帖数: 6997 | 87 嗯，这东西威武无比。还能指定要多少个CPU CORE参与运算。
【在 b******u 的大作中提到】
: Where where, 这不是让您给逼出来的么。AsParallel 我还真是头一回听说。
|
l*****a
发帖数: 14598 | 88 上面好多帖子确实1米来长没人愿意看
但我想知道面试的时候让你写排序算法，你是不是直接调用任意一个sort() method完
事？
【在 H*******g 的大作中提到】
: List inputSet = new List();
: inputSet .Add(1);
: inputSet .Add(1);
: inputSet .Add(2);
: inputSet .Add(3);
: inputSet .Add(3);
: inputSet .Add(5);
: var duplicates = inputSet
: .GroupBy(i => i)
: .Where(g => g.Count() > 1)
|
H*******g
发帖数: 6997 | 89 那先要问清楚人家是想要SOLUTION还是想要BSO算法功力？反正我面试的时候，都是在尝试着取得主导
地位，也就是要让他们跟着我的节奏走。
譬如刚才说的什么算法吧。说实话我根本不会，但我肯定会忽悠。我会先说我不会算法，然后说我可以
提供一个SOLUTION，保证能用。然后BLAH BLAH,先扯个PREDICATE BUILDER，考官估计不知道，
然后我再扯个EXPRESSION TREE，我估计考官依然不知道。然后他们肯定要装逼问我是啥，然后我说
DELEGATE总知道了吧，考官终于开心了，说那你给讲讲。我说这个东西太复杂，我就送你一句话的解释
吧，然后BLAH BLAH，考官就被我搞定了。。。
【在 l*****a 的大作中提到】
: 上面好多帖子确实1米来长没人愿意看
: 但我想知道面试的时候让你写排序算法，你是不是直接调用任意一个sort() method完
: 事？
|
I****h
发帖数: 33 | 90 PNode trim_list(PNode begin)
{
Node head = {0};
PNode anchor = NULL;
PNode prev = NULL;
PNode curr = NULL;
int trim = 0;
if ((begin == NULL) || (begin->key != 0))
{
head.key = 0;
}
else
{
head.key = 1;
}
head.next = begin;
anchor = &head;
prev = &head;
curr = begin;
while (curr != NULL)
{
if (prev->key != curr->key)
{
if (trim == 0)
{
anchor = prev;
prev = curr;
curr = curr->next;
}
else
{
trim = 0;
anchor->next = prev->next;
free(prev);
prev = anchor->next;
curr = prev->next;
}
}
else
{
trim = 1;
prev->next = curr->next;
free(curr);
curr = prev->next;
}
}
if (trim != 0)
{
trim = 0;
anchor->next = NULL;
free(prev);
}
return head.next;
}
return
【在 r******3 的大作中提到】
: Given a sorted linked list, delete all duplicate numbers, leave only
: distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
: 1->2->5. Given 1->1->1->2->3, return 2->3.
: 要求扫一遍，O(1) space。
|
|
|
e****e
发帖数: 418 | 91 java:
public void remove(Node head) {
Node pre = null;
for ( Node node = head; node != null; node = node.getNext() ) {
boolean foundDuplidate = node.getNext() != null && node.getNum()
== node.getNext().getNum() ? true : false;
while ( node.getNext() != null && node.getNum() == node.getNext(
).getNum() ) {
node = node.getNext();
}
if ( foundDuplidate )
if ( pre == null )
pre = head = node.getNext();
else
pre.setNext( node.getNext() );
else
pre = node;
}
} |
a**y
发帖数: 56 | 92 为什么我的程序在自己的机器上给出所有答案，但在leetnode上面错了？
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL || head->next == NULL) return head;
else{
ListNode* c;
c = head->next;
int k =head->val;
while( c!=NULL && k == c->val )
c=c->next;
if (head->next != c)
{
head = c;
deleteDuplicates(head);
return head;
}
head->next = deleteDuplicates(head->next);
return head;
}
}
}; |
i**********e
发帖数: 1145 | 93 你代码有 bug。有可能重复连续的，所以不能保证当前head是之前的next。
把以下的代码：
deleteDuplicates(head);
return head;
改成：
return deleteDuplicates(head);
就好了。
【在 a**y 的大作中提到】
: 为什么我的程序在自己的机器上给出所有答案，但在leetnode上面错了？
: class Solution {
: public:
: ListNode *deleteDuplicates(ListNode *head) {
:
: if(head == NULL || head->next == NULL) return head;
: else{
: ListNode* c;
: c = head->next;
: int k =head->val;
|
S****h
发帖数: 115 | 94 这种单链表remove节点的问题，我看到有种解题习惯是在链表的头先生成一个dummy
node作为头，最后再去掉。可以省去很多判断和null指针的问题。（同理，tail也可
以）
e.g.
final ListNode dummy = new ListNode(0);
大家觉得这个习惯如何？
return
【在 r******3 的大作中提到】
: Given a sorted linked list, delete all duplicate numbers, leave only
: distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
: 1->2->5. Given 1->1->1->2->3, return 2->3.
: 要求扫一遍，O(1) space。
|
i**********e
发帖数: 1145 | 95 这个解法可以，省去很多判定情况。但是就额外多了个节点，而且用意不明显，所以最
好与面试官先沟通。
其实用递归也可以有同样的效果，代码简洁些。
【在 S****h 的大作中提到】
: 这种单链表remove节点的问题，我看到有种解题习惯是在链表的头先生成一个dummy
: node作为头，最后再去掉。可以省去很多判断和null指针的问题。（同理，tail也可
: 以）
: e.g.
: final ListNode dummy = new ListNode(0);
: 大家觉得这个习惯如何？
:
: return
|
e******x
发帖数: 184 | 96 为什么中间讨论出现了别的题。。
给出我的code，leetcode上大小数据都跑过了~
public ListNode deleteDuplicates(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
// Start typing your Java solution below
// DO NOT write main() function
if (head == null || head.next == null) { return head; }
ListNode last = head;
int v = head.val;
boolean dupl = false;
ListNode current = head.next;
while (current != null) {
if (current.val != v) {
if (! dupl && (last != head || last.val != v)) {
last = last.next;
} else if (dupl && last == head && last.val == v) {
last = current;
head = current;
dupl = false;
} else if (dupl) {
last.next = current;
dupl = false;
}
v = current.val;
} else {
dupl = true;
}
current = current.next;
}
if (dupl && last == head && last.val == v) {
return null;
} else if (dupl) {
last.next = null;
}
return head;
} |
k******I
发帖数: 238 | 97 List 是 O (1)吧
【在 s******o 的大作中提到】
: for std::slist, erase is O(N) operation
|
k******I
发帖数: 238 | 98 能说一下具体的思路么？搞了半天没想出来怎么做
【在 i**********e 的大作中提到】
: 是的，用ｓｔａｃｋ解，很隐含。
: 这道题你真正理解怎么用 ｓｔａｃｋ 做的话，可以解很多类似这种的题目，思路都
: 是类似：
: maximal rectangle of 1's in a binary matrix
: 直方图盛水
: largest distance j-i such that A[i] < A[j].
|
i**********e
发帖数: 1145 | |
l*********8
发帖数: 4642 | 100 不过他说的是slist
【在 k******I 的大作中提到】
: List 是 O (1)吧
|
|
|
l*********8
发帖数: 4642 | 101 我觉得以后不同的题目还是另外开一贴好。大家看起来方便。
【在 e******x 的大作中提到】
: 为什么中间讨论出现了别的题。。
: 给出我的code，leetcode上大小数据都跑过了~
: public ListNode deleteDuplicates(ListNode head) {
: // Start typing your Java solution below
: // DO NOT write main() function
: // Start typing your Java solution below
: // DO NOT write main() function
: if (head == null || head.next == null) { return head; }
: ListNode last = head;
: int v = head.val;
|
k******I
发帖数: 238 | 102 哦，那要用erase_after之类的，还得要一个previous保存一下前一个。我还是要不够
细心啊
【在 l*********8 的大作中提到】
: 不过他说的是slist
|
k*******2
发帖数: 84 | 103 Solution with Dummy node at the bottom. And how will recursion work here,
please?
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(head == NULL)
return head;
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *p1 = dummy;
ListNode *p2 = dummy->next;
while(p2!= NULL && p2->next != NULL)
{
if(p1->next->val == p2->next->val)
{
while(p2->next != NULL && p1->next->val == p2->next->val)
{
delete p2->next;
p2->next = p2->next->next;
}
p2 = p2->next;
p1->next = p1->next->next;
}else
{
p1 = p1->next;
p2 = p2->next;
}
}
return dummy->next;
}
};
【在 i**********e 的大作中提到】
: 这个解法可以，省去很多判定情况。但是就额外多了个节点，而且用意不明显，所以最
: 好与面试官先沟通。
: 其实用递归也可以有同样的效果，代码简洁些。
|
d*******y
发帖数: 27 | 104 one pass and constant space:
public static void rmDup(LinkedListNode head) {
LinkedListNode prev = head;
LinkedListNode run = head;
while (run != null) {
if (run.data == prev.data) {
run = run.next;
} else {
if (prev.next == run) {
prev = prev.next;
} else {
prev.next = run;
}
}
}
if (prev.next != run) {
prev.next = null;
}
} |
