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

目录

⼆进制求和（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();
 }
}