8, Mathematics
204. Count prime
Count the number of all prime numbers less than non negative integer n.
Example:
input: 10 output: 4 explain: There are four prime numbers less than 10, They are two, 3, 5, 7 .
Idea: this problem needs to consider optimization in order to make the algorithm efficient. Using the eratoseni sieve method, first of all, it does not need to traverse from 2 to N, but only from 2 to sqrt(n). If no divisible factor is found in this interval, it can be directly concluded that n is a prime number. In addition, the multiple of each prime number must not be a prime number and can also be excluded. What remains after exclusion is a prime number. Recommend this article: https://leetcode-cn.com/problems/count-primes/solution/ru-he-gao-xiao-pan-ding-shai-xuan-su-shu-by-labula/
Code implementation:
class Solution:
def countPrimes(self, n: int) -> int:
isPrime = [True] * n
for i in range(2,int(n**0.5)+1):
if isPrime[i]:
# The multiple of i can't be prime
for j in range(i*i, n, i):
isPrime[j] = False
count = 0
for i in range(2,n):
if isPrime[i]:
count += 1
return count
Maximum common divisor and minimum common multiple
Code implementation:
# greatest common divisor:
def gcd(a,b):
for i in range(1, min(a,b)+1):
if a % i == 0 and b % i == 0:
gcd = i
return gcd
print(gcd(8,10))
# Least common multiple
def lcm(a,b):
g = gcd(a,b)
return a*b//g
print(lcm(8,6))
Solving the greatest common divisor using bit manipulation and subtraction
Idea: for the maximum common divisor f(a, b) of a and B, there are:
If a and b Even numbers, f(a, b) = 2*f(a/2, b/2); If a It's an even number b It's odd, f(a, b) = f(a/2, b); If b It's an even number a It's odd, f(a, b) = f(a, b/2); If a and b Are odd, f(a, b) = f(b, a-b);
Both multiply by 2 and divide by 2 can be converted to shift operations.
Code implementation:
# Solving the greatest common divisor using bit manipulation and subtraction
def gcd(a,b):
if a < b:
return gcd(b,a) # Ensure that the first number is not less than the second number
if b == 0:
return a
def is_even(x):
return True if x % 2 == 0 else False
aeven = is_even(a)
beven = is_even(b)
if aeven and beven:
return 2 * gcd(a >> 1, b >> 1) # Moving one bit to the right is equivalent to dividing by 2
elif aeven and not beven:
return gcd(a >> 1, b)
elif not aeven and beven:
return gcd(a, b >> 1)
elif not aeven and not beven:
return gcd(b, a-b)
365. Kettle problem
There are two kettles with capacity of x liters and y liters, and unlimited water. Please judge whether you can get exactly z liters of water by using these two kettles?
If you can, please use one or two of the above kettles to hold the z liters of water.
You allow:
Fill any kettle Empty any kettle Pour water from one kettle to another until it is full or empty
Example 1: (from the fame "Die Hard" example)
input: x = 3, y = 5, z = 4 output: True
Example 2:
input: x = 2, y = 6, z = 5 output: False
Idea: this problem can be transformed into a pure mathematical problem, which requires peishu theorem: if a and B are integers and the maximum common divisor of a and B is d, then for any integer x,y, ax+by, it must be a multiple of d. in particular, there must be integers x and y, so that ax+by=d holds. For the bucket operation, each operation will only increase the total amount of water in the bucket by X, increase y, reduce x, or reduce y. You may think this is a problem: what if you put water into a dissatisfied bucket or empty it? Isn't that X or Y? Next, let's explain this:
First of all, it should be clear that under the operation given in the title, two buckets cannot have water and be dissatisfied at the same time. Because observing the operation in all subjects, the result of the operation is that at least one bucket is empty or full; Second, there is no point in adding water to a dissatisfied bucket. Because if another bucket is empty, the result of this operation is equivalent to filling the bucket with water directly from the initial state; If the other bucket is full, the result of this operation is equivalent to filling the two buckets respectively from the initial state; Thirdly, it is meaningless to pour out the water in a dissatisfied bucket. Because if the other bucket is empty, the result of this operation is equivalent to returning to the initial state; If the other bucket is full, the result of this operation is equivalent to filling the other bucket directly from the initial state.
Therefore, we can think that each operation will only bring X or Y changes to the total amount of feed water. Therefore, our goal can be rewritten as: find a pair of integers a and B so that: ax + by = z. as long as z < = x + y is satisfied and such a and B exist, our goal can be achieved. Here a and B can be regarded as the operation of two buckets. Peishu theorem tells us that ax + by = z is solvable if and only if z is a multiple of the greatest common divisor of X and y. So we just need to find the greatest common divisor of X and Y and judge whether z is a multiple of it.
For example: when x = 3, y = 5, z = 5, we need 8 steps: (1) fill x (x has 3L); (2) Pour x to y (x is empty, y has 3L); (3) Fill up x (x has 3l, y has 3L); (4) Pour x to y (x has 1L, y has 5L); (5) Empty y (x has 1L, y is empty); (6) Pour x to y (x is empty, y has 1L); (7) Have 3x, full (L); (8) Pour x to y (x is empty, y has 4L) to complete! Among the eight steps, three steps are to fill X and one step is to empty y. The three steps and one step here correspond to a and b in ax + by = z, which is equivalent to 3x + (-1)y = 3 * 3 + (-1) * 5 = 4.
Code implementation:
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if x + y < z:
return False
if x == 0 or y == 0:
return x+y == z or z == 0
return z % math.gcd(x,y) == 0
Binary conversion
504. Hex number
Given an integer, convert it to 7-ARY and output it as a string.
Example 1:
input: 100 output: "202"
Example 2:
input: -7 output: "-10"
Note: the input range is [- 1e7, 1e7].
Idea: use the short division method, divide by 7 each time, and output the remainder on the right backwards, which is the converted hex number. When num is negative, its hex number is the hex number corresponding to the absolute value of num, and add a negative sign in front of it. For example, the hex number of 8 is 11, and the hex number of - 8 is - 11.
Code implementation:
class Solution:
def convertToBase7(self, num: int) -> str:
flag = False
if num < 0:
num = -num
flag = True
res = ""
while num >= 7:
res += str(num % 7)
num //= 7
res += str(num)
if flag:
res += '-'
return res[::-1]
405. Conversion of numbers to hexadecimal numbers
Given an integer, write an algorithm to convert this number into hexadecimal number. For negative integers, we usually use complement operation.
be careful:
All letters in hexadecimal(a-f)Must be lowercase. Hexadecimal strings cannot contain extra leading zeros. If the number to be converted is 0, it is converted as a single character'0'To express; For other cases, the first character in the hexadecimal string will not be the 0 character. The given number is guaranteed to be in the range of 32-bit signed integers. You cannot use any method provided by the library to convert or format numbers directly to hexadecimal.
Example 1:
input: 26 output: "1a"
Example 2:
input: -1 output: "ffffffff"
Idea: use the short division method to store the characters corresponding to hexadecimal in the dictionary. It should be noted that when num is negative, the complement operation is adopted. In fact, the complement operation uses the maximum allowable number of calculation digits as the upper limit, and modulus operation will be carried out if it exceeds it. The complement operation of negative number is equivalent to using the maximum value, 4294967296 plus num, and then normal hexadecimal conversion. 4294967296 here is the 32nd power of 2. Because there are 16 numbers in hexadecimal, four bits are required to represent hexadecimal in the computer (2 ^ 4 = 16). The topic gives us an int type number num, an int = 4 bytes = 32 bits, so the maximum value is the 32nd power of 2.
Code implementation:
class Solution:
def toHex(self, num: int) -> str:
if num < 0:
# If num < 0, complement operation is carried out. In fact, complement operation takes the maximum allowable number of calculated digits as the upper limit, and modulus operation is carried out if it exceeds it,
# The complement operation of negative numbers is equivalent to using the maximum value, 4294967296 plus num, and then performing normal hexadecimal conversion
num += 2**32
if num == 0:
return '0'
res = ""
hash = {0:'0', 1:'1', 2:'2', 3:'3', 4:'4', 5:'5', 6:'6', 7:'7', 8:'8', 9:'9',
10:'a', 11:'b', 12:'c', 13:'d', 14:'e', 15:'f'}
while num != 0:
res += hash[num % 16]
num //= 16
return res[::-1]
168. Excel table column name
Given a positive integer, return its corresponding column name in the Excel table.
For example,
1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ...
Example 1:
input: 1 output: "A"
Example 2:
input: 28 output: "AB"
Example 3:
input: 701 output: "ZY"
Idea: this question is actually from decimal to 26. When n=26, use the short division, quotient 1 is more than 0, and at this time, the remainder 0 has no corresponding letter, so you can borrow a digit from the quotient to give the remainder, which is expressed as quotient 0 more than 26, so n=26 is expressed as the letter 'Z'.
Code implementation:
class Solution:
def convertToTitle(self, n: int) -> str:
res = ""
while n:
n, y = divmod(n, 26) # Returns a tuple containing quotient and remainder (A / / B, a% B)
if y == 0:
n -= 1
y = 26
res = chr(y + 64) + res # Convert to uppercase letters corresponding to ASCII code
return res
172. Zero after factorial
Given an integer n, return n! The number of zeros in the mantissa of the result.
Example 1:
input: 3 output: 0 explain: 3! = 6, There is no zero in the mantissa.
Example 2:
input: 5 output: 1 explain: 5! = 120, 1 zero in mantissa.
Note: the time complexity of your algorithm should be O(log n).
Idea: for example, factorial of 11:
11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
= 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1
Observation rule: for the factor containing 2, it is 1 * 2, 2 * 2, 3 * 2, 4 * 2; For a factor containing 5, it is 1 * 5, 2 * 5; The factor containing 2 appears once every two, and the factor containing 5 appears once every five. The number of all 2 appears far more than 5. In other words, if you find a 5, you can find a 2 to match it. So we just need to find how many 5. Directly, we only need to judge how many factors of 5 are there in each cumulative multiplication. In addition, every 25 numbers, there are two 5's, so in addition to counting every 5 numbers as a 5, every 25 numbers, you also need to count an additional 5. That is, we need to add n / 25 5. Similarly, we will also find that every 5 * 5 * 5 = 125 numbers, there will be 3 5, so we need to add n / 125. To sum up, the rule is that every five numbers, there is a 5, every 25 numbers, there are two 5, every 125 numbers, there are three 5... And so on. The final number of 5 is:
n / 5 + n / 25 + n / 125 ... = n / (5^1) + n / (5^2) + n / (5^3) ...
If you write a program, if you calculate directly according to the formula above, the denominator may cause overflow. So when calculating n / 25, let's update n first, n = n / 5, and then calculate n / 5. The same applies to the back.
Code implementation:
class Solution:
def trailingZeroes(self, n: int) -> int:
count = 0
while n > 0:
count = count + n//5
n = n // 5
return count
String addition and subtraction
67. Binary summation
Give you two binary strings and return their sum (expressed in binary).
The input is a non empty string and contains only the numbers 1 and 0.
Example 1:
input: a = "11", b = "1" output: "100"
Example 2:
input: a = "1010", b = "1011" output: "10101"
Tips:
Each string consists of only characters '0' or '1' form. 1 <= a.length, b.length <= 10^4 String if not "0" ，Without leading zeros.
Idea: use Python built-in functions.
dec = input('10 The hexadecimal number is:')
print("Convert to binary:", bin(dec))
print("Convert to octal:", oct(dec))
print("Convert to hex:", hex(dec))
string1 = '101010'
print('Convert binary string to decimal number:'，int(string1,2))
string1 = '367'
print('Convert octal string to decimal number:'，int(string1,8))
string3 = 'FFF'
print('Convert hexadecimal string to decimal number:'，int(string1,16))
Bit operation method: Step 1: complete binary bits. Step 2: A ^ b. Step 3: (A & b) < 1. Step 4: treat a ^ b calculated in step 2 as a new a, treat (A & b) < 1 calculated in step 3 as a new b, and repeat step 2 and step 3 until b is 0000 0000. At this time, the value of a is the answer. Recommend this article: https://leetcode-cn.com/problems/add-binary/solution/guan-fang-ti-jie-fang-fa-er-xiang-jie-bu-shi-yong-/
Bit operation related operations: the binary representation of 8 is 0000 1000, and the binary representation of - 8 is the complement of 0000 1000. The calculated complement is + 1 after the inverse of the original code, so the binary representation of - 8 is 1111 1000. Shifting binary by 1 bit to the left is equivalent to multiplying 2 (rounding up), and shifting binary by 2 bits to the left is equivalent to multiplying 2 square (rounding up); Shifting 1 bit to the right is equivalent to dividing by 2 (rounding down), shifting 2 bits to the right is equivalent to dividing by the square of 2 (rounding down)... And so on.
Code implementation:
# Built in functions:
class Solution:
def addBinary(self, a: str, b: str) -> str:
a = int(a,2) # Binary to decimal: int(str,2)
b = int(b,2)
res = bin(a + b) # STR to bin
return res[2:]
# Bit operation: class Solution: def addBinary(self, a: str, b: str) -> str: x, y = int(a,2), int(b,2) while y != 0 : ans = x^y carry = (x&y) << 1 x, y = ans, carry return bin(x)[2:]
415. String addition
Given two non negative integers num1 and num2 in string form, calculate their sum.
be careful:
num1 and num2 The length of is less than 5100. num1 and num2 All contain only the number 0-9. num1 and num2 Does not contain any leading zeros. You cannot use any built-in BigInteger Library, and you can't directly convert the input string to integer form.
Idea: use the double pointer to traverse forward from the tail of two strings to simulate the manual column vertical addition. If there is no bit, it will be added to 0. temp // 10 calculates whether to carry. When jumping out of the loop, if carry = 0, there is no need to add "1" at the beginning; If carry = 1, add "1" at the beginning.
Code implementation:
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
res = ""
i, j, carry = len(num1)-1, len(num2)-1, 0
while i >= 0 or j >= 0:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
temp = n1 + n2 + carry
carry = temp // 10
res = str(temp % 10) + res
i -= 1
j -= 1
return "1" + res if carry else res
462. Minimum number of moves to make array elements equal II
Given a non empty integer array, find the minimum number of moves required to make all array elements equal, where each move can add or subtract 1 from the selected element. You can assume that the length of the array is up to 10000.
For example:
input: [1,2,3] output: 2 explain: Only two actions are necessary (remember that each step can only add or subtract 1 from one of the elements): [1,2,3] => [2,2,3] => [2,2,2]
Idea: first, sort the array and define two pointers i and j, pointing to the head and tail of the array respectively; The variable count represents the number of moves and is initialized to 0; Define that the pointer mid points to the middle element of the array, mid = (i+j) // 2; When i < = mid, traverse the entire array by moving pointers i and j, and add the absolute value of the difference between the two numbers to count each time; When i > mid, the entire array has been completely traversed. You can end the loop and return count.
Code implementation:
class Solution:
def minMoves2(self, nums: List[int]) -> int:
nums.sort()
i, j = 0, len(nums)-1
mid = (i+j) // 2
count = 0
while i <= mid:
count += abs(nums[i] - nums[mid])
count += abs(nums[j] - nums[mid])
i += 1
j -= 1
return count
169. Most elements
Given an array of size n, find most of its elements. Most elements refer to elements that appear more than ⌊ n/2 ⌋ in the array.
You can assume that the array is non empty and that there are always many elements in a given array.
Example 1:
input: [3,2,3] output: 3
Example 2:
input: [2,2,1,1,1,2,2] output: 2
Idea: use collections Counter() to save the number of occurrences of each number in nums. In the hash table, sort each value of the hash table in reverse order, dict = sorted(dict.items(),key=lambda item:item[1], reverse=True), and finally output dict[0][0].
Code implementation:
from collections import Counter
class Solution:
def majorityElement(self, nums: List[int]) -> int:
dict = Counter(nums)
dict = sorted(dict.items(),key=lambda item:item[1], reverse=True)
return dict[0][0]
367. Effective complete square
Given a positive integer num, write a function. If num is a complete square number, it returns True, otherwise it returns False.
Note: do not use any built-in library functions, such as sqrt.
Example 1:
Input: 16 Output: True
Example 2:
Input: 14 Output: False
Idea: Method 1: convert num**0.5 into an integer to see whether the square of this integer is equal to the original num.
Method 2: the complete square number 1,4,9,16... The difference between each of them is 3,5,7... It is an equal difference sequence with a difference of 2, that is, 16-7-5-3-1 = 0. Control a cycle. When num > 0, each cycle num -= k, K is initialized to 1, and each cycle k += 2. When exiting the cycle, if num == 0, Num is a complete square, otherwise it is not a complete square.
Code implementation:
class Solution:
def isPerfectSquare(self, num: int) -> bool:
# sq = int(num ** 0.5)
# if sq ** 2 == num:
# return True
# else:
# return False
k = 1
while num > 0:
num -= k
k += 2
return num == 0
326. Power of 3
Given an integer, write a function to determine whether it is a power of 3.
Example 1:
input: 27 output: true
Example 2:
input: 0 output: false
Example 3:
input: 9 output: true
Example 4:
input: 45 output: false
Advanced:
Can you complete the problem without using loops or recursion?
Idea: if n is the power of 3, the remainder of dividing by 3 should be 0 every time until it becomes 1, 1 divided by 3, quotient 0 is more than 1, and finally judge whether n is 1. Note that when n < = 0, it returns False directly.
Code implementation:
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n <= 0:
return False
while n % 3 == 0:
n = n // 3
return n == 1
238. Product of arrays other than itself
Give you an integer array nums with length N, where n > 1, and return the output array output, where output[i] is equal to the product of other elements in nums except nums[i].
Example:
input: [1,2,3,4] output: [24,12,8,6] Tip: the title data ensures that the product of all prefix elements and suffixes (even the whole array) of any element in the array is within the range of 32-bit integers. explain: Please do not use division, and O(n) Complete the problem within the time complexity.
Advanced:
Can you complete this problem in constant space complexity? (for the purpose of spatial complexity analysis, the output array is not considered as additional space.)
Idea: because division is not allowed in this question, you can use two lists pre_li, post_li store the prefix element product and suffix element product of num [i] respectively, because the product other than num [i] is multiplied from the first element to num [I-1], then multiplied by num [i + 1] to the last element, and finally multiply the two lists to obtain the result. The spatial complexity of this method is O(N). The space complexity can be optimized here, because the title says that the output array is not regarded as additional space, so pre can be used_ Li is placed in the output array at the beginning, and then a pointer post is used instead of post_li, post traverses from back to front, multiplying by the corresponding position of the output array each time, and finally returning the output array. The space complexity of this method is: O(1).
Code implementation:
# Space complexity: O(N)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
pre_li = [1]
post_li = [1]
for i in range(1,len(nums)):
pre_li.append(nums[i-1] * pre_li[i-1])
nums.reverse()
for j in range(1,len(nums)):
post_li.append(nums[j-1] * post_li[j-1])
post_li.reverse()
for i in range(len(post_li)):
pre_li[i] *= post_li[i]
return pre_li
# Space complexity: O(1)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1]
post = 1
for i in range(1,len(nums)):
res.append(nums[i-1] * res[i-1])
for j in reversed(range(len(nums))):
res[j] *= post
post *= nums[j]
return res
628. Maximum product of three numbers
Given an integer array, find the maximum product of three numbers in the array and output the product.
Example 1:
input: [1,2,3] output: 6
Example 2:
input: [1,2,3,4] output: 24
be careful:
The length range of the given integer array is[3,104]，The range of all elements in the array is[-1000, 1000]. The product of any three numbers in the input array will not exceed the range of 32-bit signed integers.
Idea: first, sort the array. There are two situations that lead to the maximum product of three numbers: (1) there is no negative number in the array or the absolute value of the smallest two negative numbers is not as large as the absolute value of the largest positive number, then the three largest numbers of the product is the product of the last three numbers of the sorted array; (2) If there are negative numbers in the array and the absolute value of the smallest two negative numbers is greater than the absolute value of the largest positive number, the three largest numbers of the product are the product of the first two numbers (negative numbers) of the array after sorting, and then multiplied by the last number of the array.
Code implementation:
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
nums.sort()
res1 = nums[-1] * nums[-2] * nums[-3] # Product of the last three numbers
res2 = nums[0] * nums[1] * nums[-1] # Multiply the product of the first two numbers by the last number (the first two numbers are negative and the absolute value is the largest)
return max(res1, res2)
================================================================
The above is a summary of personal learning notes for reference and exchange. Reprint or commercial use is prohibited without permission.
- All the questions are from LeetCode's official website: https://leetcode-cn.com/
- Refer to this article for topic classification: https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E7%9B%AE%E5%BD%95.md