43. String multiplication
Given two non-negative integers that are represented as strings,
num2, return the product of
num2, which is also represented as a string.
Input: num1 = “2”, num2 = “3”
Input: num1 = “123”, num2 = “456”
num2 have lengths less than 110.
num2 only contain the Numbers
num2 do not begin with zero, unless it is the number 0 itself. cannot be processed using any of the standard library’s large number types (such as BigInteger) or by converting the input directly to an integer.
So this isn’t a very difficult problem, but if you just do the regular multiplication, you can figure it out. Figure below:
The basic idea is as follows:
(1) can first flip the string, that is, start from the low order calculation.
(2) use an array to maintain the final result, updating it every time you multiply it, but pay attention to the carry case () pay attention to the two points, the same bit to add the carry, from low to high multiplication is carried. )
(3) finally, the
0 in front of the array is discarded and converted to string output.
# @Time :2018/08/05 # @Author :LiuYinxing # String Num class Solution: def multiply(self, num1, num2): res =  * (len(num1) + len(num2)) # Initialization, array to hold the product. pos = len(res) - 1 for n1 in reversed(num1): tempPos = pos for n2 in reversed(num2): res[tempPos] += int(n1) * int(n2) res[tempPos - 1] += res[tempPos] // 10 # Offset res[tempPos] %= 10 # fractional remainder tempPos -= 1 pos -= 1 st = 0 while st < len(res) - 1 and res[st] == 0: # How many zeros are in front of a statistic? st += 1 return ''.join(map(str, res[st:])) # Remove the 0, then turn it into a string, and return if __name__ == '__main__': num1, num2 = "123", "456" solu = Solution() print(solu.multiply(num1, num2))
Welcome to correct me.
- Python Time Module timestamp, Time string formatting and Conversion (13-bit timestamp)
- Python: RNN principle realized by numpy
- [How to Fix] TypeError: Cannot cast array data from dtype(‘float64‘) to dtype(‘＜U32‘)….
- can‘t multiply sequence by non-int of type ‘numpy.float64‘
- The Usage of Np.random.uniform()
- Python 3.X error: valueerror: data type must provide an itemsize
- Python: How to Set Line breaks and tabs for Strings
- Python: leetcode 1672. Richest Customer Wealth
- Python Valueerror: cannot index with vector containing Na / Nan values
- CV: How to extracts the part of the picture with the specified color
- [resolution] str.contains() problem] valueerror: cannot index with vector containing Na/Nan values
- Python ValueError: only 2 non-keyword arguments accepted
- python: File Processing and Input and Output
- ValueError: Found array with dim 4. Estimator expected and ValueError: Expected 2D array, got 1D array i
- Python algorithm for “anagram” judgment problem
- Python+ Pandas + Evaluation of Music Equipment over the years (Notes)
- Tips for Python 3 string.punctuation
- Python: How to Processe “return multiple values”
- Django Issues: TypeError: “Settings” object is irreversible
- Full explanation of SYS module of Python