动态规划法,时间和空间复杂度均为O(n)
此方法超出时间限制。
用滚动数组思想,把空间复杂度优化成O(1)
官方题解的方法2,3没看。
class Solution { public: string addBinary(string a, string b) { int len_a = a.length(); int len_b = b.length(); string ans; int help = 0; int i, j, k; for(i = len_a - 1, j = len_b - 1; i >= 0 && j >= 0; i--, j--){ k = (a[i] -'0') + (b[j] - '0') + help; if(k == 3){ ans += '1'; help = 1; }else if(k == 2){ ans += '0'; help = 1; }else if(k == 1){ ans += '1'; help = 0; }else{//0 ans += '0'; help = 0; } } while(i >= 0 || j >= 0){ if(i >= 0){ k = (a[i] - '0') + help; } else{ k = (b[j] - '0') + help; } if(k == 2){ ans += '0'; help = 1; }else if(k == 1){ ans += '1'; help = 0; }else{ if(i >= 0){ ans += a[i]; }else if(j >= 0){ ans += b[j]; } } i--, j--; } if(help == 1){ ans += '1'; } string ture_ans; for(int i = ans.length()-1; i >= 0; i--){ ture_ans += ans[i]; } return ture_ans; } };
这题要注意的是:(int)ans[i] = (int)('1')的结果是49,字符1的ASCII码值。要想取这个字符1转换为数字1,应该写成('1' - '0').
标签:12,help,int,else,力扣,--,ans,string,刷题 From: https://www.cnblogs.com/spp20/p/18409996