如何高效解决“字符串相乘“问题?

这篇具有很好参考价值的文章主要介绍了如何高效解决“字符串相乘“问题?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
如何高效解决“字符串相乘“问题?,刷题集,c++,c语言,算法>🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
金句分享:
✨你要狠下心来去努力,努力变成一个很厉害的人.✨

前言

本题牛牛写了很久,起初对每次相乘的结果就进位处理了,最后还需要考虑错位相加,进行补0等,花了半天也没搞出来.
所幸学到了一种高效且相对简单的方法解决此题,希望对友友们有所帮助.
如何高效解决“字符串相乘“问题?,刷题集,c++,c语言,算法

一、字符串相乘

题目介绍

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

思路分析

如何高效解决“字符串相乘“问题?,刷题集,c++,c语言,算法

  1. 同时从两个字符串的右边开始往前遍历相乘.

  2. num2中的每一个字符依次与与num1中的每个字符想乘.

  3. 将相乘的结果保存在一个arr数组中,每个相乘的结果放入正确的位置(i+J+1).
    如何高效解决“字符串相乘“问题?,刷题集,c++,c语言,算法

  4. arr数组创建多大的空间?
    一个最小的二位数 × 一个最小的三位数 结果是一个四位数
    10100=1000
    一个最大的二位数 × 一个最大的三位数 结果是一个五位数
    99
    999=98901
    综上呢,两个数相乘,他们的结果的位数是[length1 + length2,length1 + length2+1],(0除外哈)
    最高位可能有数据,也可能没有数据.

  5. 为什么正确的位置是i+j+1?
    试着看上图分析:注意ij都是从右边往左边遍历.
    此处是此解法的难点,通过将每次相乘后的结果放入正确的位置以实现错位相加.
    牛牛的理解是:
    j是内循环,从右往左遍历num1,i是外循环,决定的是num2.
    所以用j的变化控制与num1相乘结果的位置,用i的变化,控制错位相加(即相乘的结果要往左移动一位)即num2的位变化.

  6. 对错位相加后的数组进行进位处理:从右往左进位
    (1)先保存元素的值,tmp = arr[i]+carry;
    (2)替换为进位后的数据: arr[i] = (arr[i] + carry) % 10;
    (3)保存进位数: carry = tmp / 10;

  7. 将进位后的数组中的数据依次尾插入amass对象中.
    注意:先判断第一个位置有没有有效数据(即最高位是否有效)

  8. 最后,处理特殊情况,如果num1和num2中有一个是0,则直接返回0.

代码实现:

class Solution {
public:
    string multiply(string num1, string num2) {
    //处理特殊情况,如果有一方为0,
        if (num1[0] == '0' || num2[0] == '0') return string("0");
        int length1 = num1.size();
        int length2 = num2.size();
        int arr[length1 + length2];
        //将数组中的元素全部初始化为0
        for (auto& a : arr)
        {
            a = 0;
        }
        string amass;
        //相乘
        //内外层循环控制num2和num1 的次序无所谓
        //版本1
        for (int i = length2 -1; i >= 0; i--){//外层循环控制num2
            int s1 = num2[i] - '0';
            for (int j = length1 - 1; j >= 0; j--){//内存循环控制num1
                int s2 = num1[j] - '0';
                arr[i+j+1] += s1 * s2;//注意这里是+=
            }
        }
        //版本2
       /*
        for (int i = length1 - 1; i >= 0; i--)
        {
            int s1 = num1[i] - '0';
            for (int j = length2 - 1; j >= 0; j--)
            {
                int s2 = num2[j] - '0';
                arr[i + j + 1] += s1 * s2;//注意这里是+=
            }
        }
    */
        //处理进位问题:
        int carry = 0;
        for (int i = length1 + length2 - 1; i >= 0; i--)
        {
       		int tmp = arr[i]+carry;				//保存当前位置中的元素大小,因为下一句代码会影响giabarr[j]
            arr[i] = (arr[i] + carry) % 10;       //存放个位数
            carry = tmp / 10;          			 //存放十位数(进位数
        }

        //第一个位置是否有元素,最高位是否有效
        if (arr[0] != 0)
            amass.push_back(arr[0] + '0');
        //
        for (int i = 1; i < length1 + length2; i++)
        {
            amass.push_back(arr[i] + '0');
        }
        return amass;
    }
};

最后,感谢友友们阅读本篇解题分享,希望这篇文章对您在解决问题过程中有所帮助。在解题过程中,我们需要不断思考、尝试、调整,才能得出正确的解决方案。同时,我们也要记得不断学习、积累知识和经验,提升自己的能力。最后,祝您在解决问题的道路上越走越远,不断成长和进步。
如何高效解决“字符串相乘“问题?,刷题集,c++,c语言,算法文章来源地址https://www.toymoban.com/news/detail-653758.html

到了这里,关于如何高效解决“字符串相乘“问题?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【string题解 C++】字符串相乘 | 翻转字符串III:翻转单词

    目录 字符串相乘 题面 错误记录 Way1 拆分成“先乘后加” 思路 实现 时空复杂度分析 反思 Way2 用数组 思路 实现 时空复杂度分析 翻转字符串III:翻转字符串中的单词 题面 错误记录 思路1 遍历找单词 实现 思路2 暴力解法 实现 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平

    2024年02月07日
    浏览(59)
  • 算法刷题-字符串-左旋转字符串

    反转个字符串还有这么多用处? 力扣题目链接 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串\\\"abcdefg\\\"和数字2,该函数将返回左旋转两位得到的结果\\\"cdefgab\\\"。 示例 1: 输入: s = “abcde

    2024年02月09日
    浏览(47)
  • 算法刷题-字符串-反转字符串II

    简单的反转还不够,我要花式反转 力扣题目链接 给定一个字符串 s 和一个整数 k,从字符串开头算起, 每计数至 2k 个字符,就反转这 2k 个字符中的前 k 个字符。 如果剩余字符少于 k 个,则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,

    2024年02月09日
    浏览(48)
  • 算法刷题-字符串-重复的子字符串

    KMP算法还能干这个 力扣题目链接 给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。 示例 1: 输入: “abab” 输出: True 解释: 可由子字符串 “ab” 重复两次构成。 示例 2: 输入: “aba” 输出: False 示

    2024年02月09日
    浏览(49)
  • 算法刷题-字符串-翻转字符串里的单词

    综合考察字符串操作的好题。 力扣题目链接 给定一个字符串,逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: \\\" hello world! \\\" 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不

    2024年02月09日
    浏览(99)
  • IDEA java: 常量字符串过长问题解决

    Error:(41, 41) java: 常量字符串过长 1、字符串长度过长,导致idea默认使用的javac编译器编译不了。 解决办法: Javac编译器改为Eclipse编译器。 File-Settings-Build.Execution,Deployment-Compiler-Java Compiler 旭东怪的个人空间-旭东怪个人主页-哔哩哔哩视频 哔哩哔哩旭东怪的个人空间,提供旭东

    2024年02月11日
    浏览(57)
  • 【C语言】字符串---刷题篇

    Hi,C站的小伙伴们大家好呀!😊🥰,欢迎来阅读我的这一篇 【C语言】字符串基础刷题篇! 不知你是否和我一样,在刚刚接触到这块的知识时,总是会和这神圣的知识隔着隔着厚厚的一堵墙,迷茫的眼神中总是会露出不理解不理解😣😣(当时的状态……) 其实后来我就发现其实

    2024年02月03日
    浏览(42)
  • 【算法刷题之字符串篇】

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 1.将 left 指向字符数组首元素,right 指向字符数组尾元素。 2.当 left right: 交换 s

    2024年02月10日
    浏览(44)
  • 解决因base64字符串过长,报500的问题

    提示:后端用nodejs的express,前端是vue 当上传的图片小(base64字符串长度小)时,上传成功 当上传的图片大(base64字符串长度过长)时,上传失败,接口报500,服务器也报了一大堆的错误。 如果直接把base64字符串复制到数据库发现报错,提示数据太长,很明显是因为base64字符

    2024年02月11日
    浏览(47)
  • C语言——oj刷题——回文字符串

    问题: 实现一个函数,判断一个字符串是否为回文字符串。 回文字符串是指正读和反读都相同的字符串。例如,\\\"level\\\"、\\\"radar\\\"和\\\"madam\\\"都是回文字符串。 要解决这个问题,我们可以使用两个指针分别指向字符串的首尾字符,然后逐步向中间移动,同时比较指针所指向的字符是

    2024年02月21日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包