链表或字符串模拟加法、加一及乘法

链表或字符串模拟加法、加一及乘法2014-12-10 博客园 z陵链表模拟加法/字符串模拟二进制加法/数组模拟加一操作/打印1到最大的n位数/字符串模拟乘法

============================================

Add Two Numbers

两个链表代表两个数字，每个结点的值都是一位数字，单链表逆序存放这两个数字，

构造出一个新的链表，代表这两个链表的和。

链表的尾插法，头结点dummy结点的运用，统一对prev指针的操作，

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode（int x） : val（x）, next（NULL） {} * }; */class Solution{public:ListNode *addTwoNumbers（ListNode *l1, ListNode *l2）{/*头结点,dummy主要是为了保持prev的统一操作*/ListNode dummy（-1）;int carry = 0;ListNode *prev = &dummy;ListNode *p1 = l1, *p2 = l2;while（p1 ！= NULL || p2 ！= NULL）{const int aCur = （p1 == NULL） ？ 0 : p1->val;const int bCur = （p2 == NULL） ？ 0 : p2->val;const int value = （aCur + bCur + carry） % 10;carry = （aCur + bCur + carry） / 10;/*尾插法*/prev->next = new ListNode（value）;p1 = （p1 == NULL） ？ NULL : p1->next;p2 = （p2 == NULL） ？ NULL : p2->next;prev = prev->next;}if（carry > 0）{prev->next = new ListNode（carry）;}return dummy.next;}};

Add Binary

两个字符串模拟二进制的加法，二进制的字符串都是正序存放的，区别于链表模拟加法的题目，

插入的时候，有头插法和尾插法。这里显然要用到头插法。

class Solution{public:string addBinary（string a, string b）{string result;const int n = a.size（） > b.size（） ？ a.size（） : b.size（）;/*反转过来，然后从左到右计算*/reverse（a.begin（）, a.end（））;reverse（b.begin（）, b.end（））;int carry = 0;for（int i = 0; i < n; ++i）{/*有一方，超过了长度就把这一方的设置为0*/const int aCur = i < a.size（） ？ a[i] - "0" : 0;const int bCur = i < b.size（） ？ b[i] - "0" : 0;/*余数*/const int val = （aCur + bCur + carry） % 2;/*进位*/carry = （aCur + bCur + carry） / 2;/*头插法*/result.insert（result.begin（）, val + "0"）;}if（carry == 1）{result.insert（result.begin（）, "1"）;}return result;}};