This series is my summary of data structure and algorithm when I was looking for a job many years ago. There are basic parts and classic interview questions of various companies. It was first published on CSDN. Is sorted out for a series of friends in need of reference, if there is a mistake, welcome to correct. The full code address for this series is here.
0 overview
Mathematics is the foundation of science, and numerical problems are often played out by the surface. Mathematics itself is an interesting subject, some time ago a little bit of work, had a strong interest in mathematics, so read a few books on the history of mathematics, but also bought “geometry” and “Tao Zhexuan’s real analysis”, see part of the chapter, benefited a lot, interested friends can see. In particular, the original geometry, the work of Euclid thousands of years ago, the way of thinking and proving it is really inspiring for all ages. This article first summarizes the number questions in the following questions, I try to add some mathematical proof, if there is any mistake, please correct. The code for this article is here.
1 finding prime numbers
Problem: Write a program to find the first N prime numbers. For example, if N is 100, find the first 100 prime numbers.
Analysis: A prime number (or prime number) is a natural number greater than 1 that is not divisible by any other natural number except 1 and itself. . The basic idea is to evaluate every number from 1 to N, and output if it’s prime. An improved approach is to eliminate the need to judge all numbers from 1 to N, because even numbers except 2 are definitely not prime, and odd numbers may or may not be prime. Then we can skip multiples of 2 and 3, that is, for 6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5, we just need to determine whether 6n+1 and 6n+5 are prime numbers.
The most basic way to determine whether a number m is prime is to divide the number between 2 and m-1 exactly by m. If any number is divisible by m, then M is not prime. The determination of whether m is prime can be further improved. Instead of dividing all numbers between 2 and m-1 by m, only numbers between 2 and the square root of m can be divided by m. If you use 2,3,4,5… Square root of m divisible by m. And this is actually a waste of time, because if 2 is not divisible, then multiples of 2 are not divisible, and if 3 is not divisible, then multiples of 3 are not divisible, so you can just use primes between 2 and the square root of m that are less than the square root of m.
Solution: 2, 3, 5 are prime numbers, then skip multiples of 2 and 3, start with 7, then 11, then 13, then 17… The rule is you go from 5 to 2, then to 4, then to 2, then to 4. So repeatedly, as shown in the figure below, only need to judge 7,11,13,17,19,23,25,29… These numbers.
To judge whether it is prime or not, the improved scheme is adopted, that is, the number between 2 and the square root of m is divisible by m. It is important to note that you cannot use the square root of m directly, because for some numbers, such as 121, the square root of 121 might be 10.999999, so it is best to use the multiplication judgment, as shown in the code.
Int primeGeneration(int N) {int prime = (int *)malloc(sizeof(int) * N); int gap = 2; int count = 3; int maybePrime = 5; int i, isPrime; */ prime[0] = 2; prime[1] = 3; prime[2] = 5;while (count < n) {
maybePrime += gap;
gap = 6 - gap;
isPrime = 1;
for (i = 2; prime[i]*prime[i] <= maybePrime && isPrime; i++)
if (maybePrime % prime[i] == 0)
isPrime = 0;
if (isPrime)
prime[count++] = maybePrime;
}
printf("\nFirst %d Prime Numbers are :\n", count);
for (i = 0; i < count; i++) {
if (i % 10 == 0) printf("\n");
printf("%5d", prime[i]);
}
printf("\n");
return 0;
}
Copy the code2 factorial with a zero at the end
Given an integer N, then N factorial N! How many zeros do we have at the end? (This question is taken from The Beauty of Programming)
Solution 1: The popular solution is that if N! = K10M, and K is not divisible by 10, then N! We have M 0’s at the end. Considering the N! You can do prime factorization, N factorial. = (2X) * (3Y) * (5Z)… , since 10 = 25, the number of zeros is only related to X and Z. Each pair of 2 and 5 is multiplied by each other to get a 10, so the number of zeros is M = min(X, Z). Obviously, there are more occurrences of 2 than 5, so the number of zeros is the number of occurrences of 5. From this, you can write the following code:
/** * N! */ int numOfZero(int n) {int CNT = 0, I, j;for (i = 1; i <= n; i++) {
j = i;
while(j % 5 == 0) { cnt++; j /= 5; }}return cnt;
}
Copy the codeSolution 2: Further analysis can improve the above code, to find the number of 5 in the factorization of 1 to N, let Z=N/5 + N/(52) + N/(53)+… That is, N/5 represents a multiple of 5 from 1 to N contributing a 5, and N/(52) represents a multiple of 52 contributing a 5… . Just to take a simple example, if you factor 1 to 100, how many 5’s are there, you know that there are 20 multiples of 5, and there are 4 multiples of 25, so there are 24 5’s. The code is as follows:
/** * N! */ numOfZero2(int n) {int CNT = 0;while (n) {
cnt += n/5;
n /= 5;
}
return cnt;
}
Copy the codeConclusion: The above analysis is unimpressive, but one thing that needs to be mentioned is that it involves a fundamental theorem of arithmetic, namely that any natural number greater than 1 can be decomposed into a product of primes in a unique way. Theorem proof is divided into two parts, existence and uniqueness. The proof is as follows:
Proof of existence
Use proof by contradiction to prove that if there are natural numbers greater than 1 that cannot be written as a product of primes, call the smallest one n. Natural numbers can be divided into three categories based on their divisible ability (whether they can be expressed as a product of two natural numbers that are not themselves) : prime, composite and 1.
- First of all, by definition, n is greater than 1.
- Second, n is not prime, because a prime p can be written as a product of prime numbers: p=p, which is inconsistent with the hypothesis. So n can only be composite, but each composite can be decomposed into the product of two natural numbers that are strictly smaller than themselves but greater than 1. set
n = a*bBoth a and b are numbers greater than 1 and less than n. According to the hypothesis, both a and B can be decomposed into a product of prime numbers, so n can also be decomposed into a product of prime numbers, so this contradicts the hypothesis. This proves that all natural numbers greater than 1 can be decomposed into products of prime numbers.
Proof of uniqueness
- When n=1, there really is only one decomposition.
- Suppose that for a natural number n>1, there are two factorizations: n= P1. pm = q1. qk, p1< =… <=pm, q1< =… <=qk, where p and q are both prime numbers, and we need to prove p1=q1, p2=q2. If they’re not equal, we can set p1 < q1To p1Less than all q’s. Due to the p1And q1Are prime numbers, so their greatest common divisor is 1. According to Euclidean algorithm, there exist integers A and b such that a * p1 + b * q1= 1. So a times p1 * q2. qk + b * q1 * q2. qk = q2. qk(Equation 1). Due to the q1. qkLambda is equal to n, so the left-hand side of equation 1 is p1So q on the right-hand side of equation 12. qkIt also has to be p1So it has to be p1 = qi, I > 1. And this is the same as the previous p1Less than all q contradictions, therefore, by symmetry, for P1 > q1A similar conclusion can be drawn in this case, so it can be proved that P1 = q1And p is the same thing2 = q2. pm=qk, thus completing the proof of uniqueness.
3 1-n The number of 1s in a positive integer
Given a positive decimal integer N, find the number of integers from 1 to N that contain 1. For example, given N=23, the number of 1s is 13. There are 1, 11, and 21 in the ones place, and 10,11 in the tens place… 19 is 10, so the total number of ones is 3 plus 10 is 13.
Analysis: The most natural idea would be to simply walk through 1 to N, find the number of 1s in each number, and then add them up to the total number of 1s. N numbers need to be traversed, each time the number of 1 needs O(log10N), the complexity of the algorithm is O(Nlog10N). When N is large, this algorithm takes a long time, and there should be a better way.
Solution: We can start with the 1-digit number and slowly find a pattern.
-
When N is a one-digit number, f(N) is 1 for N>=1.
-
When N is a two-digit number, the number of 1s in the ones place is related not only to the units place, but also to the tens place.
- When N=23, the number of 1s in the ones place is 1, 11, and 21, and the number of 1s in the tens place is 10,11… There are 10 of 19, so the number of ones
f(N) = 3+10 = 13. If the units digit of N is greater than =1, the number of 1s in the units digit is incremented by 1; If the units digit of N is 0, the number of 1s in the units digit is equal to the number of 10s. - The number of 1s in the tens digit is similar. If the tens digit of N is equal to 1, the number of 1s in the tens digit is the digit plus 1. If the tens digit of N is greater than 1, the number of 1s in the tens digit is 10.
- When N=23, the number of 1s in the ones place is 1, 11, and 21, and the number of 1s in the tens place is 10,11… There are 10 of 19, so the number of ones
-
When N is a 3-digit number, the same analysis yields the number of 1s. If N=123, the number of occurrences of 1 = 13+20+24 = 57.
-
When N is 4, 5… If we assume that N is abcde, we need to calculate the number of 1’s in the hundreds place, which is affected by three factors: the number in the hundreds place, the number below the hundreds place, and the number above the hundreds place.
- If the hundreds digit is 0, the number of times a 1 occurs in the hundreds digit is determined by the higher digit. If N=12013, 100~199, 1000~1199, 2100~2199… 11100 to 111999 A total of 1200 digits, equal to the higher digit of the hundreds (12) x the current digit (100).
- If the digit in the hundreds place is 1, the number of 1s in the hundreds place is affected not only by the higher place but also by the lower place. If 12113, there are 1200+114=1314 cases of 1 in the hundreds place, that is, 12 * 100 of high influence + 113+1 = 114 of low influence.
- If the hundreds digit is any other digit, the number of times a 1 occurs in the hundreds digit is determined only by the higher digit. If 12213 occurs in the hundreds digit, (12+1)*100=1300.
With that in mind, write the following code. Low indicates the low digit, curr indicates the current digit, and high indicates the high digit. A simple analysis, considering the number 123, first consider the ones place, then curr is 3, the low place is 0, and the high place is 12. Then consider the tens place, where the curr is 2, the low place is 3, and the high place is 1. Other numbers can be used in the same way, the implementation code is as follows:
Int numOfOne(int N) {int factor = 1, CNT = 0; Int low = 0, curr = 0, high = 0;while(n / factor ! = 0) { low = n - n/factor * factor; Curr = n/factor % 10; curr = n/factor % 10; high = n/(factor * 10); switch(curr) {caseCNT += high * factor;break;
caseCNT += high * factor + low + 1;break; Default: // CNT += (high+1) * factor;break;
}
factor *= 10;
}
return cnt;
}
Copy the codeA sequence of positive integers that sum to N
Problem: Input a positive integer number N, output all sum is N consecutive positive integer sequence. For example, input 15, and since 1+2+3+4+5=4+5+6=7+8=15, output three consecutive sequences 1-5, 4-6, and 7-8.
Solution 1: Apply mathematical laws
Suppose there are k consecutive positive integers sum N, where the first number in a continuous sequence is x, then x+(x+1)+(x+2)+… + (x + k – 1) = N. So we get x is equal to N minus k times k minus 1 over 2 over k. When x<=0, it indicates that there are no positive integer sequences with a sum of N, and the loop exits. Initialize k=2, indicating that the sum of two consecutive positive integers is N, then the value of x can be calculated, and determine whether there are two consecutive positive integers sum N starting from x, if not, k++, continue the cycle.
Int findContinuousSequence(int N) {int found = 0; int k = 2, x, m, i; // k is the number of consecutive numbers, x is the starting value, and m is used to determine whether there is a value that meets the condition.while(1) { x = (n - k*(k-1)/2) / k; X m = (n - k*(k-1)/2) % k; // m is used to determine whether there is a continuous positive integer value that meets the conditionif (x <= 0)
break; // Exit condition, if x<=0, loop exit.if(! M) {// m is 0, indicating that the sum of continuous subsequence is found and n. found = 1;printContinuousSequence(x, k);
}
k++;
}
returnfound; } /** * prints a continuous subsequence */ voidprintContinuousSequence(int x, int k)
{
int i;
for (i = 0; i < k; i++) {
printf("%d ", x++);
}
printf("\n");
}
Copy the codeSolution 2: sequence end position method
Because the sequence has at least two numbers, we can first determine whether the sum of a continuous sequence ending with the number 2 is equal to n, and then whether the sum of a continuous sequence ending with 3 is equal to n… And so on. This solution idea refers to Mr. He Haitao’s blog, the code is as follows:
/ * * * search and for continuous - sequences at the end position of N * / int findContinuousSequenceEndIndex (int N) {if (n < 3) return 0;
int found = 0;
int begin = 1, end = 2;
int mid = (1 + n) / 2;
int sum = begin + end;
while (begin < mid) {
if (sum > n) {
sum -= begin;
begin++;
} else {
if (sum == n) {
found = 1;
printContinuousSequence(begin, end-begin+1); } end++; sum += end; }}return found;
}
Copy the codeExtension: Can all positive integers be decomposed into consecutive sequences of positive integers?
Answer: No. Not all positive integers can be factored into the sum of consecutive positive integers. For example, 32 cannot be factored into the sum of consecutive positive integers. For an odd number, we can always write it as 2k+1, so it can be factored into [k,k+1], so it can always factored into a continuous sequence of positive integers. For every even number, it can be decomposed into the product of prime factors, that is, n = 2i * 3j * 5k… If j, k… All are 0, then n = 2i, for this kind of number, all the factors are even, there is no continuous subsequence sum of n, so all positive integers of n>=3 except the power of 2 can be written as a continuous sum of natural numbers.
5. Sum of maximum continuous subsequence
For example, given the array A = {1, 3, -2, 4, -5}, then the maximum sum of continuous subsequences is 6, i.e. 1 + 3 + (-2) + 4 = 6.
Analysis: The maximum continuous subsequence and the problem is an old interview problem, the best solution is O(N) complexity, of course there are some noteworthy. Here are three common solutions, focusing on the last one, O(N). Note that in some cases the maximum subsequence sum is negative, then 0 is returned; In this case, if they are all negative numbers, return the largest negative number.
Solution 1: Since the sum of the maximum contiguous subsequence can only start at some point in the array 0 to n-1, we can traverse 0 to n-1 and calculate the maximum value in the sum of all contiguous subsequences starting from this position. So we can figure out the maximum.
/ maximum continuous subsequence and * * * * / int maxSumOfContinuousSequence (int a [], int n) {int Max = a [0], I, j, sum; // Initialize the maximum value to the first elementfor(i = 0; i < n; i++) { sum = 0; // sum must be cleared to zerofor(j = i; j < n; J++) {// calculate the size of the maximum subsequence sum from I starting at position I, and update Max if greater than Max. sum += a[j];if(sum > max) max = sum; }}return max;
}
Copy the codeSolution 2: The problem can also be solved by divide-and-conquer, where the maximum continuous subsequence sum occurs either in the left half of the array, the right half of the array, or across the left and right halves. So by finding the maximum value in these three cases, you can get the sum of the maximum continuous subsequence.
/ maximum continuous subsequence and * * * - * / partition method int maxSumOfContinuousSequenceSub (int a [], int l, int u) {if (l > u) return 0;
if (l == u) returna[l]; int m = (l + u) / 2; Int lmax = a[m], lsum = 0; int i;for (i = m; i >= l; i--) {
lsum += a[i];
if(lsum > lmax) lmax = lsum; Int rmax=a[m+1], rsum = 0;for (i = m+1; i <= u; i++) {
rsum += a[i];
if (rsum > rmax)
rmax = rsum;
}
returnmax3(lmax+rmax, maxSumOfContinuousSequenceSub(a, l, m), maxSumOfContinuousSequenceSub(a, m+1, u)); // Return the maximum value of all three}Copy the codeSolution 3: There is a better solution that only takes O(N) time. Because the maximum subsequence sum can only end at positions 0 to n minus 1. When traversing the ith element, judge whether the sum of the contiguous subsequence before it is greater than 0. If it is greater than 0, then the sum of the largest contiguous subsequence ending at position I is the sum of the sum of the contiguous subsequence before element I. Otherwise, the sum of the maximum continuous subsequence ending at position I is a[I].
/ * * * the most continuous subsequence and end position method * / int maxSumOfContinuousSequenceEndIndex (int a [], int n) {int maxSum, maxHere, I; maxSum = maxHere = a[0]; // Initialize Max sum to a[0]for (i = 1; i < n; i++) {
if(maxHere <= 0) maxHere = a[i]; // If the sum is less than or equal to 0, then the sum is a[I].elsemaxHere += a[i]; // If the sum of the largest contiguous subsequence in the preceding position is greater than 0, the sum of the largest contiguous subsequence ending in the current position I is the sum of both of themif(maxHere > maxSum) { maxSum = maxHere; // Update maximum continuous subsequence and}}return maxSum;
}
Copy the codeMaximum continuous subsequence product
Given a sequence of integers (possibly positive, 0, and negative), find a maximum continuous subsequence product. Such as array given a [] = {3, 4, 5, 6, 2}, is the largest continuous subsequence product was $360, or 3 * (4) * * 6 = 360 (5).
Solution: Finding the product of the maximum continuous subsequence is different from the sum problem of the maximum continuous subsequence, because there are positive, negative and possibly 0, which can be solved directly by using dynamic return. Considering the possible existence of negative numbers, we use Max [I] to represent the product value of the maximum continuous subsequence ending with a[I]. Min [I] is used to represent the product value of the smallest continuous subsequence ending with A [I], then the state transition equation is:
max[i] = max{a[i], max[i-1]*a[i], min[i-1]*a[i]};
min[i] = min{a[i], max[i-1]*a[i], min[i-1]*a[i]};
Copy the codeInitial state Max [0] = min[0] = A [0]. The code is as follows:
/ * * * product of maximum continuous subsequence * / int maxMultipleOfContinuousSequence (int a [], int n) {int minSofar, maxSofar, Max, I; int maxHere, minHere; max = minSofar = maxSofar = a[0];for(i = 1; i < n; i++){
int maxHere = max3(maxSofar*a[i], minSofar*a[i], a[i]);
int minHere = min3(maxSofar*a[i], minSofar*a[i], a[i]);
maxSofar = maxHere, minSofar = minHere;
if(max < maxSofar)
max = maxSofar;
}
return max;
}
Copy the code7 bit correlation
1) Determine whether a positive integer is a power of 2
Given a positive integer n, determine whether the positive integer is a power of 2.
Solution 1: A basic solution is to start with I =1, multiply by 2 until I >=n, and then determine if I is equal to n.
Solution 2: A better way is to look at the binary representation of numbers, such as n=101000, and find n-1=100111. So n- > n-1 is changing the 1 to the right of n to a 0, and changing all the bits to the right of the 1 to the right of n from 0 to 1. So if n ^ (n-1) == 0 we know that the positive integer n is an integer power of 2.
Int powOf2(int n) {assert(n > 0);return! (n & (n-1)); }Copy the code2) Find the number of 1s in the binary representation of an integer
Find the number of 1’s in the binary representation of integer, for example, given N=6, its binary representation is 0110, the number of 1’s in the binary representation is 2.
Solution 1: A natural way is to place N and 1 and then divide N by 2 until N is 0. The algorithm code is as follows:
int numOfBit1(int n)
{
int cnt = 0;
while (n) {
if (n & 1)
++cnt;
n >>= 1;
}
return cnt;
}
Copy the codeThe code above has a problem that negative numbers can cause an infinite loop. To solve the problem of negative numbers, we can use the unsigned right shift operator >>> if we use JAVA. If we use C/C++, we can avoid the infinite loop by not right-shifting the input number I. First, I &1, and I want to know if the lowest order of I is 1. Then move 1 one bit to the left to get 2, and then do the and operation with I to determine whether the second highest order of I is 1… If I move to the left over and over again, each time I know whether one of the I’s is 1 or not.
1 */ int numOfBit1(int n) {int CNT = 0; unsigned int flag = 1;while (flag) {
if(n & flag)
cnt++;
flag = flag << 1;
if (flag > n)
break;
}
return cnt;
}
Copy the codeSolution 2: A better solution is to use a similar idea to the one in the first problem. Every time n&(n-1) changes the rightmost 1 in n to 0, so it is easy to find the total number of 1s.
/** * int numOfBit1WithCheck(int n) {int CNT = 0;while(n ! = 0) { n = (n & (n-1)); cnt++; }return cnt;
}
Copy the code3) Invert all the bits of an unsigned integer
Given an unsigned integer N, reverse all the bits of the integer. For example, an 8-bit number 01101001 would be reversed to 10010110, and a 32-bit unsigned integer would be similarly reversed.
Solution 1: The natural solution is to follow the string inversion algorithm, assuming that the unsigned integer has n bits, swap the 0th and NTH bits first, and then swap the 1st and n-1st bits… Note that swapping two bits can be done by XOR, because 0 XOR 0 = 0, 1 XOR 1 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1, and using 1 XOR 0/1 reverses the value.
/** * reverse bit */ uint swapBits(uint x, uint I, uint j) {uint lo = ((x >> I) &1); Uint hi = ((x >> j) &1); // Take the JTH bit of xif(lo ^ hi) { x ^= ((1U << i) | (1U << j)); // If the i-th bit and the j-th bit are different, swap the i-th bit and the j-th bit with xor}returnx; } /** * reverseXOR(uint x) {uint n = sizeof(x) * 8; uint i;for (i = 0; i < n/2; i++) {
x = swapBits(x, i, n-i-1);
}
return x;
}
Copy the codeSolution 2: Using a divide-and-conquer strategy, first swap adjacent bits of the number X, then 2 bits, then 4 bits… For example, given an 8-digit number 01101010, first swap the adjacent bits to become 10 0101 01, then swap the two adjacent bits to get 0110 0101, and then swap the four bits to get 0101 0110. The total time complexity is O(lgN), where N is the number of digits of an integer. Here is a code to invert 32-bit integers, and so on if integers are 64-bit.
/** * reverseMask(uint x) {assert(sizeof(x) == 4); // specialcase: only works for 4 bytes (32 bits).
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
return x;
}
Copy the codeThe resources
- The beauty of the programming
- The concrete mathematical
- Articles.leetcode.com/reverse-bit…
- Zhedahht.blog.163.com/blog/static…