加法
题目
415. 字符串相加
题解
class Solution {
public:
string addStrings(string num1, string num2) {
/**
* 对齐数字
* x = 123 , y = 4567
* x = 0123 , y = 4567
*/
if (num1.size() != num2.size())
{
if (num1.size() > num2.size())
{
auto len = num1.size() - num2.size();
for (int i = 0; i < len; i++)
{
num2.insert(0, "0");
}
}
else
{
auto len = num2.size() - num1.size();
for (int i = 0; i < len; i++)
{
num1.insert(0, "0");
}
}
}
/**
* 对齐后的字符串转换为倒置的 int 数组
* x = 0123 , y = 4567
* x = 3210 , y = 7654
*/
char *sx = const_cast<char *>(num1.c_str());
char *sy = const_cast<char *>(num2.c_str());
const size_t len = num1.size();
auto a = std::make_unique<int[]>(len);
auto b = std::make_unique<int[]>(len);
for (int i = 0; i < len; i++)
{
a[len - 1 - i] = sx[i] - '0';
}
for (int i = 0; i < len; i++)
{
b[len - 1 - i] = sy[i] - '0';
}
/** 计算 */
const size_t size = len + 1;
auto c = std::make_unique<int[]>(size);
for (int i = 0; i < len; i++)
{
c[i] += a[i] + b[i];
// 处理进位
if (c[i] >= 10)
{
c[i + 1] += c[i] / 10;
c[i] = c[i] % 10;
}
}
/** 翻转计算结果 */
std::string str;
int i = size - 1;
if(0 == c[i])
{
i--;
}
while( i >= 0 )
{
str.push_back(c[i] + '0');
i--;
}
return str;
}
};
减法
题目
P2142 高精度减法
题解
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
std::string substract(std::string x, std::string y)
{
// 结果是否为负数
bool isNegativeNumber = false;
/**
* 对齐数字
* x = 123 , y = 4567
* x = 0123 , y = 4567
*/
if (x.size() != y.size())
{
if (x.size() > y.size())
{
auto len = x.size() - y.size();
for (int i = 0; i < len; i++)
{
y.insert(0, "0");
}
}
else
{
auto len = y.size() - x.size();
for (int i = 0; i < len; i++)
{
x.insert(0, "0");
}
}
}
/**
* 数字排序
* s1 为较大数字
* s2 为较小数字
*/
std::string s1 = x;
std::string s2 = y;
if (s1.compare(s2) < 0)
{
s1 = y;
s2 = x;
isNegativeNumber = true;
}
/**
* 对齐后的字符串转换为倒置的 int 数组
* x = 0123 , y = 4567
* x = 3210 , y = 7654
*/
char *sx = const_cast<char *>(s1.c_str());
char *sy = const_cast<char *>(s2.c_str());
const size_t len = s1.size();
auto a = std::make_unique<int[]>(len);
auto b = std::make_unique<int[]>(len);
for (int i = 0; i < len; i++)
{
a[len - 1 - i] = sx[i] - '0';
}
for (int i = 0; i < len; i++)
{
b[len - 1 - i] = sy[i] - '0';
}
/** 计算 */
const size_t size = len;
auto c = std::make_unique<int[]>(size);
for (int i = 0; i < len; i++)
{
// 借位处理
if (a[i] < b[i])
{
a[i + 1]--;
a[i] += 10;
}
c[i] = a[i] - b[i];
}
/** 翻转计算结果 */
std::string str;
int i = size - 1;
// 删除前导0
while (0 == c[i] && i >= 1)
{
i--;
}
// 添加负号
if (isNegativeNumber)
{
str.push_back('-');
}
// 拼接计算结果
while (i >= 0)
{
str.push_back(c[i] + '0');
i--;
}
return str;
}
int main()
{
std::string s1, s2;
std::cin >> s1;
std::cin >> s2;
std::cout << substract(s1,s2) << std::endl;
return 0;
}
乘法
题目
43. 字符串相乘
题解
class Solution {
public:
string multiply(string x, string y) {
/**
* 字符串转换为倒置的 int 数组
* x = 123 , y = 4567
* x = 321 , y = 7654
*/
char *sx = const_cast<char *>(x.c_str());
char *sy = const_cast<char *>(y.c_str());
const size_t la = x.size() + 1;
const size_t lb = y.size() + 1;
auto a = std::make_unique<int[]>(la);
auto b = std::make_unique<int[]>(lb);
for (int i = 1; i < la; i++)
{
a[la - i] = sx[i-1] - '0';
}
for (int i = 1; i < lb; i++)
{
b[lb - i] = sy[i-1] - '0';
}
/** 计算 */
const size_t lc = x.size() + y.size() + 1;
auto c = std::make_unique<int[]>(lc);
for (int i = 1; i < la; i++)
{
for (int j = 1; j < lb; j++)
{
c[i + j - 1] += a[i] * b[j];
c[i + j] += c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
}
/** 翻转计算结果 */
std::string str;
int i = lc - 1;
while( 0 == c[i] && i > 1)
{
i--;
}
// 拼接计算结果
while (i >= 1)
{
str.push_back(c[i] + '0');
i--;
}
return str;
}
};
除法
题目
1006 . 大數除法
题解
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
int compare(std::string x, std::string y) {
if (x.size() < y.size()) {
return -1;
}
if (x.size() > y.size()) {
return 1;
}
return x.compare(y);
}
std::string add(std::string x, std::string y) {
/**
* 对齐数字
* x = 123 , y = 4567
* x = 0123 , y = 4567
*/
if (x.size() != y.size()) {
if (x.size() > y.size()) {
int len = x.size() - y.size();
for (int i = 0; i < len; i++) {
y.insert(0, "0");
}
} else {
int len = y.size() - x.size();
for (int i = 0; i < len; i++) {
x.insert(0, "0");
}
}
}
/**
* 对齐后的字符串转换为倒置的 int 数组
* x = 0123 , y = 4567
* x = 3210 , y = 7654
*/
char *sx = const_cast<char *>(x.c_str());
char *sy = const_cast<char *>(y.c_str());
const int len = x.size();
auto a = std::make_unique<int[]>(len);
auto b = std::make_unique<int[]>(len);
for (int i = 0; i < len; i++) {
a[len - 1 - i] = sx[i] - '0';
}
for (int i = 0; i < len; i++) {
b[len - 1 - i] = sy[i] - '0';
}
/** 计算 */
const int size = len + 1;
auto c = std::make_unique<int[]>(size);
for (int i = 0; i < len; i++) {
c[i] += a[i] + b[i];
// 处理进位
if (c[i] >= 10) {
c[i + 1] += c[i] / 10;
c[i] = c[i] % 10;
}
}
/** 翻转计算结果 */
std::string str;
int i = size - 1;
// 删除前导0
if (0 == c[i]) {
i--;
}
// 拼接计算结果
while (i >= 0) {
str.push_back(c[i] + '0');
i--;
}
return str;
}
std::string substract(std::string x, std::string y) {
// 结果是否为负数
bool isNegativeNumber = false;
/**
* 对齐数字
* x = 123 , y = 4567
* x = 0123 , y = 4567
*/
if (x.size() != y.size()) {
if (x.size() > y.size()) {
int len = x.size() - y.size();
for (int i = 0; i < len; i++) {
y.insert(0, "0");
}
} else {
int len = y.size() - x.size();
for (int i = 0; i < len; i++) {
x.insert(0, "0");
}
}
}
/**
* 数字排序
* s1 为较大数字
* s2 为较小数字
*/
std::string s1 = x;
std::string s2 = y;
if (s1.compare(s2) < 0) {
s1 = y;
s2 = x;
isNegativeNumber = true;
}
/**
* 对齐后的字符串转换为倒置的 int 数组
* x = 0123 , y = 4567
* x = 3210 , y = 7654
*/
char *sx = const_cast<char *>(s1.c_str());
char *sy = const_cast<char *>(s2.c_str());
const int len = s1.size();
auto a = std::make_unique<int[]>(len);
auto b = std::make_unique<int[]>(len);
for (int i = 0; i < len; i++) {
a[len - 1 - i] = sx[i] - '0';
}
for (int i = 0; i < len; i++) {
b[len - 1 - i] = sy[i] - '0';
}
/** 计算 */
const int size = len;
auto c = std::make_unique<int[]>(size);
for (int i = 0; i < len; i++) {
// 借位处理
if (a[i] < b[i]) {
a[i + 1]--;
a[i] += 10;
}
c[i] = a[i] - b[i];
}
/** 翻转计算结果 */
std::string str;
int i = size - 1;
// 删除前导0
while (0 == c[i] && i >= 1) {
i--;
}
// 添加负号
if (isNegativeNumber) {
str.push_back('-');
}
// 拼接计算结果
while (i >= 0) {
str.push_back(c[i] + '0');
i--;
}
return str;
}
std::string multiply(std::string x, std::string y) {
/**
* 字符串转换为倒置的 int 数组
* x = 123 , y = 4567
* x = 321 , y = 7654
*/
char *sx = const_cast<char *>(x.c_str());
char *sy = const_cast<char *>(y.c_str());
const int la = x.size() + 1;
const int lb = y.size() + 1;
auto a = std::make_unique<int[]>(la);
auto b = std::make_unique<int[]>(lb);
for (int i = 1; i < la; i++) {
a[la - i] = sx[i - 1] - '0';
}
for (int i = 1; i < lb; i++) {
b[lb - i] = sy[i - 1] - '0';
}
/** 计算 */
const int lc = x.size() + y.size() + 1;
auto c = std::make_unique<int[]>(lc);
for (int i = 1; i < la; i++) {
for (int j = 1; j < lb; j++) {
c[i + j - 1] += a[i] * b[j];
c[i + j] += c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
}
/** 翻转计算结果 */
std::string str;
int i = lc - 1;
while (0 == c[i] && i > 1) {
i--;
}
// 拼接计算结果
while (i >= 1) {
str.push_back(c[i] + '0');
i--;
}
return str;
}
std::string divide(std::string x, std::string y) {
// 被除数为 0 或者被除数小于除数, 均返回 0
if (0 == x.compare("0") || compare(x, y) < 0) {
return "0";
}
// 相等直接返回 1
if (0 == compare(x, y)) {
return "1";
}
// 除数为 1 , 直接返回被除数
if (0 == y.compare("1")) {
return x;
}
std::string str = "0";
std::string remainder;
// 被除数只比除数多一位, 则使用减法
if (x.size() - y.size() < 2) {
// 余数
remainder = x;
while (compare(remainder, y) >= 0) {
remainder = substract(remainder, y);
str = add(str, "1");
}
} else {
// 被除数比除数多两位或以上, 先用加法再用减法
// 余数
str = "0";
std::string times = "1";
std::string num = y;
std::string t = x;
while (t.size() - y.size() >= 2) {
while (compare(num, t) <= 0) {
remainder = num;
num = add(num, num);
if (compare(num, t) > 0) {
num = y;
str = add(str, times);
times = "1";
t = substract(t, remainder);
break;
}
times = multiply(times, "2");
}
}
remainder = t;
if (compare(remainder, y) >= 0) {
while (compare(remainder, y) >= 0) {
remainder = substract(remainder, y);
str = add(str, "1");
}
}
}
// std::cout << str << std::endl;
// std::cout << remainder << std::endl;
return str;
}
int main() {
std::string s1, s2;
std::cin >> s1;
std::cin >> s2;
std::cout << divide(s1, s2) << std::endl;
return 0;
}