Plus one&&Add binary&&Add Two Numbers

本文是对leetcode中按位计算的题目进行的总结

Plus one

Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.
题目大意:给定一个非负整数(字符串形式)，求出加一后的结果

常规做法:按位计算

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 1;
        
        int index = digits.size() -1;
        
        for(; index >= 0; index--){
            int result = digits[index] + carry;
            
            digits[index] = result % 10;
            carry = result / 10;
        }
        
        if(carry == 1)
            digits.insert(digits.begin(), 1);
        return digits;
    }
};

改进方法：由于只有当这一位为9时才会发生进位

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int index = digits.size() -1;
        
        for(;index >= 0; index--){
            if(digits[index] == 9){
                digits[index] = 0;
            }else{
                digits[index] += 1;
                return digits;
            }
        }
        digits[0] = 1;
        digits.push_back(0);
        return digits;
    }
};

用c改写上述方法

/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize) {
    for(int index = digitsSize -1; index >= 0; index--){
        if(digits[index] == 9)
            digits[index] = 0;
        else{
            digits[index] += 1;
            *returnSize = digitsSize;
            return digits;
        }
    }
    
    *returnSize = digitsSize + 1;
    int *newDigits = (int*)malloc(sizeof(int) * (*returnSize));
    
    memcpy(newDigits + 1, digits, sizeof(int) * (digitsSize));
    newDigits[0] = 1;
    return newDigits;
}

Add binary

Given two binary strings, return their sum (also a binary string).
For example,
a = “11”
b = “1”
Return “100”.

参阅:http://fisherlei.blogspot.com/2013/01/leetcode-add-binary.html

题目大意:将数字表示成二进制的字符串，求出相加的结果
此种解法对所有进制的数字均有效，只需将对应的进位数修改就可以了

class Solution {
public:
    string addBinary(string a, string b) {
        int carry = 0;
        string s;
        for(int aIndex = a.size()-1, bIndex= b.size() -1; aIndex >= 0|| bIndex >=0; aIndex--, bIndex--){
            int numa = aIndex >= 0 ? a[aIndex] - '0' : 0;
            int numb = bIndex >= 0 ? b[bIndex] - '0' : 0;
            
            int num = (numa + numb +carry)%2;
            carry = (numa + numb + carry) /2;
            
            s = (char)(num + '0')+s;
        }
        //此处容易被忽略
        if(carry)
            s= '1' +s;
        return s;
    }
};

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. * struct ListNode { *     int val; *     struct ListNode *next; * }; */
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
            int flag = 0;
            int sum = 0;
            
            struct ListNode *head = NULL;
            struct ListNode *rear = NULL;
            while(l1!=NULL && l2!= NULL){
                sum = (l1->val) + (l2->val) + flag;
                flag = sum / 10;
                struct ListNode *temp;
                temp = (struct ListNode*)malloc(sizeof(struct ListNode));
                temp->val = sum %10;
                temp->next = NULL;
                
                if (head == NULL)
                    head = temp;
                else
                    rear->next = temp;
                rear = temp;
                
                l1 = l1->next;
                l2 = l2->next;
            }
            
            while (l1 != NULL){
                int num = l1->val+flag;
                flag = num/10;
                l1-> val = num % 10;
                if (head == NULL)
                    head = l1;
                else
                    rear->next = l1;
                rear = l1;
                l1= l1->next;
            }
            
            while(l2 != NULL){
                int num = l2->val+flag;
                flag = num/10;
                l2->val = num%10;
                if (head == NULL)
                    head = l2;
                else
                    rear->next = l2;
                rear = l2;
                l2 = l2->next;
            }
            if(flag > 0){
                struct ListNode *last; 
                last = (struct ListNode *)malloc(sizeof(struct ListNode));
                last->val = flag;
                last->next = NULL;
                
                rear->next = last;
                rear = last;
            }
            return head;
}

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

题目大意:两个字符串代表两个数字，输出两个字符串相乘的结果
有了上述的做题过程，这都题目就是一个按位计算的过程，计算过程类似正常的计算乘法的过程，需要注意的是：
(1)我们计算乘法的过程是从低位开始计算的，为了方便，我们要把字符串反转
(2)得到的结果也要反转哟
(3)m位的数字乘以n位的数字的结果最大为m+n位：
99999 < 1000100 = 100000，最多为3+2 = 5位数。

正常的计算乘法的过程:

      1 2 3
x     2 3 4
___________
      4 9 2
    3 6 9
  2 4 6
___________
  2 8 7 8 2

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1.size() == 0 || num2.size() ==0)
            return "";
            
        string ret(num1.size() + num2.size(), '0');
        
        //反转两个数组
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        
        //按照做乘法题目的方法来求，首先去除乘数的最低位，再次低位，直到最高位
        for(int i = 0; i < num2.size(); i++){
            int val = num2[i] - '0';
            int carry = 0;
            //将被乘数的每一项与上面的数字相乘
            for(int j = 0; j < num1.size(); j++){
                int temp = (num1[j] - '0')*val + (ret[i + j] - '0') + carry;
                
                ret[i + j] = temp % 10 + '0';
                carry = temp /10;
            }
            //一轮结束后判断是否最高位有进位
            if(carry != 0) ret[num1.size() + i] = carry + '0';
        }
        
        reverse(ret.begin(), ret.end());
        int zerobit = 0;
        while(zerobit < ret.size() -1 && ret[zerobit] == '0')
            zerobit++;
        ret.erase(0, zerobit);
        
        return ret;
    }
};

另一种实现的方法

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1.size() == 0 || num2.size() ==0)
            return "";
            
        string ret(num1.size() + num2.size(), '0');
        
        //反转两个数组
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        
        //按照乘法来求
        for(int i = 0; i < num2.size(); i++){
            for(int j = 0; j < num1.size(); j++){
                int temp = (num1[j] - '0')*(num2[i] - '0');
                
                ret[i + j +1] = （ret[i + j +1] - '0'） + (temp + ret[i + j] - '0')/10 + '0';
                ret[i + j] = (temp + ret[i + j] - '0')%10 + '0';
            }
        }
        
        reverse(ret.begin(), ret.end());
        //可以肯定的是最高位一定至少有一个0
        if(ret.find_first_not_of('0')==string::npos)    
            return "0";    
        else    
            return ret.substr(ret.find_first_not_of('0'));
    }
};

附上一讲解find_first_not_of的讲解
http://www.vimer.cn/2011/02/stl%E5%8F%AF%E8%83%BD%E7%9A%84%E8%AF%AF%E7%94%A8-find_first_of%E5%92%8Cerase.html