|
#2
rjsp2021-09-15 11:31
我写了段代码试试
 程序代码：std::string addBinary( const std::string_view a, const std::string_view b ) { const size_t alen = a.size(); const size_t blen = b.size(); const size_t clen = std::max( alen, blen ) + 1; // "+1" 是因为可能存在进位 std::string c( clen, 0 ); char carry = 0; for( size_t i = 0; i != clen; ++i ) { if( i < alen ) carry += a[alen - 1 - i] - '0'; if( i < blen ) carry += b[blen - 1 - i] - '0'; c[clen - 1 - i] = carry % 2 + '0'; carry /= 2; } if( c[0] == '0' ) c.erase( 0, 1 ); return c; } 根本不存在多余的空间消耗，但leetcode显示 执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户 看来，leetcode 的计算就不准内存消耗：6 MB, 在所有 C++ 提交中击败了94.70% 的用户 |
程序代码：给你两个二进制字符串，返回它们的和（用二进制表示）。 //思路对十进制，八进制，十六进制整数同样有效
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。
链接：https://
先后提交了两种解法，我觉得第一种解法应该比第二种解法内存占用要低的，因为第二种毕竟用到了reverse函数
但是运行的结果是前者占用6.2-6.4M，超过40%的用户，后者5.9-6.0M，超过99%的用户。
问题：
为什么是第二种解法占用的空间反而少了？
顺便问下，是否前者空间复杂度是O（1），后者是O（n）？
望解答，谢谢
代码如下：
第一种：
程序代码：class Solution {
public:
string addBinary(string a, string b) {
int addZero=max(a.size(),b.size());//统一这两个数的位数
int carry=0;//carry代表上一位是否产生进位，初始化为否
for(int i=a.size();i<addZero;i++) a='0'+a; //前端补0
for(int i=b.size();i<addZero;i++) b='0'+b; //前端补0
//cout<<a<<"\n"<<b<<endl;
for(int i=addZero-1;i>=0;--i)//从最右侧依次向左
{
if(carry+a[i]-'0'+b[i]-'0'<2) //如果carry与两个位数相加后小于2，即不产生进位，那么直接相加
{
a[i]=(carry+a[i]-'0')+(b[i]-'0')+'0';//直接相加
carry=0;//表示不产生进位
}
else if(carry+a[i]-'0'+b[i]-'0'>=2) //如果相加后产生进位
{
a[i]=(carry+a[i]-'0'+b[i]-'0')%2+'0';//将相加结果对2取余，完成这个数位的进位
carry=1;//产生进位，下一个位数相加同时还要加上carry
}
}
if(carry==1) //如果遍历结束最后还产生进位，那么就要在结果最前方再加一个数位“1”
a="1"+a;
return a;
}
};
第二种：
程序代码：class Solution {
public:
string addBinary(string a, string b) {
string ans;//新建一个字符串
reverse(a.begin(), a.end()); //翻转这两个字符串，后续从左往右开始遍历，相加，最后结果ans再翻转一次，就是最终结果
reverse(b.begin(), b.end());
int m = a.size(), n = b.size(), t = 0;
for(int i = 0; i < m || i < n; i++) {
if(i < m) t += a[i] - '0';//只要有一个数还没有遍历完，就继续把对应数位的结果赋给ans
if(i < n) t += b[i] - '0';
ans.push_back(t % 2 + '0');
t /= 2;
}
if(t) ans.push_back(t + '0');
reverse(ans.begin(), ans.end());
return ans;
}
};
代码有疑问的话，我把解题思路写在博客里了，https://，望解答，谢谢
