我在做一道leetcode题。两个数字相加
其中一个testCases没有通过,我不知道为什么我的程序会漏掉最后一个值。下面是代码。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//have to use bit addition here
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
int b1=0, b2=0, resBit = 0, carryBit=0;
ListNode res = new ListNode(-1);
ListNode dummy = res;
while(l1!=null && l2!=null){
resBit = l1.val+l2.val+carryBit;
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
l1=l1.next;
l2=l2.next;
dummy=dummy.next;
}
//add any remaining numbers to our result
if(l1!=null){
System.out.println(l1.val);
if(carryBit!=0){
resBit = l1.val+carryBit;
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
}
else{
dummy.next = new ListNode(l1.val);
}
l1=l1.next;
System.out.println(l1.val);
dummy=dummy.next;
}
if(l2!=null){
if(carryBit!=0){
resBit = l2.val+carryBit;
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
}
else{
dummy.next = new ListNode(l2.val);
}
l2=l2.next;
dummy=dummy.next;
}
if(carryBit!=0){
dummy.next = new ListNode(carryBit);
}
//remove the -1 used to create the LL initially
res = res.next;
return res;
}
}
以下是失败的测试案例的细节:
Wrong AnswerRuntime: 0 msYour input[9,1,6][0]
stdout16
产量[9,1]预期[9,1,6]
如你所见,我的代码漏掉了6。然而,在剩余的L1元素解析循环中,6被打印出来了。为什么会漏掉呢?
唯一可能漏掉的方法是循环没有被运行,这意味着程序将6作为空值,因此跳过了一个值。不知道为什么会出现这种情况。这条思路对吗?
任何新的信息,或者改进都非常感谢。
作为一点无耻的促销活动,请查看 我的办法. 但我可以指出为什么它不工作的原因,和一些其他的事情,是良好的做法首先,什么是 b1
和 b2
为?我是不是遗漏了什么,因为我在你的代码中没有看到它。
在这里
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
你把携带位设置为 1
. 但是,你必须将它设置为 sum / 10
万一总和达到 20
. 在实际问题中,并没有任何测试用例会给你带来问题,然而在数字较大的情况下,这会导致错误。
更大的原因是这部分。
if(l1!=null){
和...
if(l2!=null){
你只是在检查它是否不为空。然而,如果两个列表的大小相差2个或更多,那么 l1
或 l2
终止时仍然是非空的。所以,你必须改变 if
到 while
循环。
当我应用这些变化时,它工作了。这就是结果。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//have to use bit addition here
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
int resBit = 0, carryBit=0;
ListNode res = new ListNode(-1);
ListNode dummy = res;
while(l1!=null && l2!=null){
resBit = l1.val+l2.val+carryBit;
if(resBit >9){
carryBit=resBit / 10;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
l1=l1.next;
l2=l2.next;
dummy=dummy.next;
}
//add any remaining numbers to our result
while(l1!=null){
if(carryBit!=0){
resBit = l1.val+carryBit;
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
}
else{
dummy.next = new ListNode(l1.val);
}
l1=l1.next;
dummy=dummy.next;
}
while(l2!=null){
if(carryBit!=0){
resBit = l2.val+carryBit;
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
}
else{
dummy.next = new ListNode(l2.val);
}
l2=l2.next;
dummy=dummy.next;
}
if(carryBit!=0){
dummy.next = new ListNode(carryBit);
}
//remove the -1 used to create the LL initially
res = res.next;
return res;
}
}
有一个方法可以跳过我的错误方法,解决了这个问题。但是,它仍然没有解决原来的问题。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//have to use bit addition here
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
int b1=0, b2=0, resBit = 0, carryBit=0;
ListNode res = new ListNode(-1);
ListNode dummy = res;
while(l1!=null || l2!=null){
b1 = (l1 != null) ? l1.val : 0;
b2 = (l2 != null) ? l2.val : 0;
resBit = b1+b2+carryBit;
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
if(l1!=null){
l1=l1.next;
}
if(l2!=null){
l2=l2.next;
}
dummy=dummy.next;
}
//add carry to our result if carry is not 0
if(carryBit!=0){
dummy.next = new ListNode(carryBit);
}
//remove the -1 used to create the LL initially
res = res.next;
return res;
}
正如我所说,这个解决方案成功了测试用例。但是,我还是不知道为什么之前的代码不能用。如果你看到了原因,请回复。
/在结果中添加任何剩余的数字
if(l1!=null){
System.out.println(l1.val);
if(carryBit!=0){
resBit = l1.val+carryBit;
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
}
else{
dummy.next = new ListNode(l1.val);
}
l1=l1.next;
System.out.println(l1.val);
dummy=dummy.next;
}
if(l2!=null){
if(carryBit!=0){
resBit = l2.val+carryBit;
if(resBit >9){
carryBit=1;
resBit=resBit%10;
}
else{
carryBit=0;
}
dummy.next = new ListNode(resBit);
}
else{
dummy.next = new ListNode(l2.val);
}
l2=l2.next;
dummy=dummy.next;
}
if(carryBit!=0){
dummy.next = new ListNode(carryBit);
}
使用while循环而不是if,总之。
正如你所看到的,上面的代码只运行一次,如果任何一个 LinkedList
变成了空。而由于你的测试用例是。
L1: [9,1,6]
L2: [0]
你可以注意到,在第一次加法后,
那么你只是对L1指针做了一次加法,而不是直到L1变成{null}。
你在注释中给出的解决方案中使用while循环解决了这个问题。