-
Notifications
You must be signed in to change notification settings - Fork 59
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add Two Numbers #3
Comments
这道题可能太简单了没人过来,我来捧个场,其实链表这个很容易想到做一次单循环相加即可,原理就是小学一年级的加法算式,余1进1,所以时间和空间复杂度都和l1和l2的长度相关,O(max(l1,l2)) 。 var addTwoNumbers = function(l1, l2) {
var carry = 0,ret = new ListNode(0),l3 = ret;
while(l1!==null || l2!==null){
if(l1) {carry += l1.val;l1=l1.next;}
if(l2) {carry += l2.val;l2=l2.next;}
l3.next = new ListNode(carry%10)
l3 = l3.next
carry = carry>=10?1:0
}
if(carry) l3.next = new ListNode(1)
return ret.next
}; 不过我大JS怎么能少了array.reduce呢…… var addTwoNumbers = function(l1, l2) {
const toArray=l=>l.next?[l.val,...toArray(l.next)]:[l.val];
const arr=[toArray(l1),toArray(l2)],w=+(arr[0].length<arr[1].length),ret=new ListNode(0);
const r=arr[w].reduce((r,v,i)=>{
const v2=arr[+!w][i];
const x=v2?v2+v+r[1]:v+r[1],l=new ListNode(x%10);
r[0].next=l;
return [l,+(x>=10)];
},[ret,0]);
r[1]?r[0].next=new ListNode(1):0;
return ret.next;
}; |
哈哈,是我太傻,居然整了个数组实现,逃~~~已经来不及,先发这吧~ def addLinkedList(a,b):
addflag = 0 ;
len_a = len(a);
len_b = len(b);
if(len_a == len_b == 0):
return [];
ret = [];
min_len = len_a if len_a < len_b else len_b;
for i in range(min_len):
value = a[i] + b[i];
if addflag == 1:
value = value + addflag;
if value >= 10:
addflag = 1;
value -= 10;
else:
addflag = 0;
ret.append(value);
temp = a if len_a > len_b else b;
max_len = len_a if len_a > len_b else len_b;
for j in range(min_len, max_len):
if addflag == 1:
temp[j] = temp[j] + addflag;
if temp[j] >= 10:
addflag = 1;
temp[j] -= 10;
else:
addflag = 0;
break;
if addflag == 1:
temp.append(1);
ret = ret + temp[min_len:];
return ret;
print (addLinkedList([2,4,3],[5,6,4]))
print (addLinkedList([2,4,3,9,9],[5,6,9])) |
相对数组,链表使用起来要简便很多,在内存中,栈/数组的储存是连续的,如果需要对栈的内部元素做处理(比如删除或者插入),动作会比较大。而链表,可以轻松修改下待处理元素(或者其附近元素)的指针就可以解决问题。 链表实现:https://github.com/barretlee/daily-algorithms/blob/master/ref/linkedlist.js |
使用规范的链表,解法如下: import LinkedList, {Node} from './linkedlist';
const linkA = new LinkedList(2);
linkA.append(4);
linkA.append(3);
const linkB = new LinkedList(5);
linkB.append(6);
linkB.append(4);
const ret = resolve(linkA, linkB);
console.log(JSON.stringify(ret, null, 2));
function resolve(a, b) {
const alen = a.length;
const blen = b.length;
let count = Math.max(alen, blen);
let target = a.head, plus = b.head;
if (alen < blen) {
target = b.head;
plus = a.head;
}
while(count--) {
const sum = target.element + plus.element;
const bits = sum % 10;
const tens = ~~(sum / 10);
target.element = bits;
if (tens && !target.next) {
target.next = new Node(tens);
} else if (tens) {
target.next.element = target.next.element + tens;
}
target = target.next;
plus = plus.next;
}
return alen < blen ? b : a;
} |
@barretlee |
function resolve(a, b) {
const alen = a.length;
const blen = b.length;
let count = Math.max(alen, blen);
let target = a.head, plus = b.head;
if (alen < blen) {
target = b.head;
plus = a.head;
}
while(count--) {
- const sum = target.element + plus.element;
+ const sum = target.element + ( plus && plus.element || 0);
const bits = sum % 10;
const tens = ~~(sum / 10);
target.element = bits;
if (tens && !target.next) {
target.next = new Node(tens);
} else if (tens) {
target.next.element = target.next.element + tens;
}
target = target.next;
- plus = plus.next;
+ plus = plus && plus.next || null;
}
return alen < blen ? b : a;
} |
第一反应也是用数组实现,感觉解决方案还差好多,先发出来,在去看看答案。👽 function addTwoNumbers(linkA, linkB) {
let linkAArr = linkA.split('->');
let linkBArr = linkB.split('->');
let totalOfAB = [];
let otherNum = 0;
let baselength = linkAArr.length > linkBArr.length ? linkAArr.length : linkBArr.length;
for (let index = 0; index < baselength; index++) {
let temp = 0;
if (linkAArr[index] && linkBArr[index]) {
temp = parseInt(linkAArr[index]) + parseInt(linkBArr[index]) + otherNum;
} else if (linkAArr[index]) {
temp = parseInt(linkAArr[index]) + otherNum;
} else if (linkBArr[index]) {
temp = parseInt(linkBArr[index]) + otherNum;
}
if (temp < 10) {
totalOfAB.push(temp);
otherNum = 0;
} else {
totalOfAB.push(parseInt(temp.toString().slice(-1)));
otherNum = parseInt(temp.toString().slice(0, -1));
}
}
if (otherNum) {
totalOfAB.push(parseInt(otherNum, 10));
}
return totalOfAB.join('->');
} |
|
@winar-jin 不用删除,没关系,markdown 代码格式选择 diff,第一行第一个字符为 - red
- red
+ green
+ green |
题目要求返回新的链表。 |
from utils import LinkedList, Node
def resolve(alst, blst):
result = LinkedList()
shift, first = 0, 1
anode, bnode = alst.head, blst.head
while(anode or bnode or shift):
t_rnode = Node(0)
if first:
result.head = t_rnode
first = 0
else:
rnode.next = t_rnode
rnode = t_rnode
if anode:
rnode.val += anode.val
anode = anode.next
if bnode:
rnode.val += bnode.val
bnode = bnode.next
if shift:
rnode.val += shift
shift = 0
if rnode.val // 10:
shift = rnode.val // 10
rnode.val %= 10
else:
shift = 0
return result |
两个非空链表,分别代表两个非负整数,链表的每个节点储存着整数的一位,并且是倒序储存的,将这两个数字相加返回新的链表,如:
提示,这道题需要考虑溢出问题。
参考答案:https://github.com/barretlee/daily-algorithms/blob/master/answers/3.md
The text was updated successfully, but these errors were encountered: