【优选算法】（第三十二篇）

目录

⼆进制求和（easy）
题目分析
讲解算法原理
编写代码
字符串相乘（medium）
题目分析
讲解算法原理
编写代码

---

⼆进制求和（easy）

题目分析

1.题目链接：. - 力扣（LeetCode）
2.题目描述
   给你两个⼆进制字符串 a 和 b ，以⼆进制字符串的形式返回它们的和。
⽰例 1：
输⼊:a = "11", b = "1"
输出："100"
⽰例 2：
输⼊：a = "1010", b = "1011"
输出："10101"
  讲解算法原理

解法（模仿⼗进制的⼤数相加的过程）：
算法思路：
模仿⼗进制中我们列竖式盘算两个数之和的过程。但是这⾥是⼆进制的求和，我们不是逢⼗进⼀，⽽是逢⼆进⼀。
编写代码

c++算法代码：

1. class Solution
2. {
3. public:
4. string addBinary(string a, string b)
5. {
6. string ret;
7. int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
8. while(cur1 >= 0 || cur2 >= 0 || t)
9. {
10. if(cur1 >= 0) t += a[cur1--] - '0';
11. if(cur2 >= 0) t += b[cur2--] - '0';
12. ret += t % 2 + '0';
13. t /= 2;
14. }
15. reverse(ret.begin(), ret.end());
17. return ret;
18. }
19. };

复制代码

java算法代码：

1. class Solution
2. {
3. public String addBinary(String a, String b)
4. {
5. StringBuffer ret = new StringBuffer();
6. int cur1 = a.length() - 1, cur2 = b.length() - 1, t = 0;
7. while(cur1 >= 0 || cur2 >= 0 || t != 0)
8. {
9. if(cur1 >= 0) t += a.charAt(cur1--) - '0';
10. if(cur2 >= 0) t += b.charAt(cur2--) - '0';
11. ret.append((char)('0' + (char)(t % 2)));
12. t /= 2;
13. }
14. ret.reverse();
15. return ret.toString();
16. }
17. }

复制代码

字符串相乘（medium）

题目分析

1.题目链接：. - 力扣（LeetCode）
2.题目描述
   给定两个以字符串形式表⽰的⾮负整数num1和num2，返回num1和num2的乘积，它们的乘积也表⽰为字符串形式。
留意：不能使⽤任何内置的BigInteger库或直接将输⼊转换为整数。⽰例1:
输⼊:num1="2",num2="3"
输出:"6"
⽰例2:
输⼊:num1="123",num2="456"
输出:"56088"
  讲解算法原理

解法（⽆进位相乘然后相加，末了处置惩罚进位）：
算法思路：
整体思路就是模仿我们⼩学列竖式盘算两个数相乘的过程。但是为了我们书写代码的⽅便性，我们选择⼀种优化版本的，就是在盘算两数相乘的时候，先不思量进位，比及所有效果盘算完毕之后，再去思量进位。如下图：

 
编写代码

C++算法代码：

1. class Solution
2. {
3. public:
4. string multiply(string n1, string n2)
5. {
6. // 解法：⽆进位相乘后相加，然后处理进位
7. int m = n1.size(), n = n2.size();
8. reverse(n1.begin(), n1.end());
9. reverse(n2.begin(), n2.end());
10. vector<int> tmp(m + n - 1);
11. // 1. ⽆进位相乘后相加
12. for(int i = 0; i < m; i++)
13. for(int j = 0; j < n; j++)
14. tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
16. // 2. 处理进位
17. int cur = 0, t = 0;
18. string ret;
19. while(cur < m + n - 1 || t)
20. {
21. if(cur < m + n - 1) t += tmp[cur++];
22. ret += t % 10 + '0';
23. t /= 10;
24. }
25. // 3. 处理前导零
26. while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
27. reverse(ret.begin(), ret.end());
28. return ret;
29. }
30. };

复制代码

java算法代码：

1. class Solution
2. {
3. public String multiply(String num1, String num2)
4. {
5. int m = num1.length(), n = num2.length();
6. char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
7. char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();
8. int[] tmp = new int[m + n - 1];
9. // 1. ⽆进位相乘后相加
10. for(int i = 0; i < m; i++)
11. for(int j = 0; j < n; j++)
12. tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
14. // 2. 处理进位
15. int cur = 0, t = 0;
16. StringBuffer ret = new StringBuffer();
17. while(cur < m + n - 1 || t != 0)
18. {
19. if(cur < m + n - 1) t += tmp[cur++];
20. ret.append((char)(t % 10 + '0'));
21. t /= 10;
22. }
23. // 3. 处理进位
24. while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0')
25. ret.deleteCharAt((ret.length() - 1));
26. return ret.reverse().toString();
27. }
28. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。