大数的数学运算

返回首页

返回算法分类分析

第一题 Add Binary

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"

b = "1"

Return "100".

解法

注意这里范例式的处理，没有去根据长短进行分类讨论，而是有效地用一个循环处理了所有情况。对字符串的处理也值得学习。

class Solution(object):

def addBinary(self, a, b):

    """

    :type a: str

    :type b: str

    :rtype: str

    """

    pa, pb, c, res = len(a) - 1, len(b) - 1, 0, ''

    while pa >= 0 or pb >= 0 or c > 0:

        c += 1 if pa >= 0 and a[pa] == '1' else 0

        c += 1 if pb >= 0 and b[pb] == '1' else 0

        res = str(c % 2) + res

        pa, pb, c = pa - 1, pb - 1, c / 2

    return res

第二题 Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

解法

解法和上面一题一样，只是这次在链表上实现了。

# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None



class Solution(object):

def addTwoNumbers(self, l1, l2):

    """

    :type l1: ListNode

    :type l2: ListNode

    :rtype: ListNode

    """

    c = 0

    head = ListNode(0)

    l = head

    while not l1 == None or not l2 == None or not c == 0:

        c += l1.val if not l1 == None else 0

        c += l2.val if not l2 == None else 0

        l.next = ListNode(c%10)

        l = l.next

        l1 = l1.next if not l1 == None else l1

        l2 = l2.next if not l2 == None else l2

        c = c / 10

    return head.next