当前位置:网站首页>【LeetCode】43. String multiplication
【LeetCode】43. String multiplication
2022-07-01 15:50:00 【Uaena_ An】
43. String multiplication
🧸 Reading questions
Give two strings , Multiply to get a string , This problem can't be solved by plastic surgery , Because the later test examples will be very large , plastic , Long plastic surgery can't be installed !
🧸 Ideas
To multiply by bits , Save in string , Then add the strings obtained by the product , The final result is stored in the string in turn ,
🧸 Code
class Solution {
public:
string addStrings(string& count, string& sum)
{
//end1,end2 Add from the tail of two numbers ,carry Record carry
int end1 = count.size() - 1, end2 = sum.size() - 1, carry = 0;
string ret;// Record the sum of two numbers added
while (end1 >= 0 || end2 >= 0)
{
// If end1 Greater than 0 shows count There are also a number , be x1 take end1 The value of a , Otherwise take 0
int x1 = 0;
if (end1 >= 0)
{
x1 = count[end1] - '0';
--end1;
}
int x2 = 0;
if (end2 >= 0)
{
x2 = sum[end2] - '0';
--end2;
}
//add Record the sum of two numbers added , Plus carry , The first carry is 0
int add = x1 + x2 + carry;
// If add Greater than 9, It indicates that carry is required , also add To subtract 10
// And enter the position 1 , Otherwise, enter the position 0, Otherwise, the carry will retain the result of the last carry , There will be errors
if (add > 9)
{
carry = 1;
add -= 10;
}
else {
carry = 0;
}
// Insert the remainder of the carry character at the end of ret in , Turn it over later , To improve efficiency
ret += add;
}
// Come here , It means that both numbers have been added , But there is also carry 1 position , Insert the tail
if (carry != 0)
{
ret += carry;
carry = 0;
}
// Flip
reverse(ret.begin(), ret.end());
// Convert to numeric characters
for (auto& e : ret)
{
e += '0';
}
return ret;
}
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0")
{
return "0";
}
string count = "0";// Record the sum
int end1 = num1.size() - 1, end2 = num2.size() - 1;
// Multiply by place ,num2 every * num1 All bits
for (int i = end2; i >= 0; --i)
{
string sum;// Record product
int carry = 0;// Record carry
// When j = i when , explain j Here you are . Is the last multiplication , Unwanted +0
// When j-- after j It's on the tenth , Multiply the number in the tens by other numbers , Directly in the back +1 individual 0, And so on
for (int j = end2; j > i; --j)
{
sum.push_back(0);
}
//i Control is num2 Flashback every bit of traversal
int x2 = num2[i] - '0';
// The following is to use x2 * num1 every
for (int j = end1; j >= 0; --j)
{
int x1 = num1[j] - '0';
int ret = x1 * x2 + carry;// Multiply two numbers + carry
sum += ret % 10;//sum Save a bit , Tail insertion
carry = ret / 10;//carry Save ten
}
// When two numbers are multiplied Rounding and numbers , You need to Carry tail interpolation
while (carry != 0) {
sum += carry % 10;
carry /= 10;
}
// After tail insertion Flip strings
reverse(sum.begin(), sum.end());
// Convert a string into a numeric string
for (auto &e : sum) {
e += '0';
}
count = addStrings(count, sum);
}
return count;
}
};
🧸 Decoding code
The interpretation code has been written in the code comments !
make blind and disorderly conjectures
This problem is done 2 Hours , Read the explanation of the question , Understand the solution step by step , Then I tried to write , Half understood , I will do it again several times in the future
come on. I wish you get what you want offer!
边栏推荐
- 2022-07-01日报:谷歌新研究:Minerva,用语言模型解决定量推理问题
- Recommendation of data acquisition tools and detailed graphic process of data acquisition list
- Pico, can we save consumer VR?
- 【显存优化】深度学习显存优化方法
- 张驰课堂:六西格玛数据的几种类型与区别
- "Qt+pcl Chapter 6" point cloud registration ICP Series 6
- 入侵检测模型(An Intrusion-Detection Model)
- 并发编程系列之什么是ForkJoin框架?
- 【OpenCV 例程200篇】216. 绘制多段线和多边形
- Sort out the four commonly used sorting functions in SQL
猜你喜欢
《性能之巅第2版》阅读笔记(五)--file-system监测
GaussDB(for MySQL) :Partial Result Cache,通过缓存中间结果对算子进行加速
ATSS:自动选择样本,消除Anchor based和Anchor free物体检测方法之间的差别
Microservice tracking SQL (support Gorm query tracking under isto control)
STM32ADC模拟/数字转换详解
【OpenCV 例程200篇】216. 绘制多段线和多边形
Pnas: brain and behavior changes of social anxiety patients with empathic embarrassment
Équipe tensflow: Nous ne sommes pas abandonnés
#夏日挑战赛# HarmonyOS canvas实现时钟
RT-Thread Env 工具介绍(学习笔记)
随机推荐
Returning to the top of the list, the ID is still weak
[video memory optimization] deep learning video memory optimization method
Qt+pcl Chapter 6 point cloud registration ICP Series 5
微信小程序03-文字一左一右显示,行内块元素居中
马来西亚《星报》:在WTO MC12 孙宇晨仍在坚持数字经济梦想
华为发布HCSP-Solution-5G Security人才认证,助力5G安全人才生态建设
Zero copy technology of MySQL
STM32ADC模拟/数字转换详解
RT-Thread Env 工具介绍(学习笔记)
Pico, can we save consumer VR?
做空蔚来的灰熊,以“碰瓷”中概股为生?
Phpcms background upload picture button cannot be clicked
《性能之巅第2版》阅读笔记(五)--file-system监测
精益六西格玛项目辅导咨询:集中辅导和点对点辅导两种方式
swiper 轮播图,最后一张图与第一张图无缝衔接
TensorFlow團隊:我們沒被拋弃
并发编程系列之什么是ForkJoin框架?
药品溯源夯实安全大堤
Photoshop插件-HDR(二)-脚本开发-PS插件
phpcms后台上传图片按钮无法点击