This is the 15th day of my participation in the First Challenge 2022

First, write first

I heard you’re still writing a two-layer for loop to solve the sum of two numbers?

LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!

LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher

LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!

Continue solving LeetCode, the longest public prefix

One of LeetCode’s “most classic” algorithm problems: the sum of three numbers

The sum of the nearest three numbers, wonderful

LeetCode: Valid parentheses

Delete duplicates in LeetCode: delete duplicates in LeetCode

The container that holds the most water is the container that holds the most water

Question 11: String multiplication, for the interview, looking forward to your participation.

Today’s topic

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, whose product is also represented as strings.

Note: (1) Num1 and num2 are shorter than 110 characters. (2) NUM1 and num2 contain only the numbers 0-9. (3) Num1 and num2 do not begin with a zero, except for the number 0 itself. (4) Do not use any library large number type (such as BigInteger) or directly convert the input to an integer for processing. Example:

Enter: num1 ="2", num2 = "3"Output:"6"Enter: num1 ="123", num2 = "456"Output:"56088"
Copy the code

Three, the analysis

Int STR, multiply STR, and convert STR to a string.

And then I came across this sentence: “Use the utility in the API is recommended in the project. But if you Use it in an interview, You will definitely fail.” If you think about it that way, you can’t get a job. If you think about it that way, you can’t get a job. If you think about it that way, you can’t get a job. Or we need to know at least some basic sorting algorithm before we can use it, otherwise, if you spend all your time shuffling, shuffling libraries, shuffling methods, you’re just going to end up losing everything.

Analysis of correct ideas:

Fourth, the problem solving

  • A shortcut:

Switch around switch around

class Solution(object) :
	def multiply(self, num1, num2) :
		""" :type num1: str :type num2: str :rtype: str """
		# str->int
		num1 = int(num1)
		num2 = int(num2)
		# quadrature
		result = num1*num2
		# int - > STR, return
		return str(result)
Copy the code
  • Submit the results

Test stats: 311 groups Running time: 28ms Beat percentage :98.89% This should be the best case scenario

  • Correct ideas

Time complexity: O(n^2)

class Solution(object) :
	def multiply(self, num1, num2) :
		""" :type num1: str :type num2: str :rtype: str """
		# set the storage list
		product = [0] * (len(num1) + len(num2))
		# subscript
		pos = len(product) - 1
		# string reversals to facilitate traversal from bits
		num1 = num1[::-1]
		num2 = num2[::-1]
		# Iterate over the multiplicator string
		for n1 in num1:
			# Data store location (order of magnitude, first one digit multiplication, last digit multiplication, second ten digit multiplication, penultimate second...)
			tempPos = pos
			# Iterate over the multiplier string
			for n2 in num2:
				Multiply single data
				product[tempPos] += int(n1) * int(n2)
				# take the order of tens or higher
				product[tempPos - 1] += product[tempPos] // 10
				# take bits
				product[tempPos] %= 10
				# forward
				tempPos -= 1
			# move forward, increase by an order of magnitude
			pos -= 1
		Find non-zero numbers in the result list
		pt = 0
		while pt < len(product) - 1 and product[pt] == 0:
			pt += 1
		# Slice out data
		res_list = product[pt:]
		# map is converted to an iterated object and returned with the jion function concatenation
		return ' '.join(map(str,res_list))
Copy the code
  • Submit the results

Test data: 311 groups running time: 308ms Beat percentage :28.81%

Although beat people are not many, but I have ideas, I am proud ~

Five, doubt

There are two aspects to this question: 1. 2. Inspect the operation and processing of data operation.

The above algorithm basically includes, and is also a method recommended by LeetCode English website.

Six, the concluding

Persistence and hard work: results.

Like to see the message forwarding, four support, the original is not easy. Ok, see you next time, I love the cat love technology, more love si si’s old cousin Da Mian ଘ(˙꒳˙)ଓ Di Di