最新消息:深度思考

各种形式的两数相加

算法 liuxuecheng 2815浏览 0评论

这篇文章总结一下LeetCode上各种形式的两数相加,有两个链表相加、字符串模拟二进制数相加、不使用运算符号的相加等。

1.两个单链表相加,返回一个单链表

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

给定链表结构如下:

public class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
    this.val = val;
    }
}

链表中头结点存的值相当于整数的末位,因此有个好处就是从头结点遍历相加就行,需要考虑的是链表的长度不一致,也有可能其中一个链表为空。对于十进制的数相加,加和sum/10就是要进位的数,sum%10就是当前位。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //定义一个节点用来充当链表的头结点
        ListNode head = new ListNode(0);
        //链表的当前节点
        ListNode current = head;
        //进位
        int carry = 0;
        //当l1 l2的节点都不为空的时候进行循环
        while(l1 !=null || l2!=null){
            int x = l1!=null ? l1.val:0;
            int y = l2!=null ? l2.val:0;
            //加和进位操作
            int sum = x+y+carry;
            carry = sum/10;
            current.next = new ListNode(sum%10);

            //新生成的链表及l1,l2的指针移动
            current = current.next;
            if(l1!=null){
                l1= l1.next;
            }
            if(l2!=null){
                l2 = l2.next;
            }
        }

        //不要忘记,加和完成可能多出位数
        if(carry>0){
            current.next = new ListNode(carry);
        }

        return head.next;
    }
}

2.单链表高位数在链表头部

与上面两个链表求和的差异在于给定的链表高位数在链表头部,这样就没法同上面一样直接顺次遍历链表求和,因为两个数求和不能从高位数开始相加。题目如下:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
且题目要求不允许对输入的两个链表做翻转操作。

容易想到的解法就是将链表元素放入栈,元素出栈的时候相当于链表从尾到头遍历。

  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        while(l1!= null){
            s1.push(l1.val);
            l1 = l1.next;
        }

        while (l2!=null){
            s2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;
        ListNode current = null;
        while(!s1.isEmpty() || !s2.isEmpty()){
            int x = s1.isEmpty() ? 0:s1.pop();
            int y = s2.isEmpty() ? 0:s2.pop();
            int sum = x+y+carry;
            carry = sum/10;
            ListNode node = new ListNode(sum%10);
            node.next = current;
            current = node;
        }

        if(carry > 0){
            ListNode node = new ListNode(carry);
            node.next = current;
            current = node;
        }

        return current;
    }

3.二进制数求和

给定两个字符串,只包含0和1,两个字符串模拟二进制求和。
Input: a = “1010”, b = “1011”
Output: “10101”

和两个单链表求和类似,只不过是从每个字符串的最后一位往前遍历。

public String addBinary(String s1,String s2){
        //容错处理
        if(s1 == null){
            return s2;
        }else if(s2 == null){
            return s1;
        }

        int x = s1.length() -1 ;
        int y = s2.length() -1 ;
        int carry = 0;
        String result = "";

        //从后往前移动
        while (x>=0 || y>=0){
            //将字符转为整数
            int p = x>=0 ? s1.charAt(x) -'0':0;
            int q = y>=0 ? s2.charAt(y) -'0':0;
            int sum = p+q+carry;
            int current = sum%2;
            carry = sum/2;
            result = current+result;
            x --;
            y --;
        }
        //有进位时多出一位
        if(carry >0){
            result = carry + result;
        }
        return result;
    }

转载请注明:大数据随笔 » 各种形式的两数相加

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址