nowcoder NC10 大数乘法
题目链接:
https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571?tpId=196&tqId=37177&rp=1&ru=/exam/company&qru=/exam/company&sourceUrl=%2Fexam%2Fcompany&difficulty=undefined&judgeStatus=undefined&tags=&title=
题目描述:
以字符串的形式读入两个数字,编写一个函数计算它们的乘积,以字符串形式返回。
数据范围: 读入的数字大小满足
要求:空间复杂度 O(m),时间复杂度 O()(假设m是n的长度)
示例1:
输入:"11","99"
返回值:"1089"
说明:11*99=1089
示例2:
输入:"1","0"
返回值:"0"
答案:
import java.util.*;public class Solution {public String solve (String s, String t) {// write code hereif (s.charAt(0) == '0' || t.charAt(0) == '0'){return "0";}String ret = "0";String[] tmp = new String[t.length()]; for (int i = t.length() - 1; i >= 0; i--){tmp[i] = "";int j = t.length() - 1;while(j - i > 0){tmp[i] += '0';j--;}tmp[i] += alongMultiply(s, t.charAt(i));}for (int i = t.length() - 1; i >= 0; i--){ret = Add(tmp[i], ret);}StringBuffer stringBuffer = new StringBuffer();for (int i = ret.length() - 1; i >= 0; i--){stringBuffer.append(ret.charAt(i));}ret = stringBuffer.toString();return ret;}public String Add(String a, String b){String str = "";int aLen = a.length() - 1;int ai = 0;int bLen = b.length() - 1;int bi = 0;int ten = 0;while(aLen >= ai && bLen >= bi){int tmp = (a.charAt(ai++) - '0') + (b.charAt(bi++) - '0');tmp += ten;ten = tmp / 10;str += tmp % 10;}while(aLen >= ai){int tmp = a.charAt(ai++) - '0';tmp += ten;ten = tmp / 10;str += tmp % 10;}while(bLen >= bi){int tmp = b.charAt(bi++) - '0';tmp += ten;ten = tmp / 10;str += tmp % 10;}if (ten != 0){str += ten;}return str;}public String alongMultiply(String s, char t){String ret = "";if (s.charAt(0) == '0' || t == '0'){return "0";}int tt = t - '0';int ten = 0;for (int i = s.length() - 1; i >= 0; i--){int tmp = s.charAt(i) - '0';tmp *= tt;tmp += ten;ten = tmp / 10;ret += tmp % 10;}if (ten != 0){ret += ten;}return ret;}
}
详解:
从题目中我们可以得到以下几点信息:
- 输入值和返回值都是字符串类型;
- 输入值和返回值不可以直接转换成整数(因为数字过大);
- 对时间复杂度几乎没有要求;
- 不会出现负数乘法。
当我们清楚了题目要求之后就该考虑该如何解题了。
首先我们应该考虑的是乘法是如何进行计算的!
我们以 11 * 99 为例:
我们可以分析得到无论是几位数的乘法都是按照以下步骤进行的:
- 将第一个数字分别乘以第二个数的每一位;
- 如果第一个数乘的是第二个数的个位就给结果乘一,十位就乘十 以此类推;
- 最后一步就是将各各结果相加。
到这一步之后如果你想在题目给的那一个方法里面实现这些内容就会大大提高你写代码的难度,此时其实我推荐将其用三个方法来实现。
- 第一个为主函数,主要用来实现代码的整体思路;
- 第二个为相乘的方法,其主要功能是实现一个 n 位数与一位数相乘;
- 第三个为相加的方法,其主要功能是实现两个 n 位数的相加。
根据乘法的定义可以知道:0 与任何数相乘都是 0 所以我们的第一段代码就可以为:
public String solve (String s, String t) {// write code hereif (s.charAt(0) == '0' || t.charAt(0) == '0'){return "0";}}
接下来就是对每一位进行相乘但是我们并不知道是 几位数与几位数进行相乘 所以我们此时应该根据 t 的长度来定义一个字符串数组 tmp 用来存储 t 中的每一位与 s 相乘的结果。
再定义一个名为 alongMultiply() 的方法 此方法就用来实现n 位数与一位数相乘并将其值以字符串的形式进行返回。(此方法可以先不急着实现)。
再定义一个名为 的字符串类型的变量,将其初始化为“0” 用来存储最终的返回值。
因为会有进位而导致最后结果的位数充满不确定性所以我们可以采用倒序的存储方式
即:12345 存储为 54321
因为加法也会有进位所以我们可以在主方法的最后统一进行反转。
public String solve (String s, String t) {// write code hereif (s.charAt(0) == '0' || t.charAt(0) == '0'){return "0";}String ret = "0";//新加的代码String[] tmp = new String[t.length()]; for (int i = t.length() - 1; i >= 0; i--){tmp[i] = "";int j = t.length() - 1;while(j - i > 0){ //相当于十位乘十 , 百位乘一百……tmp[i] += '0';j--;}tmp[i] += alongMultiply(s, t.charAt(i));}
}
紧接着我们再将 tmp数组 中的所有值进行相加存储在 ret 中。
for (int i = t.length() - 1; i >= 0; i--){ret = Add(tmp[i], ret);
}
到这里我们的整体布局已经完成了,接下来就该实现 alongMultiply() 方法了:
public String alongMultiply(String s, char t){String ret = ""; //用来存储最后的返回值if (s.charAt(0) == '0' || t == '0'){return "0";}int tt = t - '0';int ten = 0; //用来存储每次的进位for (int i = s.length() - 1; i >= 0; i--){int tmp = s.charAt(i) - '0';tmp *= tt;tmp += ten;ten = tmp / 10;ret += tmp % 10;}if (ten != 0){ret += ten;}return ret;}
Add() 方法的实现:
public String Add(String a, String b){String str = ""; //存储最终的返回值int aLen = a.length() - 1;int ai = 0;int bLen = b.length() - 1;int bi = 0;int ten = 0; //用来存储每次的进位while(aLen >= ai && bLen >= bi){int tmp = (a.charAt(ai++) - '0') + (b.charAt(bi++) - '0');tmp += ten;ten = tmp / 10;str += tmp % 10;}while(aLen >= ai){int tmp = a.charAt(ai++) - '0';tmp += ten;ten = tmp / 10;str += tmp % 10;}while(bLen >= bi){int tmp = b.charAt(bi++) - '0';tmp += ten;ten = tmp / 10;str += tmp % 10;}if (ten != 0){str += ten;}return str;}
接下来我们只要再将最终的值进行反转本题就算做完了:
StringBuffer stringBuffer = new StringBuffer();for (int i = ret.length() - 1; i >= 0; i--){stringBuffer.append(ret.charAt(i));}ret = stringBuffer.toString();
当然你也可以用(我用上面的方法主要是因为它比较快):
tmp[0] = ret;ret = "";for (int i = tmp[0].length() - 1; i >= 0; i--){ret += tmp[0].charAt(i);}
相关文章:
nowcoder NC10 大数乘法
题目链接: https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571?tpId196&tqId37177&rp1&ru/exam/company&qru/exam/company&sourceUrl%2Fexam%2Fcompany&difficultyundefined&judgeStatusundefined&tags&tit…...
非科班菜鸡算法学习记录 | 代码随想录算法训练营第58天|| 单调栈! 739. 每日温度 496.下一个更大元素 I
739. 每日温度 输入一个数组,找比i天温度高的第一天 知识点:单调栈 状态:看思路自己写 思路: 看自己写的注释,维护一个单调栈 // 版本一 class Solution { public:vector<int> dailyTemperatures(vector<…...
【Luogu】 P5445 [APIO2019] 路灯
题目链接 点击打开链接 题目解法 转化很妙 考虑关路灯 x x x 的操作 令左边第一个未关的路灯为 L L L,右边第一个未关的路灯为 R R R,那么这一次会影响的区间即为 l ∈ [ L 1 , x ] , r ∈ [ x , R − 1 ] l\in[L1,x],\;r\in[x,R-1] l∈[L1,x],…...
Kafka3.0.0版本——消费者(独立消费者消费某一个主题中某个分区数据案例__订阅分区)
目录 一、独立消费者消费某一个主题中某个分区数据案例1.1、案例需求1.2、案例代码1.3、测试 一、独立消费者消费某一个主题中某个分区数据案例 1.1、案例需求 创建一个独立消费者,消费firstTopic主题 0 号分区的数据,所下图所示: 1.2、案…...
基于Simulink的用于电力系统动态分析
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
日200亿次调用,喜马拉雅网关的架构设计
说在前面 在40岁老架构师 尼恩的读者社区(50)中,很多小伙伴拿到一线互联网企业如阿里、网易、有赞、希音、百度、滴滴的面试资格。 最近,尼恩指导一个小伙伴简历,写了一个《API网关项目》,此项目帮这个小伙拿到 字节/阿里/微博/…...
构造函数和析构函数(个人学习笔记黑马学习)
构造函数:主要作用在于创建对象时为对象的成员属性赋值,构造函数由编译器自动调用,无须手动调用。析构函数:主要作用在于对象销毁前系统自动调用,执行一些清理工作。 #include <iostream> using namespace std;//对象初始化和清理class…...
GPT引领前沿与应用突破之GPT4科研实践技术与AI绘图教程
详情点击链接:GPT引领前沿与应用突破之GPT4科研实践技术与AI绘图教程 前沿 GPT对于每个科研人员已经成为不可或缺的辅助工具,不同的研究领域和项目具有不同的需求。 如在科研编程、绘图领域: 1、编程建议和示例代码: 无论你使用的编程语言是…...
Git上传新项目
第一步:初始化 Git 仓库 首先,打开终端或命令行界面,然后导航到项目目录。运行下面的命令来初始化一个新的 Git 仓库: git init这将创建一个新的 .git 子目录,其中包含了初始化的 Git 仓库。 第二步:添加…...
C语言文件操作总结
目录 字符方式读入文件 数据块方式读写文件 文件定位与随机读写 文件中数据的修改 字符方式读入文件 1.向文件中写入(输入字符) 用 fputc 函数或 puts 函数可以把一个字符写到磁盘文件中去。 int fputc(int ch,FILE * fp) ch 是要输出的字符&#…...
原生js之dom如何进行事件监听(事件捕获/冒泡)
那么好,这次主要讲解的就是dom是如何进行事件监听和事件取消监听的,我们知道vue中主要用watch来进行监听. js监听与取消监听 那么原生js主要用到的就是addListenEvent事件来进行监听,可以监听文档dom对象也可以监听浏览器bom对象,监听事件的语法结构如下 Dom/Bom监听 eleme…...
使用SimPowerSystems并网光伏阵列研究(Simulink实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
BUUCTF-WEB-[ACTF2020 新生赛]Includel
打开靶机 点击tips 利用Burp抓包,未见异常 但发现了响应头是 PHP/7.3.13 想到了"php://input"伪协议POST发送PHP代码 构建Payload:?filephp://filter/readconvert.base64-encode/resourceflag.php 这里需要注意的是使用php://filter伪协议…...
算法通关村十四关:白银挑战-堆能高效解决的经典问题
白银挑战-堆能高效解决的经典问题 1.在数组中找第K大的元素 LeetCode215 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 思路分析 主要解决方法有3个,选择法,堆查找法和快速排序法 方法1:选择法 先遍历一遍找到最大的…...
跨站请求伪造(CSRF)攻击与防御原理
跨站请求伪造(CSRF) 1.1 CSRF原理 1.1.1 基本概念 跨站请求伪造(Cross Site Request Forgery,CSRF)是一种攻击,它强制浏览器客户端用户在当前对其进行身份验证后的Web 应用程序上执行非本意操作的攻击&a…...
从0到1实现播放控制器
这系列文章主要讲诉如何从0到1使用QT实现带时间显示、滚动字幕等的自定义配置视频播放控制器。平时我们乘坐地铁经常看到各条线的播放控制器都大同小异。其实都是通过QT等界面开发软件来实现的。 在具体开发之前,需要明确我们需要做什么? 1. 开发一个可…...
【Vue-Element-Admin】导出el-table全部数据
背景 因为el-table实现了分页查询,所以想要实现el-table需要重新编写一个查询全部数据的方法 查询全部数据 listQuery: export default{return{listQuery:{//page:1,//limit:20,//如果想兼容按条件导出,可以定义查询条件age:undefined,sex:undefined…...
MFC 更改控件的大小和位置
获取当前主窗体的位置rect CRect dlgNow;GetWindowRect(&dlgNow);获取某一个控件当前的位置 CRect rect;CButton* pBtn (CButton*)GetDlgItem(IDC_BUTTONXXX);//获取按钮控件pBtn->GetWindowRect(rect);CWnd* pWnd(CWnd*)GetDlgItem(IDC_EDITXXX);//其它控件࿰…...
【向量数据库】相似向量检索Faiss数据库的安装及余弦相似度计算(C++)
目录 简介安装方法安装OpenBLAS安装lapack编译Faiss 代码示例余弦相似度计算输出ID号而非索引的改进版 简介 Faiss 是一个强大的向量相似度搜索库,具有以下优点: 高效的搜索性能:Faiss 在处理大规模向量数据时表现出色。它利用了高度优化的索…...
教育培训小程序的设计与功能解析
随着互联网的发展,线上教育逐渐成为一种趋势,越来越多的人开始选择在线学习。而搭建一个适合自己的线上教育小程序,可以为教育机构或个人提供更好的教学和学习体验。在本文中,我们将介绍如何通过一个第三方制作平台来搭建在线教育…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
从零手写Java版本的LSM Tree (一):LSM Tree 概述
🔥 推荐一个高质量的Java LSM Tree开源项目! https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree,专为高并发写入场景设计。 核心亮点: ⚡ 极致性能:写入速度超…...
RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上
一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema,不需要复杂的查询,只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 :在几秒钟…...
