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()
- Error:output with shape [1, 224, 224] doesn‘t match the broadcast shape [3, 224, 224]
- Python 3.X error: valueerror: data type must provide an itemsize
- [ONNXRuntimeError] : 10 : INVALID_Graph loading model error
- Pandas Error: ValueError: setting an array element with a sequence.
- [Solved] python-sutime Error: the JSON object must be str, bytes or bytearray, not ‘java.lang.String‘
- Python: How to Set Line breaks and tabs for Strings
- Python: leetcode 1672. Richest Customer Wealth
- CV: How to extracts the part of the picture with the specified color
- Python Valueerror: cannot index with vector containing Na / Nan values
- [Solved] TypeError: not all arguments converted during string formatting
- [resolution] str.contains() problem] valueerror: cannot index with vector containing Na/Nan values
- For the problem of rejecting old usage errors after numpy is updated, modified in numpy 1.20; for more details and guidance
- 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