【华为机试】43. 字符串相乘
文章目录
- 43. 字符串相乘
43. 字符串相乘
描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2
输入: num1 = “123”, num2 = “456”
输出: “56088”
提示
- 1 <= num1.length, num2.length <= 200
- num1 和 num2 只能由数字组成。
- num1 和 num2 都不包含任何前导零，除了数字0本身。
解题思路
算法分析
这道题是大数乘法和模拟手算乘法的经典应用。主要解法包括：
- 模拟乘法法：模拟小学乘法竖式运算过程
- 分治乘法法：使用Karatsuba算法进行分治
- FFT乘法法：使用快速傅里叶变换（复杂度最优但实现复杂）
- 逐位相乘法：每一位分别相乘后处理进位
问题本质分析
#mermaid-svg-FS8XGcaoHIrYWO7q {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-FS8XGcaoHIrYWO7q .error-icon{fill:#552222;}#mermaid-svg-FS8XGcaoHIrYWO7q .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-FS8XGcaoHIrYWO7q .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-FS8XGcaoHIrYWO7q .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-FS8XGcaoHIrYWO7q .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-FS8XGcaoHIrYWO7q .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-FS8XGcaoHIrYWO7q .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-FS8XGcaoHIrYWO7q .marker{fill:#333333;stroke:#333333;}#mermaid-svg-FS8XGcaoHIrYWO7q .marker.cross{stroke:#333333;}#mermaid-svg-FS8XGcaoHIrYWO7q svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-FS8XGcaoHIrYWO7q .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-FS8XGcaoHIrYWO7q .cluster-label text{fill:#333;}#mermaid-svg-FS8XGcaoHIrYWO7q .cluster-label span{color:#333;}#mermaid-svg-FS8XGcaoHIrYWO7q .label text,#mermaid-svg-FS8XGcaoHIrYWO7q span{fill:#333;color:#333;}#mermaid-svg-FS8XGcaoHIrYWO7q .node rect,#mermaid-svg-FS8XGcaoHIrYWO7q .node circle,#mermaid-svg-FS8XGcaoHIrYWO7q .node ellipse,#mermaid-svg-FS8XGcaoHIrYWO7q .node polygon,#mermaid-svg-FS8XGcaoHIrYWO7q .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-FS8XGcaoHIrYWO7q .node .label{text-align:center;}#mermaid-svg-FS8XGcaoHIrYWO7q .node.clickable{cursor:pointer;}#mermaid-svg-FS8XGcaoHIrYWO7q .arrowheadPath{fill:#333333;}#mermaid-svg-FS8XGcaoHIrYWO7q .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-FS8XGcaoHIrYWO7q .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-FS8XGcaoHIrYWO7q .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-FS8XGcaoHIrYWO7q .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-FS8XGcaoHIrYWO7q .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-FS8XGcaoHIrYWO7q .cluster text{fill:#333;}#mermaid-svg-FS8XGcaoHIrYWO7q .cluster span{color:#333;}#mermaid-svg-FS8XGcaoHIrYWO7q div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-FS8XGcaoHIrYWO7q :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 字符串相乘 大数乘法问题 模拟竖式乘法 分治算法 FFT算法 逐位相乘累加 Karatsuba算法 频域乘法 时间复杂度O_mn空间复杂度O_m+n 时间复杂度O_n^1.585空间复杂度O_n 时间复杂度O_nlogn空间复杂度O_n
模拟乘法算法详解
flowchart TD A[输入num1和num2] --> B[处理特殊情况] B --> C{是否包含0} C -->|是| D[返回\"0\"] C -->|否| E[初始化结果数组] E --> F[双重循环遍历] F --> G[计算单位乘积] G --> H[累加到对应位置] H --> I[处理进位] I --> J[继续下一位] J --> K{是否完成所有位} K -->|否| F K -->|是| L[处理最终进位] L --> M[转换为字符串] M --> N[去除前导零] N --> O[返回结果]乘法竖式过程演示
#mermaid-svg-CC87AOi87cKgEJkt {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-CC87AOi87cKgEJkt .error-icon{fill:#552222;}#mermaid-svg-CC87AOi87cKgEJkt .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-CC87AOi87cKgEJkt .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-CC87AOi87cKgEJkt .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-CC87AOi87cKgEJkt .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-CC87AOi87cKgEJkt .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-CC87AOi87cKgEJkt .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-CC87AOi87cKgEJkt .marker{fill:#333333;stroke:#333333;}#mermaid-svg-CC87AOi87cKgEJkt .marker.cross{stroke:#333333;}#mermaid-svg-CC87AOi87cKgEJkt svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-CC87AOi87cKgEJkt .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-CC87AOi87cKgEJkt .cluster-label text{fill:#333;}#mermaid-svg-CC87AOi87cKgEJkt .cluster-label span{color:#333;}#mermaid-svg-CC87AOi87cKgEJkt .label text,#mermaid-svg-CC87AOi87cKgEJkt span{fill:#333;color:#333;}#mermaid-svg-CC87AOi87cKgEJkt .node rect,#mermaid-svg-CC87AOi87cKgEJkt .node circle,#mermaid-svg-CC87AOi87cKgEJkt .node ellipse,#mermaid-svg-CC87AOi87cKgEJkt .node polygon,#mermaid-svg-CC87AOi87cKgEJkt .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-CC87AOi87cKgEJkt .node .label{text-align:center;}#mermaid-svg-CC87AOi87cKgEJkt .node.clickable{cursor:pointer;}#mermaid-svg-CC87AOi87cKgEJkt .arrowheadPath{fill:#333333;}#mermaid-svg-CC87AOi87cKgEJkt .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-CC87AOi87cKgEJkt .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-CC87AOi87cKgEJkt .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-CC87AOi87cKgEJkt .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-CC87AOi87cKgEJkt .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-CC87AOi87cKgEJkt .cluster text{fill:#333;}#mermaid-svg-CC87AOi87cKgEJkt .cluster span{color:#333;}#mermaid-svg-CC87AOi87cKgEJkt div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-CC87AOi87cKgEJkt :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 输入: \'123\' × \'456\' 竖式分解 123 × 6 = 738 123 × 5 = 615（左移1位） 123 × 4 = 492（左移2位） 位置对应: 738 位置对应: 6150 位置对应: 49200 累加求和 738 + 6150 + 49200 = 56088
位置索引计算规则
#mermaid-svg-og3QvOaNhJuSTzQ4 {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-og3QvOaNhJuSTzQ4 .error-icon{fill:#552222;}#mermaid-svg-og3QvOaNhJuSTzQ4 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-og3QvOaNhJuSTzQ4 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-og3QvOaNhJuSTzQ4 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-og3QvOaNhJuSTzQ4 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-og3QvOaNhJuSTzQ4 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-og3QvOaNhJuSTzQ4 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-og3QvOaNhJuSTzQ4 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-og3QvOaNhJuSTzQ4 .marker.cross{stroke:#333333;}#mermaid-svg-og3QvOaNhJuSTzQ4 svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-og3QvOaNhJuSTzQ4 .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-og3QvOaNhJuSTzQ4 .cluster-label text{fill:#333;}#mermaid-svg-og3QvOaNhJuSTzQ4 .cluster-label span{color:#333;}#mermaid-svg-og3QvOaNhJuSTzQ4 .label text,#mermaid-svg-og3QvOaNhJuSTzQ4 span{fill:#333;color:#333;}#mermaid-svg-og3QvOaNhJuSTzQ4 .node rect,#mermaid-svg-og3QvOaNhJuSTzQ4 .node circle,#mermaid-svg-og3QvOaNhJuSTzQ4 .node ellipse,#mermaid-svg-og3QvOaNhJuSTzQ4 .node polygon,#mermaid-svg-og3QvOaNhJuSTzQ4 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-og3QvOaNhJuSTzQ4 .node .label{text-align:center;}#mermaid-svg-og3QvOaNhJuSTzQ4 .node.clickable{cursor:pointer;}#mermaid-svg-og3QvOaNhJuSTzQ4 .arrowheadPath{fill:#333333;}#mermaid-svg-og3QvOaNhJuSTzQ4 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-og3QvOaNhJuSTzQ4 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-og3QvOaNhJuSTzQ4 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-og3QvOaNhJuSTzQ4 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-og3QvOaNhJuSTzQ4 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-og3QvOaNhJuSTzQ4 .cluster text{fill:#333;}#mermaid-svg-og3QvOaNhJuSTzQ4 .cluster span{color:#333;}#mermaid-svg-og3QvOaNhJuSTzQ4 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-og3QvOaNhJuSTzQ4 :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 位置计算规律 乘法位置规则 num1[i] × num2[j] 结果位置: i + j + 1 进位位置: i + j 个位数放入i+j+1 十位数累加到i+j 避免数组越界 正确处理进位
算法流程图
flowchart TD A[开始] --> B[特殊情况检查] B --> C{num1或num2为\"0\"} C -->|是| D[返回\"0\"] C -->|否| E[创建结果数组] E --> F[外层循环i: num1从右到左] F --> G[内层循环j: num2从右到左] G --> H[计算乘积: digit1 × digit2] H --> I[累加到result[i+j+1]] I --> J[处理进位到result[i+j]] J --> K{内层循环结束?} K -->|否| G K -->|是| L{外层循环结束?} L -->|否| F L -->|是| M[构造结果字符串] M --> N[跳过前导零] N --> O[返回结果]进位处理机制
#mermaid-svg-0T7KXyxlXtd3Yfsh {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-0T7KXyxlXtd3Yfsh .error-icon{fill:#552222;}#mermaid-svg-0T7KXyxlXtd3Yfsh .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-0T7KXyxlXtd3Yfsh .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-0T7KXyxlXtd3Yfsh .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-0T7KXyxlXtd3Yfsh .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-0T7KXyxlXtd3Yfsh .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-0T7KXyxlXtd3Yfsh .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-0T7KXyxlXtd3Yfsh .marker{fill:#333333;stroke:#333333;}#mermaid-svg-0T7KXyxlXtd3Yfsh .marker.cross{stroke:#333333;}#mermaid-svg-0T7KXyxlXtd3Yfsh svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-0T7KXyxlXtd3Yfsh .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-0T7KXyxlXtd3Yfsh .cluster-label text{fill:#333;}#mermaid-svg-0T7KXyxlXtd3Yfsh .cluster-label span{color:#333;}#mermaid-svg-0T7KXyxlXtd3Yfsh .label text,#mermaid-svg-0T7KXyxlXtd3Yfsh span{fill:#333;color:#333;}#mermaid-svg-0T7KXyxlXtd3Yfsh .node rect,#mermaid-svg-0T7KXyxlXtd3Yfsh .node circle,#mermaid-svg-0T7KXyxlXtd3Yfsh .node ellipse,#mermaid-svg-0T7KXyxlXtd3Yfsh .node polygon,#mermaid-svg-0T7KXyxlXtd3Yfsh .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-0T7KXyxlXtd3Yfsh .node .label{text-align:center;}#mermaid-svg-0T7KXyxlXtd3Yfsh .node.clickable{cursor:pointer;}#mermaid-svg-0T7KXyxlXtd3Yfsh .arrowheadPath{fill:#333333;}#mermaid-svg-0T7KXyxlXtd3Yfsh .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-0T7KXyxlXtd3Yfsh .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-0T7KXyxlXtd3Yfsh .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-0T7KXyxlXtd3Yfsh .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-0T7KXyxlXtd3Yfsh .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-0T7KXyxlXtd3Yfsh .cluster text{fill:#333;}#mermaid-svg-0T7KXyxlXtd3Yfsh .cluster span{color:#333;}#mermaid-svg-0T7KXyxlXtd3Yfsh div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-0T7KXyxlXtd3Yfsh :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 进位处理 当前位累加 计算商和余数 余数保留在当前位 商加到高位 当前位 = sum % 10 高位 += sum / 10 确保单位数字 传递进位 继续下一位处理
各种解法对比
graph TD A[解法对比] --> B[模拟乘法] A --> C[分治算法] A --> D[FFT算法] A --> E[字符串加法组合] B --> F[时间O_mn空间O_m+n] C --> G[时间O_n^1.585空间O_logn] D --> H[时间O_nlogn空间O_n] E --> I[时间O_mn²空间O_mn] F --> J[简单直观推荐] G --> K[大数优化] H --> L[理论最优复杂实现] I --> M[易理解效率低]Karatsuba分治算法
flowchart TD A[Karatsuba算法] --> B[分割数字] B --> C[x = x1×10^m + x0] B --> D[y = y1×10^m + y0] C --> E[递归计算] D --> E E --> F[z0 = x0 × y0] E --> G[z2 = x1 × y1] E --> H[z1 = (x0+x1) × (y0+y1) - z0 - z2] F --> I[组合结果] G --> I H --> I I --> J[result = z2×10^2m + z1×10^m + z0]边界情况处理
graph TD A[边界情况] --> B[零值处理] A --> C[单位数字] A --> D[极大数字] A --> E[相同数字] B --> F[\"0\" × 任何数 = \"0\"] C --> G[直接计算后转字符串] D --> H[200位×200位=400位] E --> I[数字平方运算] F --> J[提前返回优化] G --> J H --> K[数组容量预分配] I --> K时间复杂度分析
- 模拟乘法：O(m×n)，m和n分别为两数字长度
- Karatsuba：O(n^log₂3) ≈ O(n^1.585)
- FFT乘法：O(n log n)，n为较大数字长度
- 字符串累加：O(m×n²)，效率最低
空间复杂度分析
- 模拟乘法：O(m+n)，结果数组空间
- Karatsuba：O(log n)，递归栈空间
- FFT乘法：O(n)，变换数组空间
- 字符串累加：O(m×n)，中间结果存储
关键优化点
#mermaid-svg-kGXgobTvYehzy0UY {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-kGXgobTvYehzy0UY .error-icon{fill:#552222;}#mermaid-svg-kGXgobTvYehzy0UY .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-kGXgobTvYehzy0UY .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-kGXgobTvYehzy0UY .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-kGXgobTvYehzy0UY .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-kGXgobTvYehzy0UY .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-kGXgobTvYehzy0UY .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-kGXgobTvYehzy0UY .marker{fill:#333333;stroke:#333333;}#mermaid-svg-kGXgobTvYehzy0UY .marker.cross{stroke:#333333;}#mermaid-svg-kGXgobTvYehzy0UY svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-kGXgobTvYehzy0UY .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-kGXgobTvYehzy0UY .cluster-label text{fill:#333;}#mermaid-svg-kGXgobTvYehzy0UY .cluster-label span{color:#333;}#mermaid-svg-kGXgobTvYehzy0UY .label text,#mermaid-svg-kGXgobTvYehzy0UY span{fill:#333;color:#333;}#mermaid-svg-kGXgobTvYehzy0UY .node rect,#mermaid-svg-kGXgobTvYehzy0UY .node circle,#mermaid-svg-kGXgobTvYehzy0UY .node ellipse,#mermaid-svg-kGXgobTvYehzy0UY .node polygon,#mermaid-svg-kGXgobTvYehzy0UY .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-kGXgobTvYehzy0UY .node .label{text-align:center;}#mermaid-svg-kGXgobTvYehzy0UY .node.clickable{cursor:pointer;}#mermaid-svg-kGXgobTvYehzy0UY .arrowheadPath{fill:#333333;}#mermaid-svg-kGXgobTvYehzy0UY .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-kGXgobTvYehzy0UY .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-kGXgobTvYehzy0UY .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-kGXgobTvYehzy0UY .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-kGXgobTvYehzy0UY .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-kGXgobTvYehzy0UY .cluster text{fill:#333;}#mermaid-svg-kGXgobTvYehzy0UY .cluster span{color:#333;}#mermaid-svg-kGXgobTvYehzy0UY div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-kGXgobTvYehzy0UY :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 优化策略 特殊值检查 数组预分配 进位优化 算法选择 零值提前返回 避免动态扩容 批量处理进位 根据数据规模选择 性能提升
实际应用场景
#mermaid-svg-xmxFUWQ7xmGPG67u {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-xmxFUWQ7xmGPG67u .error-icon{fill:#552222;}#mermaid-svg-xmxFUWQ7xmGPG67u .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-xmxFUWQ7xmGPG67u .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-xmxFUWQ7xmGPG67u .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-xmxFUWQ7xmGPG67u .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-xmxFUWQ7xmGPG67u .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-xmxFUWQ7xmGPG67u .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-xmxFUWQ7xmGPG67u .marker{fill:#333333;stroke:#333333;}#mermaid-svg-xmxFUWQ7xmGPG67u .marker.cross{stroke:#333333;}#mermaid-svg-xmxFUWQ7xmGPG67u svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-xmxFUWQ7xmGPG67u .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-xmxFUWQ7xmGPG67u .cluster-label text{fill:#333;}#mermaid-svg-xmxFUWQ7xmGPG67u .cluster-label span{color:#333;}#mermaid-svg-xmxFUWQ7xmGPG67u .label text,#mermaid-svg-xmxFUWQ7xmGPG67u span{fill:#333;color:#333;}#mermaid-svg-xmxFUWQ7xmGPG67u .node rect,#mermaid-svg-xmxFUWQ7xmGPG67u .node circle,#mermaid-svg-xmxFUWQ7xmGPG67u .node ellipse,#mermaid-svg-xmxFUWQ7xmGPG67u .node polygon,#mermaid-svg-xmxFUWQ7xmGPG67u .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-xmxFUWQ7xmGPG67u .node .label{text-align:center;}#mermaid-svg-xmxFUWQ7xmGPG67u .node.clickable{cursor:pointer;}#mermaid-svg-xmxFUWQ7xmGPG67u .arrowheadPath{fill:#333333;}#mermaid-svg-xmxFUWQ7xmGPG67u .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-xmxFUWQ7xmGPG67u .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-xmxFUWQ7xmGPG67u .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-xmxFUWQ7xmGPG67u .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-xmxFUWQ7xmGPG67u .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-xmxFUWQ7xmGPG67u .cluster text{fill:#333;}#mermaid-svg-xmxFUWQ7xmGPG67u .cluster span{color:#333;}#mermaid-svg-xmxFUWQ7xmGPG67u div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-xmxFUWQ7xmGPG67u :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 应用场景 密码学 金融计算 科学计算 竞赛编程 RSA加密算法 高精度金额计算 大整数运算库 ACM算法竞赛 核心算法组件
算法扩展
#mermaid-svg-2CLW9yRtUF10Wk3z {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-2CLW9yRtUF10Wk3z .error-icon{fill:#552222;}#mermaid-svg-2CLW9yRtUF10Wk3z .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-2CLW9yRtUF10Wk3z .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-2CLW9yRtUF10Wk3z .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-2CLW9yRtUF10Wk3z .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-2CLW9yRtUF10Wk3z .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-2CLW9yRtUF10Wk3z .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-2CLW9yRtUF10Wk3z .marker{fill:#333333;stroke:#333333;}#mermaid-svg-2CLW9yRtUF10Wk3z .marker.cross{stroke:#333333;}#mermaid-svg-2CLW9yRtUF10Wk3z svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-2CLW9yRtUF10Wk3z .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-2CLW9yRtUF10Wk3z .cluster-label text{fill:#333;}#mermaid-svg-2CLW9yRtUF10Wk3z .cluster-label span{color:#333;}#mermaid-svg-2CLW9yRtUF10Wk3z .label text,#mermaid-svg-2CLW9yRtUF10Wk3z span{fill:#333;color:#333;}#mermaid-svg-2CLW9yRtUF10Wk3z .node rect,#mermaid-svg-2CLW9yRtUF10Wk3z .node circle,#mermaid-svg-2CLW9yRtUF10Wk3z .node ellipse,#mermaid-svg-2CLW9yRtUF10Wk3z .node polygon,#mermaid-svg-2CLW9yRtUF10Wk3z .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-2CLW9yRtUF10Wk3z .node .label{text-align:center;}#mermaid-svg-2CLW9yRtUF10Wk3z .node.clickable{cursor:pointer;}#mermaid-svg-2CLW9yRtUF10Wk3z .arrowheadPath{fill:#333333;}#mermaid-svg-2CLW9yRtUF10Wk3z .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-2CLW9yRtUF10Wk3z .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-2CLW9yRtUF10Wk3z .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-2CLW9yRtUF10Wk3z .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-2CLW9yRtUF10Wk3z .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-2CLW9yRtUF10Wk3z .cluster text{fill:#333;}#mermaid-svg-2CLW9yRtUF10Wk3z .cluster span{color:#333;}#mermaid-svg-2CLW9yRtUF10Wk3z div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-2CLW9yRtUF10Wk3z :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 算法扩展 大数加法 大数减法 大数除法 大数幂运算 字符串数值运算基础 借位处理机制 长除法模拟 快速幂优化 大数运算库
测试用例设计
graph TD A[测试用例] --> B[基础功能] A --> C[边界情况] A --> D[性能测试] B --> E[小数相乘] B --> F[大数相乘] B --> G[不同长度] C --> H[零值情况] C --> I[单位数] C --> J[最大长度] D --> K[200位×200位] D --> L[相同数字平方] E --> M[验证正确性] F --> M G --> M H --> M I --> M J --> M K --> N[验证性能] L --> N代码实现要点
-
数组索引设计：
- 结果数组长度为m+n
- 乘法位置计算：i+j和i+j+1
- 从右到左处理数字
-
进位处理逻辑：
- 先累加所有同位置的乘积
- 再统一处理进位
- 避免重复进位计算
-
边界条件处理：
- 零值特殊处理
- 前导零移除
- 数组越界检查
-
性能优化技巧：
- 预分配数组容量
- 减少字符串操作
- 选择合适的算法
手算验证示例
#mermaid-svg-i4z1E8CVTIHcdLmV {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-i4z1E8CVTIHcdLmV .error-icon{fill:#552222;}#mermaid-svg-i4z1E8CVTIHcdLmV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-i4z1E8CVTIHcdLmV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-i4z1E8CVTIHcdLmV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-i4z1E8CVTIHcdLmV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-i4z1E8CVTIHcdLmV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-i4z1E8CVTIHcdLmV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-i4z1E8CVTIHcdLmV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-i4z1E8CVTIHcdLmV .marker.cross{stroke:#333333;}#mermaid-svg-i4z1E8CVTIHcdLmV svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-i4z1E8CVTIHcdLmV .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-i4z1E8CVTIHcdLmV .cluster-label text{fill:#333;}#mermaid-svg-i4z1E8CVTIHcdLmV .cluster-label span{color:#333;}#mermaid-svg-i4z1E8CVTIHcdLmV .label text,#mermaid-svg-i4z1E8CVTIHcdLmV span{fill:#333;color:#333;}#mermaid-svg-i4z1E8CVTIHcdLmV .node rect,#mermaid-svg-i4z1E8CVTIHcdLmV .node circle,#mermaid-svg-i4z1E8CVTIHcdLmV .node ellipse,#mermaid-svg-i4z1E8CVTIHcdLmV .node polygon,#mermaid-svg-i4z1E8CVTIHcdLmV .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-i4z1E8CVTIHcdLmV .node .label{text-align:center;}#mermaid-svg-i4z1E8CVTIHcdLmV .node.clickable{cursor:pointer;}#mermaid-svg-i4z1E8CVTIHcdLmV .arrowheadPath{fill:#333333;}#mermaid-svg-i4z1E8CVTIHcdLmV .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-i4z1E8CVTIHcdLmV .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-i4z1E8CVTIHcdLmV .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-i4z1E8CVTIHcdLmV .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-i4z1E8CVTIHcdLmV .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-i4z1E8CVTIHcdLmV .cluster text{fill:#333;}#mermaid-svg-i4z1E8CVTIHcdLmV .cluster span{color:#333;}#mermaid-svg-i4z1E8CVTIHcdLmV div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-i4z1E8CVTIHcdLmV :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 123 × 456手算过程 第一步 3×6=18, 3×5=15, 3×4=12 第二步 2×6=12, 2×5=10, 2×4=8 第三步 1×6=6, 1×5=5, 1×4=4 位置累加 位置0:18, 位置1:15+12, 位置2:12+10+6 位置3:8+5, 位置4:4 处理进位得到56088
这个问题的关键在于理解乘法竖式的计算规律和掌握进位处理的机制，通过模拟手算过程实现高精度的字符串乘法运算。
完整题解代码
package mainimport (\"fmt\"\"strconv\"\"strings\"\"time\")// 解法一：模拟乘法竖式（推荐解法）// 时间复杂度：O(m×n)，空间复杂度：O(m+n)func multiply(num1 string, num2 string) string {// 特殊情况：任一数字为0if num1 == \"0\" || num2 == \"0\" {return \"0\"}m, n := len(num1), len(num2)// 结果最多有 m+n 位result := make([]int, m+n)// 从右到左遍历两个数字for i := m - 1; i >= 0; i-- {digit1 := int(num1[i] - \'0\')for j := n - 1; j >= 0; j-- {digit2 := int(num2[j] - \'0\')// 计算乘积并加到对应位置product := digit1 * digit2posLow := i + j + 1 // 个位posHigh := i + j // 十位// 累加到当前位sum := product + result[posLow]result[posLow] = sum % 10 // 保留个位result[posHigh] += sum / 10 // 进位到高位}}// 转换为字符串，跳过前导零var sb strings.Builderstart := 0for start < len(result) && result[start] == 0 {start++}for i := start; i < len(result); i++ {sb.WriteByte(byte(result[i] + \'0\'))}return sb.String()}// 解法二：优化的模拟乘法（预处理优化）// 时间复杂度：O(m×n)，空间复杂度：O(m+n)func multiplyOptimized(num1 string, num2 string) string {if num1 == \"0\" || num2 == \"0\" {return \"0\"}m, n := len(num1), len(num2)result := make([]int, m+n)// 预转换字符为数字，减少重复转换digits1 := make([]int, m)digits2 := make([]int, n)for i := 0; i < m; i++ {digits1[i] = int(num1[i] - \'0\')}for i := 0; i < n; i++ {digits2[i] = int(num2[i] - \'0\')}// 执行乘法for i := m - 1; i >= 0; i-- {for j := n - 1; j >= 0; j-- {product := digits1[i] * digits2[j]posLow := i + j + 1posHigh := i + jsum := product + result[posLow]result[posLow] = sum % 10result[posHigh] += sum / 10}}// 构建结果字符串var sb strings.Buildersb.Grow(m + n) // 预分配容量start := 0for start < len(result) && result[start] == 0 {start++}for i := start; i < len(result); i++ {sb.WriteByte(byte(result[i] + \'0\'))}return sb.String()}// 解法三：字符串加法组合// 时间复杂度：O(m×n²)，空间复杂度：O(m×n)func multiplyByAddition(num1 string, num2 string) string {if num1 == \"0\" || num2 == \"0\" {return \"0\"}result := \"0\"// 逐位相乘并累加for i := len(num2) - 1; i >= 0; i-- {digit := int(num2[i] - \'0\')// 计算 num1 × digittemp := multiplyByDigit(num1, digit)// 添加相应的零（位数偏移）zeros := len(num2) - 1 - ifor j := 0; j < zeros; j++ {temp += \"0\"}// 累加到结果result = addStrings(result, temp)}return result}// 辅助函数：数字字符串乘以单个数字func multiplyByDigit(num string, digit int) string {if digit == 0 {return \"0\"}result := make([]int, len(num)+1)carry := 0for i := len(num) - 1; i >= 0; i-- {product := int(num[i]-\'0\')*digit + carryresult[i+1] = product % 10carry = product / 10}result[0] = carry// 转换为字符串var sb strings.Builderstart := 0if result[0] == 0 {start = 1}for i := start; i < len(result); i++ {sb.WriteByte(byte(result[i] + \'0\'))}return sb.String()}// 辅助函数：字符串加法func addStrings(num1 string, num2 string) string {i, j := len(num1)-1, len(num2)-1carry := 0var result strings.Builderfor i >= 0 || j >= 0 || carry > 0 {sum := carryif i >= 0 {sum += int(num1[i] - \'0\')i--}if j >= 0 {sum += int(num2[j] - \'0\')j--}result.WriteByte(byte(sum%10 + \'0\'))carry = sum / 10}// 反转结果return reverseString(result.String())}// 辅助函数：反转字符串func reverseString(s string) string {runes := []rune(s)for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {runes[i], runes[j] = runes[j], runes[i]}return string(runes)}// 解法四：Karatsuba分治算法（适用于超大数）// 时间复杂度：O(n^1.585)，空间复杂度：O(log n)func multiplyKaratsuba(num1 string, num2 string) string {if num1 == \"0\" || num2 == \"0\" {return \"0\"}// 小数字直接计算if len(num1) <= 10 && len(num2) <= 10 {return multiply(num1, num2)}// 补齐到相同长度maxLen := max(len(num1), len(num2))if maxLen%2 == 1 {maxLen++}num1 = padLeft(num1, maxLen)num2 = padLeft(num2, maxLen)return karatsuba(num1, num2)}func karatsuba(x, y string) string {n := len(x)if n <= 10 {return multiply(x, y)}m := n / 2// 分割x1 := x[:n-m] // 高位x0 := x[n-m:] // 低位y1 := y[:n-m] // 高位y0 := y[n-m:] // 低位// 递归计算z0 := karatsuba(x0, y0)z2 := karatsuba(x1, y1)// 计算 (x1 + x0) * (y1 + y0)x1PlusX0 := addStrings(x1, x0)y1PlusY0 := addStrings(y1, y0)z1Temp := karatsuba(x1PlusX0, y1PlusY0)// z1 = z1Temp - z2 - z0z1 := subtractStrings(z1Temp, addStrings(z2, z0))// 组合结果: z2 * 10^(2m) + z1 * 10^m + z0result := addStrings(addStrings(multiplyByPowerOf10(z2, 2*m),multiplyByPowerOf10(z1, m)),z0)return removeLeadingZeros(result)}// 辅助函数：左填充零func padLeft(s string, length int) string {if len(s) >= length {return s}return strings.Repeat(\"0\", length-len(s)) + s}// 辅助函数：乘以10的幂func multiplyByPowerOf10(num string, power int) string {if num == \"0\" || power == 0 {return num}return num + strings.Repeat(\"0\", power)}// 辅助函数：字符串减法（假设num1 >= num2）func subtractStrings(num1, num2 string) string {if compareStrings(num1, num2) < 0 {return \"0\" // 简化处理，实际应该处理负数}i, j := len(num1)-1, len(num2)-1borrow := 0var result strings.Builderfor i >= 0 {diff := int(num1[i]-\'0\') - borrowif j >= 0 {diff -= int(num2[j] - \'0\')j--}if diff < 0 {diff += 10borrow = 1} else {borrow = 0}result.WriteByte(byte(diff + \'0\'))i--}return removeLeadingZeros(reverseString(result.String()))}// 辅助函数：比较两个数字字符串func compareStrings(num1, num2 string) int {if len(num1) != len(num2) {return len(num1) - len(num2)}return strings.Compare(num1, num2)}// 辅助函数：移除前导零func removeLeadingZeros(s string) string {i := 0for i < len(s) && s[i] == \'0\' {i++}if i == len(s) {return \"0\"}return s[i:]}// 辅助函数：取最大值func max(a, b int) int {if a > b {return a}return b}// 解法五：直接转换法（受整数范围限制，仅用于演示）func multiplyDirect(num1 string, num2 string) string {// 仅适用于小数字，受int64范围限制if len(num1) > 18 || len(num2) > 18 {return multiply(num1, num2) // 回退到模拟算法}n1, _ := strconv.ParseInt(num1, 10, 64)n2, _ := strconv.ParseInt(num2, 10, 64)return strconv.FormatInt(n1*n2, 10)}// 测试函数func testMultiply() {testCases := []struct {num1 stringnum2 stringexpected stringdesc string}{{\"2\", \"3\", \"6\", \"简单单位数相乘\"},{\"123\", \"456\", \"56088\", \"三位数相乘\"},{\"0\", \"123\", \"0\", \"零乘法\"},{\"999\", \"999\", \"998001\", \"最大单位数相乘\"},{\"12\", \"34\", \"408\", \"两位数相乘\"},{\"100\", \"200\", \"20000\", \"整百数相乘\"},{\"11\", \"11\", \"121\", \"相同数字相乘\"},{\"1\", \"123456789\", \"123456789\", \"乘以1\"},{\"999999999\", \"999999999\", \"999999998000000001\", \"九位数相乘\"},{\"12345\", \"67890\", \"838102050\", \"五位数相乘\"},{\"1000000\", \"2000000\", \"2000000000000\", \"大整数相乘\"},{\"98765\", \"43210\", \"4267635650\", \"随机数字\"},{\"777\", \"888\", \"689976\", \"重复数字\"},{\"505\", \"404\", \"204020\", \"包含零的数字\"},{\"99999\", \"99999\", \"9999800001\", \"五个9相乘\"},}fmt.Println(\"=== 字符串相乘测试 ===\\n\")for i, tc := range testCases {// 测试主要解法result1 := multiply(tc.num1, tc.num2)result2 := multiplyOptimized(tc.num1, tc.num2)result3 := multiplyByAddition(tc.num1, tc.num2)status := \"✅\"if result1 != tc.expected {status = \"❌\"}fmt.Printf(\"测试 %d: %s\\n\", i+1, tc.desc)fmt.Printf(\"输入: \\\"%s\\\" × \\\"%s\\\"\\n\", tc.num1, tc.num2)fmt.Printf(\"期望: %s\\n\", tc.expected)fmt.Printf(\"模拟法: %s\\n\", result1)fmt.Printf(\"优化法: %s\\n\", result2)fmt.Printf(\"加法法: %s\\n\", result3)fmt.Printf(\"结果: %s\\n\", status)fmt.Println(strings.Repeat(\"-\", 40))}}// 性能测试func benchmarkMultiply() {fmt.Println(\"\\n=== 性能测试 ===\\n\")// 构造测试数据testData := []struct {num1, num2 stringdesc string}{{generateNumber(10), generateNumber(10), \"10位×10位\"},{generateNumber(50), generateNumber(50), \"50位×50位\"},{generateNumber(100), generateNumber(100), \"100位×100位\"},{generateNumber(200), generateNumber(200), \"200位×200位\"},}algorithms := []struct {name stringfn func(string, string) string}{{\"模拟乘法\", multiply},{\"优化乘法\", multiplyOptimized},{\"Karatsuba\", multiplyKaratsuba},{\"加法组合\", multiplyByAddition},}for _, data := range testData {fmt.Printf(\"%s:\\n\", data.desc)for _, algo := range algorithms {start := time.Now()result := algo.fn(data.num1, data.num2)duration := time.Since(start)fmt.Printf(\" %s: 结果长度%d, 耗时: %v\\n\",algo.name, len(result), duration)}fmt.Println()}}// 生成指定长度的随机数字字符串func generateNumber(length int) string {if length <= 0 {return \"0\"}var sb strings.Buildersb.Grow(length)// 首位不能为0sb.WriteByte(byte(\'1\' + length%9))// 后续位可以是任意数字for i := 1; i < length; i++ {sb.WriteByte(byte(\'0\' + (i*7+3)%10))}return sb.String()}// 演示手算验证func demonstrateManualCalculation() {fmt.Println(\"\\n=== 手算过程演示 ===\")fmt.Println(\"计算 123 × 456:\")fmt.Println()fmt.Println(\" 123\")fmt.Println(\" × 456\")fmt.Println(\" -----\")fmt.Println(\" 738 (123 × 6)\")fmt.Println(\" 6150 (123 × 50)\")fmt.Println(\" 49200 (123 × 400)\")fmt.Println(\" -----\")fmt.Println(\" 56088\")fmt.Println()result := multiply(\"123\", \"456\")fmt.Printf(\"算法结果: %s\\n\", result)fmt.Printf(\"验证: %s\\n\", map[bool]string{true: \"✅ 正确\", false: \"❌ 错误\"}[result == \"56088\"])}func main() {fmt.Println(\"43. 字符串相乘 - 多种解法实现\")fmt.Println(\"========================================\")// 基础功能测试testMultiply()// 性能对比测试benchmarkMultiply()// 手算演示demonstrateManualCalculation()// 展示算法特点fmt.Println(\"\\n=== 算法特点分析 ===\")fmt.Println(\"1. 模拟乘法：经典解法，时间O(m×n)，推荐日常使用\")fmt.Println(\"2. 优化乘法：预处理优化，减少重复计算，性能略优\")fmt.Println(\"3. Karatsuba：分治算法，时间O(n^1.585)，适合超大数\")fmt.Println(\"4. 加法组合：思路直观，但效率较低O(m×n²)\")fmt.Println(\"5. 直接转换：受整数范围限制，仅适用小数字\")fmt.Println(\"\\n=== 关键技巧总结 ===\")fmt.Println(\"• 位置计算：num1[i]×num2[j] 结果放在 i+j+1 位置\")fmt.Println(\"• 进位处理：先累加同位置乘积，再统一处理进位\")fmt.Println(\"• 零值优化：任一数字为0时提前返回\")fmt.Println(\"• 前导零处理：结果构造时跳过前导零\")fmt.Println(\"• 容量预分配：StringBuilder预分配避免扩容\")}
