LeetCode 刷题【66. 加一、67. 二进制求和】

66. 加一

自己做

解：逢十进位

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int add = 1;                //进位
        vector<int> res(digits.size() + 1); //防止多一位的情况：9 + 1 = 10

        for(int i = (int)digits.size() - 1; i >= 0; i--){
            int num = digits[i] + add;  //当前相加的结果
            add = num / 10;             //下一个数的进位
            res[i + 1] = num % 10;      //余位放进结果中
            digits[i] = num % 10;       //余位放进结果中
        }

        //如果相加后的结果比原先的数多一位，那么就补上进位，否则就返回正常的结果（比如8+1 = 9不会多一位）
        if(add != 0){
            res[0] = add;
            return res;
        }
        else
            return digits;
        
    }
};

67. 二进制求和

自己做

解：同十进制处理

class Solution {
public:
    string addBinary(string a, string b) {
        int add = 0;                    //进位
        int p = (int)a.size() - 1;      //a的尾指针
        int q = (int)b.size() - 1;      //b的尾指针
        bool a_or_b = true;             //判断a与b谁更长

        if(a.size() < b.size())
            a_or_b = false;

        while(p >= 0 && q >= 0){
            int num = a[p] - '0' + b[q] - '0' + add;            //本位相加结果
            add = num / 2;                          //进位

            if(a_or_b)                              //如果a更长就加到a上去
                a[p] = num % 2 + '0';
            else                                    //如果b更长就加到b上去
                b[q] = num % 2 + '0';

            p--;
            q--;
        }

        while(p >= 0){                       //加完以后还剩下a
            int num = a[p] - '0' + add;            //本位相加结果
            add = num / 2;                          //进位
            a[p--] = num % 2 + '0';          
        }

        while(q >= 0){                       //加完以后还剩下b
            int num = b[q] - '0' + add;            //本位相加结果
            add = num / 2;                          //进位
            b[q--] = num % 2 + '0';            
        }

        //如果相加后的结果比原先的数多一位，那么就补上进位，否则就返回不考虑进位的结果
        if(add != 0){
            if(a_or_b)
                return "1" + a;
            else
                return "1" + b;
        }
        else{
            if(a_or_b)
                return a;
            else
                return b;
        }
        
    
    }
};

解：逻辑运算符处理

class Solution {
public:
    string addBinary(string a, string b) {
        bool add = false;                //进位
        int p = (int)a.size() - 1;      //a的尾指针
        int q = (int)b.size() - 1;      //b的尾指针
        bool a_or_b = true;             //判断a与b谁更长（默认a更长）

        if(a.size() < b.size())         //如果b更长
            a_or_b = false;

        while(p >= 0 && q >= 0){
            if(a[p] == b[q]){                       //要么同为1，要么同为0，不管如何，a+b相加结果的余位都为0
                bool is_one = true;                 //判断是否同为1
                if(a[p] == '0')
                    is_one = false;

                if(a_or_b)                              //如果a更长就加到a上去
                    a[p] = add + '0';
                else                                    //如果b更长就加到b上去
                    b[q] = add + '0';

                if(is_one)                     //1 + 1有进位的情况
                    add = true;
                else                           //0 + 0无进位的情况
                    add = false;
            }
            else{                       //两者为1和0，不管如何，a+b相加结果的余位都为1
                //有进位的情况=> 1 + 0 + 1，进位1，余位0，无进位的情况=> 1 + 0 + 0，进位0，余位1
                if(a_or_b)                              //如果a更长就加到a上去
                    a[p] = '1' - add;
                else                                    //如果b更长就加到b上去
                    b[q] = '1' - add; 

                //进位保持不变
            }

            p--;
            q--;
        }

        while(p >= 0){                       //加完以后还剩下a
            if(!add)                         //如果没有进位就直接结束计算
                break;
            else{                            //如果有进位就要考虑计算
                if(a[p] == '1'){             //原位1与进位1相加
                    a[p] = '0';
                    //进位保持不变
                }
                else{                        //原位0与进位1相加
                    a[p] = '1';
                    add = false;
                }
            }

            p--;
        }

        while(q >= 0){                       //加完以后还剩下a
            if(!add)                         //如果没有进位就直接结束计算
                break;
            else{                            //如果有进位就要考虑计算
                if(b[q] == '1'){             //原位1与进位1相加
                    b[q] = '0';
                    //进位保持不变               
                }
                else{                        //原位0与进位1相加
                    b[q] = '1';
                    add = false;
                }
            }

            q--;
        }

        //如果相加后的结果比原先的数多一位，那么就补上进位，否则就返回不考虑进位的结果
        if(add){
            if(a_or_b)
                return "1" + a;
            else
                return "1" + b;
        }
        else{
            if(a_or_b)
                return a;
            else
                return b;
        }
        
    }
};