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

目录

⼆进制求和（easy）

题目解析

讲解算法原理

编写代码

字符串相乘（medium）

题目解析

讲解算法原理

编写代码

---

⼆进制求和（easy）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你两个⼆进制字符串 a 和 b ，以⼆进制字符串的形式返回它们的和。
⽰例 1：
输⼊:a = "11", b = "1"
输出："100"
⽰例 2：
输⼊：a = "1010", b = "1011"
输出："10101"

讲解算法原理

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

编写代码

c++算法代码：

class Solution
{
public:string addBinary(string a, string b) {string ret;int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;while(cur1 >= 0 || cur2 >= 0 || t){if(cur1 >= 0) t += a[cur1--] - '0';if(cur2 >= 0) t += b[cur2--] - '0';ret += t % 2 + '0';t /= 2;}reverse(ret.begin(), ret.end());return ret;}
};

java算法代码：

class Solution
{public String addBinary(String a, String b) {StringBuffer ret = new StringBuffer();int cur1 = a.length() - 1, cur2 = b.length() - 1, t = 0;while(cur1 >= 0 || cur2 >= 0 || t != 0){if(cur1 >= 0) t += a.charAt(cur1--) - '0';if(cur2 >= 0) t += b.charAt(cur2--) - '0';ret.append((char)('0' + (char)(t % 2)));t /= 2;}ret.reverse();return ret.toString();}
}

字符串相乘（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定两个以字符串形式表⽰的⾮负整数num1和num2，返回num1和num2的乘积，它们的乘积也表⽰为字符串形式。
注意：不能使⽤任何内置的BigInteger库或直接将输⼊转换为整数。⽰例1:
输⼊:num1="2",num2="3"
输出:"6"
⽰例2:
输⼊:num1="123",num2="456"
输出:"56088"

讲解算法原理

解法（⽆进位相乘然后相加，最后处理进位）：
算法思路：
整体思路就是模拟我们⼩学列竖式计算两个数相乘的过程。但是为了我们书写代码的⽅便性，我们选择⼀种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。如下图：

 

编写代码

C++算法代码：

class Solution
{
public:string multiply(string n1, string n2) {// 解法：⽆进位相乘后相加，然后处理进位int m = n1.size(), n = n2.size();reverse(n1.begin(), n1.end());reverse(n2.begin(), n2.end());vector<int> tmp(m + n - 1);// 1. ⽆进位相乘后相加for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');// 2. 处理进位int cur = 0, t = 0;string ret;while(cur < m + n - 1 || t){if(cur < m + n - 1) t += tmp[cur++];ret += t % 10 + '0';t /= 10;}// 3. 处理前导零while(ret.size() > 1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};

java算法代码：

class Solution
{public String multiply(String num1, String num2) {int m = num1.length(), n = num2.length();char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();int[] tmp = new int[m + n - 1];// 1. ⽆进位相乘后相加for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');// 2. 处理进位int cur = 0, t = 0;StringBuffer ret = new StringBuffer();while(cur < m + n - 1 || t != 0){if(cur < m + n - 1) t += tmp[cur++];ret.append((char)(t % 10 + '0'));t /= 10;}// 3. 处理进位while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') ret.deleteCharAt((ret.length() - 1));return ret.reverse().toString();}
}