Leetcode1 Interesting Numbers (Basics-Part 1)

Leetcode1 Interesting Numbers (Basics-Part 1)

1. Armstrong number

1.armStrong.py:

#!/usr/bin/python # Env: python3 # Rewrite by afei_0and1 ''' 1. Suppose there is a k-digit number N, and the sum of the k powers of the numbers on each digit is also N, then this number is the Armstrong number. Now give you a positive integer N, let you determine whether this number is an Armstrong number, if it is, return True, if not, return False. EG: 153 is a 3-digit number, and: 153=1^3+5^3+3^3 Armstrong number is actually a self-power number, and the three-digit Armstrong number is also called the daffodil number. The name of the number of daffodils comes from a poignant fairy tale. The beautiful young Narcissus struggled to pursue his reflection and finally turned into a crystal clear daffodil. After that, the name of Narcissus (NARCISSUS) became synonymous with "self-appreciation". The number of daffodils to refer to the three-digit self-power number may have some description of the taste of "self-appreciation". Interesting powers: The power of one digit is also called the single number; The three-digit self-violence number is also called the daffodil number; The four-digit power number is also called the four-leaf rose number; The five-digit self-power number is also called the five-pointed star number; The power of six digits is also called the six-digit number; The power number of seven digits is also called the Big Dipper number; The power number of eight digits is also called the eight cents number; The self-power number of nine digits is also called Jiujiu Chongyang number; The power of tens is also called the perfect number. Problem-solving ideas: (1) First extract each digit in a number; (2) Perform exponential operation and accumulate each extracted digit with the digit of the current number itself; (3) In the end, compare whether the accumulated result is the same as the number itself. ''' def armStrong ( N ): tmp = N list = [] while tmp/10.0 > 0 : #take one digit s = tmp% 10 list .append(s) tmp = tmp//10 sum = 0 for item in list : sum += item** len ( list ) #print(item**len(list)) if sum == N: return True else : return False res = armStrong( 153 ) print (res) ''' Output result: True ''' #Program optimization def armStrong2 ( N ): strN = str (N) list = [] for item in strN: list .append(item) sum = 0 for item in list : sum += int (item) ** len ( list ) return sum == N res = armStrong2( 100 ) print (res) ''' Output result: False ''' #Program optimization 2 def armStrong3 ( N ): l = list ( str (N)) sum = 0 for item in l: sum = int (item) ** len (l) return sum == N res = armStrong2( 153 ) print (res) ''' Output result: True ''' Copy code

2. Self-divisor

2.self-Divisor.py:

#!/usr/bin/python # Env: python3 # Rewrite by afei_0and1 ''' 2. The self-divisor refers to the number that can be divided by every digit it contains, and it can also be understood as the self-division pair constitutes its own The remainder operation is performed on each digit, and the result is 0. Note: The self-division number is not allowed to contain 0. Such as: 128 is a self-divisor, Because: 128% 1 == 0, 128% 2 == 0, 128% 8 == 0. Now, given the numbers of the upper boundary and the lower boundary, output a list, the elements of the list are all within the boundary (including the boundary) The divisor of. Please try to solve it. ''' def selfDivisor ( left, right ): l = [] for num in range (left, right+ 1 ): numStr = str (num) numList = list (numStr) res = True for item in numList: itemNum = int (item) #Remove the case where the self-divisor is 0 if itemNum == 0 : res = False break #Remove situations that cannot be completely divisible by itself if num% itemNum != 0 : res = False #Add the self-divisor to the list if res: l.append(num) return l print (selfDivisor( 100 , 200 )) ''' Output result: [111, 112, 115, 122, 124, 126, 128, 132, 135, 144, 155, 162, 168, 175, 184] ''' #Program optimization 1 def selfDivisor2 ( left, right ): l = [num for num in range (left, right + 1 ) if ([item for item in list ( str (num)) if ( int (item) != 0 and num% int (item) == 0 )] == list ( str (num)))] return l print (selfDivisor2( 128 , 201 )) ''' Output result: [128, 132, 135, 144, 155, 162, 168, 175, 184] ''' Copy code

3. Perfect square number

3.entire-SquareNumber.py:

#!/usr/bin/python # Env: python3 # Rewrite by afei_0and1 ''' 3. The perfect square number has the characteristic: if a positive integer A is the square of a certain integer B, then this positive integer A is called a perfect square number, and zero can also be called a perfect square number. Then: Given a positive integer N, find several perfect squares so that their sum is equal to N, you need to determine the minimum number of perfect squares that make up the sum. For example: for a positive integer 13, it can be broken down to 13=4+9, and the minimum number is 2. For a positive integer 12, it can be broken down to 12=4+4+4, and the minimum number is 3. The problem needs to be used: the four-square number sum theorem The Sum of 4.Squares Theorem is also called Lagrange's Theorem of Sum of 4.Squares, which is finally solved by Lagrange. The theorem of the sum of four squares can prove: any positive integer can be expressed as the sum of squares of four integers (in which an integer is allowed to be 0). According to the four-square number sum theorem: 13 = 4 + 9 + 0 + 0 12 = 4 + 4 + 4 + 0 From the theorem, it can be seen that the number of perfect square numbers that compose this positive integer N is at most four. The inference of the sum of four squares theorem: If a number N can only be represented by the sum of 4 non-zero perfect square numbers, then this number N must satisfy: 4^A(8B+7) Problem-solving algorithm ideas: (1) First suppose that the number of perfect square numbers composing this number N is at least 4, then the number N must satisfy: N=4^A(8B+7), First judge this equation, if it passes, the final answer is 4, otherwise continue the algorithm; (2) Assuming that the number of perfect square numbers composing the number N is at least 1, the number N can be expressed as the square of a positive integer, Perform traversal, if you cannot find the algorithm (3) Assuming that the number of complete squares that make up this number N is at least 2, and using loop nesting to traverse, no continuation algorithm can be found; (4) At this point in the algorithm execution, the final answer is 3. ''' def entireSquareNumber ( N ): num = N #Judge whether it is a multiple of 4 while num% 4 == 0 : #Judge whether it is satisfied: 4^A(8B+7) num = num/4 if num% 8 == 7 : return 4 for i in range ( 1 , N + 1 ): if i * i == N: return 1 for i in range ( 1 , N + 1 ): for j in range ( 1 , N + 1): if i * i + j * j == N: return 2 return 3 print (entireSquareNumber( 100 )) ''' Output result: 1 ''' ''' If the given value of N is very large, the program will be very slow due to multiple cycles and exponentiation operations. ''' #Program optimization import math def entireSquareNumber2 ( N ): num = N while num% 4 == 0 : num = num/4 if num% 8 == 7 : return 4 #Import math library, math.sqrt() square root operation, math.pow() power operation if math. pow ( int (math.sqrt(N)) , 2 ) == N: return 1 max = int (math.sqrt(N)) + 1 for i in range ( 1 , max ): tmp = N-i * i if math. pow ( int (math.sqrt(tmp)), 2 ) == tmp: return 2 return 3 print (entireSquareNumber2( 7000 )) ''' Output result: 3 ''' Copy code

4. Strong integer

4.strongInteger.py:

#!/usr/bin/python # Env: python3 # Rewrite by afei_0and1 ''' Strong integer has such a definition, given two positive integers X and Y, if a certain integer is equal to X^I+Y^J, Wherein the integer I>=0 and J>=0, then we consider the integer to be a strong integer. Now, enter X and Y, and given an upper boundary N, try to programmatically find all strong integers less than or equal to N, and return them in the form of a list. ''' import math def strongInteher ( x, y, bounds ): l = [] for i in range ( 0 , bounds + 1 ): # the case where x^i is greater than bounds if math. pow (x, i)> bounds: break for j in range ( 0 , bounds + 1 ): res = math. pow (x, i) + math. pow (y, j) if res <= bounds: if int (res) not in l: l.append( int (res)) else : if x == 1 : return l else : break return l print (strongInteher( 2 , 3 , 20 )) ''' Output result: [2, 4, 10, 3, 5, 11, 9, 17, 19] ''' ''' Program optimization: (1) Use tuples; (2) Use the stack structure ''' def strongInteher2 ( x, y, bounds ): l = [] stack = [( 0 , 0 )] while len (stack)> 0 : #Get an element in the list, the default is the last element tmp = stack.pop() res = math. pow (x, tmp[ 0 ]) + math. pow (y, tmp[ 1 ]) if res <= bounds: if int (res) not in l: l.append( int (res)) # res>bounds case if x != 1 : stack.append((tmp[ 0 ] + 1 , tmp[ 1 ])) if y != 0 : stack.append((tmp[ 0 ], tmp[ 1 ] + 1 )) return l print (strongInteher2( 2 , 3 , 22 )) ''' Output result: [2, 4, 10, 11, 13, 17, 5, 7, 19, 3, 9] ''' Copy code

5. Number of palindrome

5.palindromicNumber.py:

#!/usr/bin/python # Env: python3 # Rewrite by afei_0and1 ''' 5. "Palindrome" means that a sentence can be read through both positive and negative readings. There is also such a type of number in mathematics that has such characteristics. This is called the "palindrome number". The palindrome number refers to the same integer in both positive order (from left to right) and reverse order (from right to left). Now it is required to enter an integer N to determine whether it is a palindrome. Problem-solving ideas: Convert the input number into a list, and judge whether it is a palindrome by the reverse order of the list. ''' def palindromicNumber ( N ): list1 = list ( str (N)) list2 = list ( str (N)) list2.reverse() return list1 == list2 print (palindromicNumber( 121 )) ''' Output result: True ''' ''' Program optimization: Use slices to reduce the amount of code ''' def palindromicNumber2 ( N ): # -1 represents from right to left, the second represents the step length return str (N) == str (N)[::- 1 ] print (palindromicNumber2( 112111 )) ''' Output result: False ''' Copy code

More articles: afei00123.blog.csdn.net/