2022-02-13 daily clock in: problem fine brush

Write in front

"After being proficient, these things may be as plain as drinking water, but they can bring great happiness to beginners. I always feel that whether we can always maintain the enthusiasm and concentration like beginners determines how far we can go and how good we can do something." This series of articles is written by python, and the topics are from three sources: those that have not been done before; Leetcode medium, difficult questions; Week Title Competition; A classic topic of a topic, all codes have been AC. 1-3 times a day, analyze according to the circumstances, and hope to be unimpeded, as a record of encouraging yourself to brush questions.

204. Count prime

Enumeration is no longer given. The biggest problem is that the correlation between numbers is not considered.

Let's first learn about the Egyptian sieve (eradosea sieve method):

• Considering that x is a prime number, its multiple 2x, 3x... Must not be a prime number.
• You can start marking directly from X ⋅ x, because 2x,3x... These numbers must have been marked by multiples of other numbers before x, such as all multiples of 2, all multiples of 3, etc.

class Solution:
    def countPrimes(self, n: int) -> int:
        # Check from 2 to n-1 (if it is less than or equal to n)
        isprime = [1 for i in range(0,n)]
        if len(isprime)<=1:
            return 0
        isprime[0]=isprime[1]=0
        for i in range(2,n):
            if isprime[i]:
                for j in range(i*i,n,i):
                    isprime[j]=0
        return sum(isprime)
        

[linear screen] is more advanced. In order to eliminate redundant operations in Egyptian screen:

• For example, 45 will be marked by 3 and 5 at the same time. We expect O ( n ) O(n) The complexity of O(n), that is, each number is determined only once. According to the basic theorem of arithmetic: "every composite number can be written as the product of prime numbers in a unique form". In other words, the product of multiple prime numbers can only form a unique composite number.
• No longer mark all multiples of x, but only the number multiplied by x in the set of prime numbers.
• For the problem of multiplying multiple prime numbers, we not only mark the prime numbers as a composite number, but also mark each number, such as 8 = 4 ∗ 2 8=4*2 8 = 4 * 2 4 cannot be ignored.
• Mark to each time x m o d    p r i m e s i = = 0 x \mod primes_i==0 xmodprimesi = = 0, because if x can divide a prime number, then for a composite number x ∗ p r i m e s i = x / p r i m e s i ∗ p r i m e s i + 1 x * primes_i = x/primes_i * primes_{i+1} X * primesi = x/primesi * primesi+1, that is, there must be a larger number after it so that it can be marked. Another blogger said in his introduction that the purpose is to "screen him out with the smallest quality factor".

class Solution:
    def countPrimes(self, n: int) -> int:
        # Check from 2 to n-1 (if it is less than or equal to n)
        isprime = [1 for i in range(0, n)]
        if len(isprime) <= 1:
            return 0
        isprime[0] = isprime[1] = 0
        primes = []
        for i in range(2, n):
            if isprime[i]:
                primes.append(i)
            for j in primes:
                if j*i < n :
                    isprime[i*j] = 0
                else:
                    break
                # You must join before exiting
                # 4 = 2*2
                if i % j == 0:
                    break
        return sum(isprime)
        

2172. Maximum sum of arrays

• Dynamic programming + state compression: from small to large, use the hexadecimal state to indicate the number of digits currently enumerated. In this way, you can reduce the number by one without enumerating the nums array O ( N ) O(N) Complexity of O(N). When one puts two into one, you can directly determine the number of 1 by counting the number of 1.

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
    	# The status is numSlots * 2-bit binary number
    	# So you can only put one in each basket
        f = [0] * (1 << (numSlots * 2))
       	# Each i represents from 0 to 1 < < (numslots * 2)
       	# That is, all the possibilities of putting the number in the basket
        for i, fi in enumerate(f):
			# There are several 1 notes that several numbers have been put in
            c = i.bit_count()
            # More than len(nums) baskets have been put in, and there are no more baskets to put in
            if c >= len(nums):
                continue
            for j in range(numSlots * 2):
            	# Enumerate empty baskets j
                if (i & (1 << j)) == 0:
                	# Put 1 on the empty blue j, and the state changes to s  
                    s = i | (1 << j)
                    f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))
        return max(f)