- 浏览: 173227 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 347There are n bulbs that are init ...
相关推荐
Multiply Strings Substring with Concatenation of All Words Pascal's Triangle Pascal's Triangle II Spiral Matrix Spiral Matrix II ZigZag Conversion Divide Two Integers Text Justification Max Points on ...
...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 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
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 ...
Multiply by shifting 224 Dividing by shifting 225 Rotating bits 226 Decimal Arithmetic 227 Unpacked BCD arithmetic 227 Packed BCD arithmetic 229 Logical Operations 231 Boolean logic 231 Bit testing ...
5)....Added: Improvements for call stack of dynarrays/strings allocations (leaks) 6)....Added: "Elem size" when reporting leaks in dynarrays 7)....Added: Streaming unpacked debug info into temporal ...
8.3 Fused Multiply-Add extension for VFP 8.4 Extension register bank mapping in VFP 8.5 VFP views of the extension register bank 8.6 Load values to VFP registers 8.7 Conditional execution of VFP ...
FASMARM v1.42 This package is an ARM assembler add-on for FASM. FASMARM currently supports the full range of instructions for 32-bit and 64-bit ARM processors and coprocessors up to and including v8...
2.1.5 Representing Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.1.6 Representing Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.1.7...