- 浏览: 184803 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
计算两个大数的乘法,如果直接计算,就会溢出。假设两个数的长度分别为m, n。那么它们相乘之后的长度肯定为m+n(有进位), 或m + n - 1(没有进位)。我们建立一个长度为m + n 的数组,用来求解每一位上对应的值,维护一个进位。代码如下:
Note: The numbers can be arbitrarily large and are non-negative.
计算两个大数的乘法,如果直接计算,就会溢出。假设两个数的长度分别为m, n。那么它们相乘之后的长度肯定为m+n(有进位), 或m + n - 1(没有进位)。我们建立一个长度为m + n 的数组,用来求解每一位上对应的值,维护一个进位。代码如下:
public class Solution { public String multiply(String num1, String num2) { if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) return ""; int[] digit = new int[num1.length() + num2.length()]; for (int i = num1.length() - 1; i >= 0; i--) { int a = num1.charAt(i) - '0'; for (int j = num2.length() - 1; j >= 0; j--) { int b = num2.charAt(j) - '0'; digit[i + j + 1] += a * b; } } StringBuilder sb = new StringBuilder(); for (int i = digit.length - 1; i > 0; i--) { int num = digit[i] % 10; int carry = digit[i] / 10; sb.append(num); digit[i - 1] += carry; } //检查最高位是否有进位,如果有进位,将进位加入字符串中 if(digit[0] > 0) sb.append(digit[0]); /* 检查最后一位是否为0,如果为0说明字符串一定为一个 全0的序列。因为在上一步我们已经判断是否有进位,如 果为0说明没有进位,只有全为0的情况下,字符串倒数第 二位才可能为0 */ if(sb.charAt(sb.length() - 1) == '0') return "0"; return sb.reverse().toString(); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 270Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 271You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 389Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 379Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 503Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 568Merge k sorted linked lists and ... -
N-Queens II
2016-03-06 03:06 668Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 473The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 434Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 584Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 590Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 429All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 905Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 933Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 606Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 691Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 857Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 789You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 723For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 442There are n bulbs that are init ...
相关推荐
java java_leetcode题解之Multiply Strings.java
js js_leetcode题解之43-multiply-strings.js
c语言入门 C语言_leetcode题解之43-multiply-strings.c
在本压缩包中,主题聚焦于使用Python解决LeetCode第43题——“字符串相乘”(Multiply Strings)。这是一道常见的编程面试题,旨在测试应聘者的字符串处理和算法设计能力。下面将详细探讨该题目的背景、解题思路、...
第43题:字符串相乘(Multiply Strings) 题目描述: 给定两个非负整数num1和num2,它们的长度相同,用字符串形式表示。你的任务是计算它们的乘积,并返回结果字符串。例如,"2" 和 "3" 相乘等于 "6"。 解决方案:...
22. **Multiply Strings**:两个字符串表示的数相乘。同样模拟笔算乘法,使用二维数组存储中间结果。 23. **Rotate Array**:将数组顺时针旋转指定步数。可以先反转整个数组,再反转前半部分和后半部分。 24. **...
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
- Multiply Strings: 给定两个非负整数字符串形式的数,要求进行乘法运算。 - Wildcard Matching: 实现支持'?'和'*'的通配符匹配。 - Jump Game / Jump Game II: 第一个问题要求判断是否能到达数组的最后一个位置,...
Multiply Strings 066 Add Binary Linked-list 002 Add Two Numbers Stack 020 Valid Parenthesis Hash Table 001 TwoSum Reference 完整的学习流程 How to be a softwair engineer: 其他人详解 Python的各式演算法
leetcode卡 LeetCode LeetCode题解 目录 字符串问题 ID Title C++ 难度 备注 0008 String to Integer(atoi) :star: :star: :star: ...Multiply Strings :star: :star: 大数相乘 0044 Wild Card Matchi
<<<<<<< HEAD#周三9/16的概述 回顾昨天,去做功课 介绍数组 在课堂练习中(成对) ...//1....//2....//3.... Add, subtract, multiply and divide them. ... Add, subtract, multiply and divide the strings
filtered_strings = list(filter(is_not_empty, strings)) print(filtered_strings) ``` 输出结果为:`['hello', 'world', 'Python']` 通过上述示例可以看出,`map()`、`reduce()` 和 `filter()` 这三个内置函数在...
filtered_strings = filter(not_empty, strings) # 输出结果:['abc', 'def', 'ghi'] ``` 综上所述,`map()`, `reduce()`和`filter()`是Python中非常实用的高阶函数,它们简化了对列表数据的操作,提高了代码的...
Multiply two numbers without using arithmetic operators Chapter 13. Compute the two’s complement for a given integer Chapter 14. Isolate the rightmost bit set to 1 Chapter 15. Create a mask for ...
- `strings.xml`:用于定义界面上显示的文本字符串。 2. **设计用户界面**: - 在`main.xml`中定义应用的用户界面布局。 - 示例代码如下所示: ```xml android:orientation="vertical" android:layout_...
对于计算逻辑,源码可能包含了多个函数,如`add()`, `subtract()`, `multiply()`, `divide()`,分别对应加减乘除运算。 此外,Android应用的生命周期管理也是一个关键知识点。在这个计算器中,你需要了解如何在...
- `multiply(Complex other)`:实现复数相乘 - `divide(Complex other)`:实现复数相除 - `toString()`:将复数格式化为字符串 #### 三、整数数组转字符串 编写一个方法,接受一个整数数组作为参数,然后将数组中...