leetcode 5078. 负二进制数相加(Adding Two Negabinary Numbers)
发布时间:2020-12-14 04:45:10 所属栏目:大数据 来源:网络整理
导读:目录 题目描述: 示例: 解法: 题目描述: 给出基数为 -2 的两个数 arr1 和 arr2,返回两数相加的结果。 数字以 数组形式 给出:数组由若干 0 和 1 组成,按最高有效位到最低有效位的顺序排列。例如, arr = [1,1,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -
目录
题目描述:给出基数为 -2 的两个数 arr1 和 arr2,返回两数相加的结果。 数字以 数组形式 给出:数组由若干 0 和 1 组成,按最高有效位到最低有效位的顺序排列。例如, 返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为:不含前导零、由若干 0 和 1 组成的数组。 示例:输入:arr1 = [1,1],arr2 = [1,1] 输出:[1,0] 解释:arr1 表示 11,arr2 表示 5,输出表示 16 。 提示:
解法:class Solution { public: vector<int> addNegabinary(vector<int>& arr1,vector<int>& arr2) { // 10101 // 101 // 1101110 int sz1 = arr1.size(); int sz2 = arr2.size(); int max_sz = max(sz1,sz2); vector<int> res(max_sz+4,0); int i = sz1-1,j = sz2-1,idx = max_sz+3; int carry = 0; while(i >= 0 && j >= 0){ int digit = carry + arr1[i] + arr2[j]; if(digit >= 2){ carry = -1; digit -= 2; }else if(digit == -1){ digit = 1; carry = 1; }else{ carry = 0; } res[idx] = digit; idx--; i--; j--; } while(i >= 0){ int digit = carry + arr1[i]; if(digit >= 2){ carry = -1; digit -= 2; }else if(digit == -1){ digit = 1; carry = 1; }else{ carry = 0; } res[idx] = digit; idx--; i--; } while(j >= 0){ int digit = carry + arr2[j]; if(digit >= 2){ carry = -1; digit -= 2; }else if(digit == -1){ digit = 1; carry = 1; }else{ carry = 0; } res[idx] = digit; idx--; j--; } assert(carry == 0 || carry == 1 || carry == -1); if(carry == -1){ res[idx--] = 1; res[idx--] = 1; }else if(carry == 1){ res[idx--] = 1; } while(!res.empty() && res.front() == 0){ res.erase(res.begin()); } if(res.empty()){ res.push_back(0); } return res; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |