字符串相乘(43)

43. 字符串相乘 - 力扣(LeetCode)

解法:

class Solution {
public:string multiply(string num1, string num2) {string res = "0";for (int i = 0; i < num2.size(); ++i) {string str = multiplyOneNum(num1, num2[num2.size() - 1 - i], i);res = add(res, str);}return res;}private :string add(const string & num1, const string & num2){string res;res.reserve(max(num1.size(), num2.size()) + 1);int idx1 = num1.size() - 1;int idx2 = num2.size() - 1;int carry = 0;while (idx1 >= 0 || idx2 >= 0 || carry > 0) {int num = 0;if (idx1 >= 0) {num += static_cast<int>(num1[idx1--] - '0');}if (idx2 >= 0) {num += static_cast<int>(num2[idx2--] - '0');}if (carry > 0) {num += carry;}carry = num / 10;num = num % 10;res.push_back(static_cast<char>(num + static_cast<int>('0')));}reverse(res.begin(), res.end());res.shrink_to_fit();return res;}string multiplyOneNum(const string & num1, const char & one_num , int times = 0){if (one_num == '0' || num1 == "0") {return "0";}string res;res.reserve(num1.size() + 1 + times);int carry = 0;for (int i = num1.size() - 1; i >= 0; --i) {int num = static_cast<int>(num1[i] - '0') * static_cast<int>(one_num - '0');if (carry > 0) {num += carry;}carry = num / 10;num = num % 10;res.push_back(static_cast<char>(num + static_cast<int>('0')));}if (carry) {res.push_back(static_cast<char>(carry + static_cast<int>('0')));}reverse(res.begin(), res.end());if (times > 0) {res.append(times, '0');}res.shrink_to_fit();return res;}
};

總結:

設num1的長度是m,num2的長度是n,multiplyOneNum函數的時間復雜度是O(m), 由于result的長度是m + n,所以add函數的時間復雜度是O(m+n),外面又一層循環n,所以時間的計算復雜度是O(mn) + O(mn + n2),即O(mn + n2)。無論是?multiplyOneNum函數還是add函數最長使用的字符串長度是m+n,所以空間復雜度是O(m+n)。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/81431.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/81431.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/81431.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

mathematics-2024《Graph Convolutional Network for Image Restoration: A Survey》

推薦深藍學院的《深度神經網絡加速&#xff1a;cuDNN 與 TensorRT》&#xff0c;課程面向就業&#xff0c;細致講解CUDA運算的理論支撐與實踐&#xff0c;學完可以系統化掌握CUDA基礎編程知識以及TensorRT實戰&#xff0c;并且能夠利用GPU開發高性能、高并發的軟件系統&#xf…

[LevelDB]LevelDB版本管理的黑魔法-為什么能在不鎖表的情況下管理數據?

文章摘要 LevelDB的日志管理系統是怎么通過雙鏈表來進行數據管理為什么LevelDB能夠在不鎖表的情況下進行日志新增 適用人群: 對版本管理機制有開發訴求&#xff0c;并且希望參考LevelDB的版本開發機制。數據庫相關從業者的專業人士。計算機狂熱愛好者&#xff0c;對計算機的…

【C++進階篇】C++容器完全指南:掌握set和map的使用,提升編碼效率

C容器的實踐與應用&#xff1a;輕松掌握set、map與multimap的區別與用法 一. 序列式容器與關聯式容器1.1 序列式容器 (Sequential Containers)1.2 關聯式容器 (Associative Containers) 二. set系列使用2.1 set的構造和迭代器2.2 set的增刪查2.2.1 插入2.2.2 查找2.2.3 刪除 2.…

2_Spring【IOC容器中獲取組件Bean】

Spring中IOC容器中獲取組件Bean 實體類 //接口 public interface TestDemo {public void doSomething(); } // 實現類 public class HappyComponent implements TestDemo {public void doSomething() {System.out.println("HappyComponent is doing something...")…

安卓開飯-ScrollView內嵌套了多個RecyclerView,只想與其中一個RecyclerView有聯動

在 Android 開發中&#xff0c;將 RecyclerView 嵌套在 ScrollView 內通常會導致性能問題和滾動沖突&#xff0c;應盡量避免這種設計。以下是原因和替代方案&#xff1a; 為什么不推薦 RecyclerView ScrollView&#xff1f;?? 性能損耗? RecyclerView 本身已自帶高效回收復…

HTTP 請求中 Content-Type 頭部

HTTP 請求中 Content-Type 頭部可以設置的各種不同的傳輸格式。multipart/form-data 只是其中一種,主要用于傳輸包含文件的數據。 以下是一些常見的 HTTP 請求體的 Content-Type 及其用途: 常見的數據傳輸格式 (Content-Type) 列表: application/json: 描述: 用于傳輸 JSO…

【U-boot 命令使用】

文章目錄 1 查詢有哪些命令2 信息查詢命令dbinfo - 查看板子信息printenv- 輸出環境變量信息version - 輸出uboot版本信息 3 環境變量操作命令修改環境變量新建環境變量刪除環境變量 4 內存操作命令md命令nm命令mm命令mv命令cp命令cmp命令 5 網絡操作命令與網絡有關的環境變量p…

初學者如何用 Python 寫第一個爬蟲?

初學者如何用 Python 寫第一個爬蟲&#xff1f; 一、爬蟲的基本概念 &#xff08;一&#xff09;爬蟲的定義 爬蟲&#xff0c;英文名為 Web Crawler&#xff0c;也被叫做網絡蜘蛛、網絡機器人。想象一下&#xff0c;有一個勤勞的小蜘蛛&#xff0c;在互聯網這個巨大的蜘蛛網中…

IDE/IoT/搭建物聯網(LiteOS)集成開發環境,基于 VSCode + IoT Link 插件

文章目錄 概述IDE安裝安裝舊版本VSCode安裝插件安裝問題和解決手動安裝SDK包手動下載依賴工具 IoTLink配置IoTLink Home用戶設置-工具鏈-編譯器用戶設置-工具鏈-構建器用戶設置-工具鏈-燒錄器用戶設置-SDK管理工程設置-SDK配置工程設置-編譯器工程設置-調試器 創建工程Demo 源碼…

深度剖析:Dify+Sanic+Vue+ECharts 搭建 Text2SQL 項目 sanic-web 的 Debug 實戰

目錄 項目背景介紹sanic-web Dify\_service handle\_think\_tag報錯NoneType問題描述debug Dify調用不成功&#xff0c;一直轉圈圈問題描述debug 前端markdown格式只顯示前5頁問題描述debug1. 修改代碼2.重新構建1.1.3鏡像3.更新sanic-web/docker/docker-compose.yaml4. 重新部…

理想AI Talk第二季-重點信息總結

一、TL&#xff1b;DR 理想為什么要做自己的基模&#xff1a;座艙家庭等特殊VLM場景&#xff0c;deepseek/openai沒有解決理想的基模參數量&#xff1a;服務端-300B&#xff0c;VLencoder-32B/3.6B&#xff0c;日常工作使用-300B&#xff0c;VLA-4B為什么自動駕駛可以達成&…

TensorRT

TensorRT 下載 TensorRT 7.1.3.4 TAR壓縮包&#xff0c;解壓到安裝目錄&#xff1a; tar xzvf TensorRT-7.1.3.4.Ubuntu-16.04.x86_64-gnu.cuda-11.0.cudnn8.0.tar.gz 添加 TensorRT lib 到環境變量&#xff1a; gedit ~/.bashrc # 添加 export LD_LIBRARY_PATH$LD_LIBRARY_PAT…

【NGINX】 -9 nginx + tomcat實現的多級反向代理

文章目錄 1、tomcat的安裝 (centos版本)1.1 安裝Java依賴環境1.2 安裝tomcat 2、tomcat的虛擬主機的配置2.1 配置多級目錄 3、利用nginx的反向代理實現將轉發指向一個虛擬機3.1 nginx服務器的配置3.2 客戶端配置 4、 反向多級代理代理服務器操作nginx 1 服務器nginx 2 服務器to…

基于requests_html的python爬蟲

前言&#xff1a;今天介紹一個相對性能更高的爬蟲庫requests_html&#xff0c;會不會感覺和requests有點聯系&#xff1f;是的。為什么開始不直接介紹呢&#xff1f;因為我覺得requests是最基本入門的東西&#xff0c;并且在學習過程中也能學到很多東西。我的python老師在介紹這…

【架構篇】架構類型解釋

架構設計的本質&#xff1a;從模糊概念到系統化思維 摘要 “架構”是系統設計的靈魂&#xff0c;但許多人對它的理解仍停留在抽象層面。本文系統解析架構的8大核心維度&#xff0c;結合設計原則、案例與誤區分析&#xff0c;幫助開發者建立從戰略到落地的完整認知框架。 一、架…

用Python繪制夢幻星空

用Python繪制夢幻星空 在這篇教程中&#xff0c;我們將學習如何使用Python創建一個美麗的星空場景。我們將使用Python的圖形庫Pygame和隨機庫來創建閃爍的星星、流星和月亮&#xff0c;打造一個動態的夜空效果。 項目概述 我們將實現以下功能&#xff1a; 創建深藍色的夜…

PyTorch循環神經網絡(Pytotch)

文章目錄 循環神經網絡&#xff08;RNN&#xff09;簡單的循環神經網絡長短期記憶網絡&#xff08;LSTM&#xff09;門控循環單元&#xff08;GRU&#xff09; 循環神經網絡&#xff08;RNN&#xff09; 循環神經網絡&#xff08;RecurrentNeuralNetwork&#xff0c;RNN&#…

用算術右移實現邏輯右移及用邏輯右移實現算術右移

函數srl()用算術右移實現邏輯右移&#xff0c;函數sra()用邏輯右移實現算術右移。 程序代碼 int sra(int x,int k); unsigned int srl(unsigned int x, int k);void main() {int rx1,k,x1;unsigned int rx2,x2;k3;x10x8777;x20x8777;rx1sra(x1, k);rx2srl(x2, k);while(1); }…

pojo層、dao層、service層、controller層的作用

在Java Web開發中&#xff0c;常見的分層架構&#xff08;如Spring Boot項目&#xff09;通常包含POJO層、DAO層、Service層和Controller層&#xff0c;各層職責明確&#xff0c;協同工作。以下是各層的作用及相互關系&#xff1a; 1. POJO層&#xff08;Model/Entity層&#…

【Linux網絡】五種IO模型與阻塞IO

IO 在Linux網絡環境里&#xff0c;IO&#xff08;Input/Output&#xff09;指的是網絡數據在系統與外部網絡&#xff08;像其他設備、服務器或者客戶端&#xff09;之間進行傳輸的過程。 它是網絡編程和系統性能優化的核心內容。 IO &#xff1a;INPUT和OUTPUT&#xff08;站…