链表两数相加\字符串相加问题

旧城等待， 2022-11-12 02:36 120阅读 0赞

> 这两天刷面经上的算法题，有两道类似的题，都是关于手动实现加法，总结了一下做法和技巧。

## **leetcode415**：字符串相加 ##

两个字符串，逢10进1，相加求结果  
不能直接使用类型转换，题意就是要手动实现一下加法

*  由于js的字符串的内部装箱操作，字符串可以进行遍历查询长度等操作，首先把两个字符串对齐，缺位补0即可
 *  接下来就是计算部分，设置个进位数，逢10进1

/** * @param {string} num1 * @param {string} num2 * @return {string} */
    var addStrings = function(num1, num2) { 
        //缺位补0对齐
        while(num1.length<num2.length){ 
            num1 = 0+num1;
        }
        while(num2.length<num1.length){ 
            num2 =0+num2;
        }
        let res = "";
        let add = 0;
        //手动加法，逢10+1
        for(let i=num1.length-1;i>=0;i--){ 
            let sum = +num1[i]+ +num2[i] +add;
            res=(sum)%10 + res;
            add = sum>=10?1:0;
        }
        return add==1?1+res:res;
    };

--------------------

## **Leetcode 2** ：两数之和 ##

两个链表，逢10进位，可以理解为逆序的number加法

*  由于是链表结构，不必强行对齐，新建一条链表用来计算最终答案
 *  用了这么久的链表，才学会使用 ***哑节点*** ，用哑节点返回答案十分方便

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
    /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */
    var addTwoNumbers = function(l1, l2) { 
        let add = 0;
        let head = new ListNode('head');
        let res = head;
        while(l1||l2||add){ 
            let val1=l1!=null?l1.val:0;
            let val2=l2!=null?l2.val:0;
            let sum = val1+val2+add;
            add = sum>=10?1:0;
            let tempVal= sum%10;
            head.next = new ListNode(tempVal);
            head = head.next;
            if(l1) l1=l1.next;
            if(l2) l2=l2.next;
        }
        return res.next;
    };

所以有关此类加法题，都是一样的操作，灵活使用add进行+1操作就可以了。