f*****k
发帖数: 65 | 1 A. 两个single linked list，每一个节点里面一个0-9的数字，输入就相当于两个大数
了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
当时的要求是：1. 不用递归。2.然后要求算法在最好的情况下，只遍历两个list一次
。最差的情况下两遍。
当时让我首先说说什么情况2遍，什么情况1遍，然后开始写。这个题目看上去不难，但
是写起来挺考验基本功的。大家准备面试练习的时候可以写写。
B. Count Inversions
http://www.geeksforgeeks.org/counting-inversions/
刚开始想到这个解法，但是有个坎没绕过去，觉得有些情况下处理不了，后来经过沟通
发现其实可以。 |
g*********e
发帖数: 14401 | |
s***5
发帖数: 2136 | |
t****d
发帖数: 423 | 4 如果逆序输入一次就够了，顺序的话要看后面的进位，利用栈的话两次应该可以
★ 发自iPhone App: ChineseWeb 7.8
【在 s***5 的大作中提到】
: 遍历一遍就可以吧？
|
f*****k
发帖数: 65 | 5 不用递归是题目要求，面试官直接就说了，不要用递归。我个人觉得这道题就是考基本
的单链表操作，比如连输入都已经假设好了，长度相等，输入也都肯定合法，不需要我
考虑。
输入是正序列。
=====我的解法，如果你想自己考虑一下，可以先跳过=====
我当时的解法是考虑每两位加起来的和，这样就可以确定是否需要再回来一次。
比如如果两个节点的和加起来小于9或者大于等于10，那么这一位之前的都可以计算出
来了，因为就算后面有进位，也不会影响到前面。然后特殊情况就是两个节点的和是9
的情况，这样就要记住当前的位置，然后开始往下找，找到下一个和不为9的节点对，
然后就可以知道从一开始的9到发现的最后一个是不是需要进位了。（觉得不容易解释
清楚，哈哈）
所以最好情况是，所有配对节点没有加起来值为9，这样一遍就可以。如果有出现配对
加起来值为9，只需要把这些节点访问两遍。 |
B**L
发帖数: 33 | |
s***5
发帖数: 2136 | 7 的确，顺序可能要两次。
【在 t****d 的大作中提到】
: 如果逆序输入一次就够了，顺序的话要看后面的进位，利用栈的话两次应该可以
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
z*f
发帖数: 293 | 8 "然后特殊情况就是两个节点的和是9
怎么倒着找下一个和不为9的
9 |
e***a
发帖数: 1661 | 9 did you work out these two questions at onsite? |
b******7
发帖数: 92 | 10 ListNode * add(ListNode * a, ListNode * b)
{
if(a == NULL || b == NULL) return NULL;
ListNode * head = NULL;
ListNode * pre = NULL;
ListNode * preLess9 = NULL;
for(; a != NULL; a = a->next, b = b->next)
{
ListNode * temp = new ListNode(a->val, b->val);
if(pre != NULL)
pre->next = temp;
else
head = temp;
if(temp->val < 9)
preLess9 = temp;
else if(temp->val >= 10)
{
temp->val -= 10;
ListNode * start = NULL;
//[start, temp) will be set to 0
if(preLess9 == NULL)
{
ListNode * newHead = new ListNode(
1);
newHead ->next = head;
head = newHead;
start = head->next;
}
else
start = preLess9->next;
for(; start != temp; start = start->next)
start->val = 0;
preLess9 = temp->val < 9 : temp : pre;
}
pre = temp;
}
assert(pre != NULL);
pre->next = NULL;
return head;
} |
|
|
s*****e
发帖数: 164 | 11 为神马是两个题？
加的过程中，用一个变量指向连续的9的前一个节点。随时更新这个变量 |
p*****2
发帖数: 21240 | |
M*******u
发帖数: 51 | 13
第一个难道不能 先判断是不是一次都OK，如果对应位置相加都小于9的话，直接相加就
oK，如果不是，那就reverse list，然后从前往后相加就ok了
第二个就是 MergeSort 修改一下
【在 f*****k 的大作中提到】
: A. 两个single linked list，每一个节点里面一个0-9的数字，输入就相当于两个大数
: 了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
: 当时的要求是：1. 不用递归。2.然后要求算法在最好的情况下，只遍历两个list一次
: 。最差的情况下两遍。
: 当时让我首先说说什么情况2遍，什么情况1遍，然后开始写。这个题目看上去不难，但
: 是写起来挺考验基本功的。大家准备面试练习的时候可以写写。
: B. Count Inversions
: http://www.geeksforgeeks.org/counting-inversions/
: 刚开始想到这个解法，但是有个坎没绕过去，觉得有些情况下处理不了，后来经过沟通
: 发现其实可以。
|
e*******i
发帖数: 56 | 14 User edmca posted code for list addition is wrong. Tested with A[]={1,2,3,4,
5,6}, B[]={9,9,8,7,8,5}. Got result 1 0 1 1 1 3 1. Any one can post a
correct solution? |
f*********m
发帖数: 726 | 15 对呀，为什么不能reverse一下呢？
【在 M*******u 的大作中提到】
:
: 第一个难道不能 先判断是不是一次都OK，如果对应位置相加都小于9的话，直接相加就
: oK，如果不是，那就reverse list，然后从前往后相加就ok了
: 第二个就是 MergeSort 修改一下
|
x*****0
发帖数: 452 | |
h****p
发帖数: 87 | |
c******t
发帖数: 1500 | 18 第二题是CLRS上的一个练习题，呵呵
多谢楼主分享经历！ |
M****9
发帖数: 912 | 19 I don't understand the first question.
what's the meaning of "输入就相当于两个大数了。然后返回这两个数的和（一个新
list）。" ....???
【在 f*****k 的大作中提到】
: A. 两个single linked list，每一个节点里面一个0-9的数字，输入就相当于两个大数
: 了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
: 当时的要求是：1. 不用递归。2.然后要求算法在最好的情况下，只遍历两个list一次
: 。最差的情况下两遍。
: 当时让我首先说说什么情况2遍，什么情况1遍，然后开始写。这个题目看上去不难，但
: 是写起来挺考验基本功的。大家准备面试练习的时候可以写写。
: B. Count Inversions
: http://www.geeksforgeeks.org/counting-inversions/
: 刚开始想到这个解法，但是有个坎没绕过去，觉得有些情况下处理不了，后来经过沟通
: 发现其实可以。
|
d******l
发帖数: 98 | 20 第一题,我用java作： 只需要遍历一次就够了 O（n）time
首先，定义一个Node head=null, runner=null; int value=carry (进位1 or 0)
接下来用while循环遍历
while(N1!=null && N2!=null){
定义一个新的临时 Node. Node temp=new Node(); //先做个位数节点，第二次遍历
是 就是 十位数节点...
再为遍历作下工作：Node next1=N1.next; Node next2=N2.next;
如果N1 N2 不为null， 把value+=N1.data; value+=N2.data;
if(value>=10) carry=1; else carry=0;
temp.data=value%10; //这是取个位数
接下来按数序插入高位的Node （十 百 千 万位 递增顺序）
if(head==null){ head=temp; runner=head; }
else{ runner.next=temp； runner=temp;}
N1=next1; N2=next2;
value=carry;
}
if(value>0){ // 防止高位数 最后 需要补一位 如： 489+539=1028
Node more=new Node(value);
runner.next=more;
}
至此 结束 |
|
|
a*****a
发帖数: 46 | 21 我觉得一遍就可以啊。
保存上一个小于9的节点last，每次相加，以和的个位数做新节点，如果有进位就增加
last.value，如果新节点小于9就把last移到新节点。
可以这样做的原因是，每一个节点只存一个数字，那么任何一位如果需要进位，个位数
最多为8，无论后面的数是什么都不会再进位。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), last = dummy, cur = dummy;
while (l1 != null && l2 != null) {
int sum = l1.value + l2.value;
cur.next = new ListNode(sum % 10);
cur = cur.next;
l1 = l1.next;
l2 = l2.next;
if (sum / 10 > 0) { // has carry
last.value++;
}
if (cur.value < 9) {
last = cur;
}
}
return (dummy.value > 0) ? dummy : dummy.next;
}
l1: 1->2->3->4->5->6->|
l2: 9->9->8->7->5->5->|
1->1->2->2->2->1->1->|
欢迎指正~~
（嗯，如果是二进制数就不能这么做了。。。）
9
【在 f*****k 的大作中提到】
: 不用递归是题目要求，面试官直接就说了，不要用递归。我个人觉得这道题就是考基本
: 的单链表操作，比如连输入都已经假设好了，长度相等，输入也都肯定合法，不需要我
: 考虑。
: 输入是正序列。
: =====我的解法，如果你想自己考虑一下，可以先跳过=====
: 我当时的解法是考虑每两位加起来的和，这样就可以确定是否需要再回来一次。
: 比如如果两个节点的和加起来小于9或者大于等于10，那么这一位之前的都可以计算出
: 来了，因为就算后面有进位，也不会影响到前面。然后特殊情况就是两个节点的和是9
: 的情况，这样就要记住当前的位置，然后开始往下找，找到下一个和不为9的节点对，
: 然后就可以知道从一开始的9到发现的最后一个是不是需要进位了。（觉得不容易解释
|
c*******d
发帖数: 27 | 22 You code cannot handle the following case. I think you need to use a stack
to store element pointers from "last" to "cur" inside the while loop.
l1 is 4->3->4
l2 is 5->6->6
your new list will be:
1->9->9->0
【在 a*****a 的大作中提到】
: 我觉得一遍就可以啊。
: 保存上一个小于9的节点last，每次相加，以和的个位数做新节点，如果有进位就增加
: last.value，如果新节点小于9就把last移到新节点。
: 可以这样做的原因是，每一个节点只存一个数字，那么任何一位如果需要进位，个位数
: 最多为8，无论后面的数是什么都不会再进位。
: public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
: ListNode dummy = new ListNode(0), last = dummy, cur = dummy;
: while (l1 != null && l2 != null) {
: int sum = l1.value + l2.value;
: cur.next = new ListNode(sum % 10);
|
f*******r
发帖数: 180 | 23 只需要把从last到cur之前value是9的置0就可以了把， 最坏情况下需要把整个list重
新走一边。
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), last = dummy, cur = dummy;
while (l1 != null && l2 != null) {
int sum = l1.value + l2.value;
cur.next = new ListNode(sum % 10);
cur = cur.next;
l1 = l1.next;
l2 = l2.next;
if (sum / 10 > 0) { // has carry
last.value++;
last = last.next;
while (last != null && last.value == 9) {
last.value = 0;
last = last.next;
}
}
if (cur.value < 9) {
last = cur;
}
}
return (dummy.value > 0) ? dummy : dummy.next;
} |
q****o
发帖数: 253 | 24 最后一句“如果有出现配对加起来值为9，只需要把这些节点访问两遍。”
这些节点应该不用都访问两遍吧，只有这一串9后面跟着一个进位的才需要访问第二遍
，否则就该跳过去了吧
9
【在 f*****k 的大作中提到】
: 不用递归是题目要求，面试官直接就说了，不要用递归。我个人觉得这道题就是考基本
: 的单链表操作，比如连输入都已经假设好了，长度相等，输入也都肯定合法，不需要我
: 考虑。
: 输入是正序列。
: =====我的解法，如果你想自己考虑一下，可以先跳过=====
: 我当时的解法是考虑每两位加起来的和，这样就可以确定是否需要再回来一次。
: 比如如果两个节点的和加起来小于9或者大于等于10，那么这一位之前的都可以计算出
: 来了，因为就算后面有进位，也不会影响到前面。然后特殊情况就是两个节点的和是9
: 的情况，这样就要记住当前的位置，然后开始往下找，找到下一个和不为9的节点对，
: 然后就可以知道从一开始的9到发现的最后一个是不是需要进位了。（觉得不容易解释
|
