preface
This is the second half of the interview questions on data structures and algorithms. This part is mainly about algorithm classes including binary search, sorting algorithm, recursive algorithm, random algorithm, knapsack problem, number problem and so on. Shishujuan /dsalg: Shishujuan /dsalg: Data structure and algorithm series summary, if there is any error, please comment below the article point out or give me a message on Github, I good timely correction so as not to mislead other friends.
At the end of this article there are a series of directories for you to read on demand, and if you need to test, you can clone the repository code for various tests. If there are mistakes or incomplete quotation, there is infringement, please point out to me, SO that I can adjust and correct in time. If this series has helped you, please feel free to like it or go to github star✨✨. Thank you very much.
Data structures and Algorithms interview questions series – binary search algorithm details
Summary of 0.
Binary search is a simple algorithm in itself, but because of its simplicity, it is more prone to writing errors. Even in the early days of binary lookup algorithms, there were bugs (spillover bugs) that weren’t fixed until decades later (see Programming Pearls). This paper intends to summarize the binary search algorithm and analyze and summarize the problems derived from binary search. If there are any mistakes, please correct them. The full code for this article is here.
1. Binary search basis
I believe we all know the basic algorithm of binary search, as shown below, this is the binary search algorithm code:
Int l = 0, u = n-1; int l = 0, u = n-1;while(l <= u) { int m = l + (u - l) / 2; // Same as (l+u) / 2, for overflowif (t > a[m])
l = m + 1;
else if (t < a[m])
u = m - 1;
else
return m;
}
return -(l+1);
}
Copy the codeThe idea is to start in the middle of the array and eliminate half of the data at a time in order (lgN). It depends on the fact that the array is ordered. If t exists in an array, return t’s position in the array; Otherwise, it does not exist and returns -(l+1).
Now, I need to explain why instead of returning -1 when t is not in the array, I return -(l+1). First we can look at the value of L, and if the lookup fails, l is exactly where T should be inserted into the array.
For example, given that the ordered array a={1, 3, 4, 7, 8}, then if t = 0, it is clear that t is not in the array, the binary search algorithm will eventually make l = 0 > u=-1 exit the loop; If t = 9, then t is also not in the array, and finally l = 5 > u = 4 exits the loop. If t=5, the loop ends with l=3 > u=2. Therefore, in some algorithms, such as DHT (consistent hashing), this return value is needed to insert the newly added node into the appropriate position, and it is also used in the NlgN algorithm for the longest increasing subsequence, see the post on longest increasing subsequence algorithm.
The other little point is that the reason why you return -(l+1) instead of just returning -l is because l might be 0, and if you return -l you can’t tell if you return 0 normally or if you don’t get it.
2. Locate the first occurrence of a number in an ordered array
Now consider a slightly more complicated problem. If there are repeated numbers in an ordered array, such as the array a={1, 2, 3, 3, 5, 7, 8}, you need to find where 3 first occurs. This is where 3 first appears at position 2. This problem has a good analysis in chapter 9 of Programming Abet, which is directly used here. The essence of the algorithm lies in the clever design of the loop invariant, the code is as follows:
/** ** binarySearchFirst(int a[], int n, int t) {int l = -1, u = n;while(l + 1 ! U) = {/ * loop invariant a [l] < t < = a [u] && l < u * / int m = l + (u - l) / 2; // Same as (l+u) / 2if (t > a[m])
l = m;
else
u = m;
}
/*assert: l+1=u && a[l]<t<=a[u]*/
int p = u;
if(p>=n || a[p]! =t) p = -1;return p;
}
Copy the codeAlgorithm analysis: Set two nonexistent elements A [-1] and a[n], so that a[-1] < t <= a[n], but we will not visit the two elements, because (L +u)/2 > L =-1, (L +u)/2 < u=n. The cyclic invariant is la[l] &&t <=a[u]. The loop must exit with l+1=u and a[l] < t <= a[u]. The value of u after the loop exits is the possible position of t, and its range is [0, n]. If t is in the array, the first position of t is p=u, and if not, p=-1 is set to return. This algorithm solves more complex problems, but it is more efficient than the original version of binary search because it requires only one comparison per loop, compared with two comparisons that the previous program typically required.
For example, if a={1, 2, 3, 3, 5, 7, 8}, if t=3, we can get p=u=2, if t=4, a[3]
=n, such as t=9, u=7, and p=-1. In particular, l=-1 and u=n cannot be written as l=0 and u=n-1. Although these two values are not accessible, changing them to the latter will cause binary lookup to fail and the first number will not be accessed. If a={1, 2, 3, 4, 5} is used to search for 1, the initial setting of l=0 and u=n-1 will cause the search to fail.
What if you want to find the last position of a number in an array? In fact, this is similar to the above algorithm, slightly change the above algorithm can be, the code is as follows:
/** * binarySearchLast(int a[], int n, int t) {int l = -1, u = n;while(l + 1 ! U) = {/ * loop invariant, a [l] < = t < a [u] * / int m = l + (u - l) / 2;if (t >= a[m])
l = m;
else
u = m;
}
/*assert: l+1 = u && a[l] <= t < a[u]*/
int p = l;
if(p<=-1 || a[p]! =t) p = -1;return p;
}
Copy the codeOf course, there is also a way to query the first and last occurrence of the number of code in a program, just need to modify the original binary lookup slightly, the code is as follows:
/** * int searchFirstandLast (int a[], int n, int t, int firstFlag) {int l = 0; int u = n - 1;while(l <= u) {
int m = l + (u - l) / 2;
if(a[m] == t) {// if (a[m] == t)if(firstFlag) {// Query the location of the first occurrenceif(m ! = 0 && a[m-1] ! = t)return m;
else if(m == 0)
return 0;
else
u = m - 1;
} else{// Query the location of the last occurrenceif(m ! = n-1 && a[m+1] ! = t)return m;
else if(m == n-1)
return n-1;
elsel = m + 1; }}else if(a[m] < t)
l = m + 1;
else
u = m - 1;
}
return- 1; }Copy the code3. Rotate the array elements to find the problem
The title
Moving the first elements of an ordered array to the end of the array is called rotation. For example, array {3, 4, 5, 1, 2} is a rotation of {1, 2, 3, 4, 5}. Now, given the rotated array and a number, we don’t know how many bits we rotated, we’re asked to come up with an algorithm that calculates the index of the given number in the array, and returns -1 if the number is not found. The number of searches cannot exceed N.
Analysis of the
As you can see from the problem, the rotated array is completely unordered, but its front and back parts are partially ordered. Binary lookup can therefore be used to solve the problem.
Solution 1: two binary searches
First determine the array split point, that is, the array on both sides of the split point is ordered. For example, the array is split at position 2, with the first part {3,4,5} in order and the second part {1,2} in order. Then use binary search for both parts. The code is as follows:
*/ int binarySearchRotateTwice(int a[], int n, int t) {int p = findRotatePosition(a, n); // Find the rotation positionif (p == -1)
returnbinarySearchFirst(a, n, t); Int left = binarySearchFirst(a, p+1, t); // Find the left halfif (left != -1)
returnleft; Int right = binarySearchFirst(a+p+1, n-p-1, t); // If the left part is not found, find the right partif (right == -1)
return- 1;returnright+p+1; Int findRotatePosition(int a[], int n) {int I; // findRotatePosition(int a[], int n) {int I;for (i = 0; i < n-1; i++) {
if (a[i+1] < a[i])
return i;
}
return- 1; }Copy the codeSolution 2: a binary search
Binary search algorithm has two key points: 1) array order; 2) Determine whether the next binary search should be carried out in the first half of the interval or the second half of the interval according to the size relationship between the middle element of the current interval and T.
After careful analysis of the problem, it can be found that at least one to the left ([l, m]) and one to the right ([m, u]) of M is ordered each time m is solved in terms of L and u. A [m] is compared with a[L] and a[u] respectively to determine which segment is ordered.
- If the left-hand side is ordered, if
t<a[m] && t>a[l],u=m-1; In other cases,l =m+1; - If the right-hand side is ordered, if
t> a[m] && t<a[u]则l=m+1; In other cases,u =m-1; The code is as follows:
/** */ int binarySearchRotateOnce(int a[], int n, int t) {int l = 0, u = n-1;while (l <= u) {
int m = l + (u-l) / 2;
if (t == a[m])
return m;
if(a[m] >= a[l]) {// Array left semi-orderedif (t >= a[l] && t < a[m])
u = m - 1;
else
l = m + 1;
} else{// The right half of the array is sortedif (t > a[m] && t <= a[u])
l = m + 1;
elseu = m - 1; }}return- 1; }Copy the codeData structures and algorithms interview questions series – The basics of sorting algorithms
Summary of 0.
Sorting algorithms are also frequently mentioned in interviews, and the most frequently asked questions should be quicksort, heap sort. These sorting algorithms are pretty basic, but if you don’t write much code, you’ll get a lot of bugs in your interview. Although thought all know, but just can’t write out. This paper intends to make a summary of various sorting algorithms, including insertion sort, bubble sort, selection sort, count sort, merge sort, radix sort, bucket sort, quick sort and so on. Quicksort is important, I will write a separate article, and heap sort can see the binary heap article in this series.
One thing to mention is that insertion sort, bubble sort, merge sort, and count sort are all stable sorts, while the rest are unstable. The full code for this article is here.
1. Insert sort
Insert sort is a very basic sort, especially in the case of basically ordered data, the performance of insert sort is very high, the best case can reach O(N), its worst case and average case time complexity is O(N^2). The code is as follows:
/** * insertSort */ void insertSort(int a[], int n) {int I, j;for(i = 1; i < n; I ++) {/* * Loop invariant: a[0... I -1] is ordered. Before the start of each iteration, a [0... I - 1] orderly, * the end of the loop I = n, a n - [0... 1] order * * / int key = a, [I].for(j = i; j > 0 && a[j-1] > key; j--) { a[j] = a[j-1]; } a[j] = key; }}Copy the code2. Hill sort
Hill sort internal calls to insert sort, by N/2, N/4… Order 1 is sorted separately to obtain the overall order.
Void shellSort(int a[], int n) {int gap;for (gap = n/2; gap > 0; gap /= 2) {
int i;
for (i = gap; i < n; i++) {
int key = a[i], j;
for(j = i; j >= gap && key < a[j-gap]; j -= gap) { a[j] = a[j-gap]; } a[j] = key; }}}Copy the code3. Select sort
The idea of selection sort is to take the ith smallest element and put it at position I. For example, the first time I choose the smallest element and put it at position 0, and the second time I choose the second smallest element and put it at position 1. Both the best and worst time complexity of selection sort are O(N^2). The code is as follows:
/** * selectSort */ void selectSort(int a[], int n) {int I, j, min, TMP;for (i = 0; i < n-1; i++) {
min = i;
for (j = i+1; j < n; j++) {
if (a[j] < a[min])
min = j;
}
if(min ! = i) tmp = a[i], a[i] = a[min], a[min] = tmp; // Switch a[I] and a[min]}}Copy the codeLoop invariant: Before the outer loop executes,a[0...i-1]containsaThe smallestiNumber, and ordered.
-
At the beginning, I =0, a[0…-1] is empty, obviously true.
-
After each execution, a[0… I] contains the smallest number of I +1 in a and is ordered. That is, after the first execution, a[0…0] contains the smallest number of a in an orderly manner.
-
At the end of the loop, I =n-1, then a[0…n-2] contains the smallest n-1 number of a and is already ordered. So the whole array is sorted.
4. Bubble sort
Bubble sort time complexity is the same as selection sort. The idea is to sort n minus 1 times, each time floating the smallest number up like a fish bubbling. The worst case is order N^2. The code is as follows:
Void bubbleSort(int a[], int n) {int I, j, TMP;for (i = 0; i < n; i++) {
for (j = n-1; j >= i+1; j--) {
if(a[j] < a[j-1]) tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; }}}Copy the codeLoop invariant: subarray before loop begins iterationa[0...i-1]Contains an arraya[0..n-1] 的 i-1Is the minimum value, and is sorted.
An improvement to bubble sort is to determine whether swapping occurs at each sort run. If neither swap occurs, the array is sorted and can exit without continuing the remaining runs. The improved code is as follows:
Void betterBubbleSort(int a[], int n) {int TMP, I, j;for (i = 0; i < n; i++) {
int sorted = 1;
for (j = n-1; j >= i+1; j--) {
if(a[j] < a[j-1]) { tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; sorted = 0; }}if (sorted)
return; }}Copy the code5. Counting sort
Suppose the array is a[0…n-1], there are duplicate numbers in the array, and the largest number in the array is K, build two auxiliary arrays B [] and C [], B [] is used to store sorted results, and C [] is used to store temporary values. The time complexity is O(N), which is suitable for arrays with a small number range.
Counting sort principle is shown in the figure above, the code is as follows:
/** * count sort */ void countingSort(int a[], int n) {int I, j; int *b = (int *)malloc(sizeof(int) * n); int k = maxOfIntArray(a, n); Int *c = (int *)malloc(sizeof(int) * (k+1)); // Auxiliary arrayfor (i = 0; i <= k; i++)
c[i] = 0;
for(j = 0; j < n; j++) c[a[j]] = c[a[j]] + 1; //c[I] contains elements equal to Ifor(i = 1; i <= k; i++) c[i] = c[i] + c[i-1]; //c[I] contains the number of elements less than or equal to Ifor(j = n-1; j >= 0; J --) {b[c[a[j]]-1 = A [j]; C [a[j]] = C [a[j]] -1; } /* For testing code, this step is not required */for (i = 0; i < n; i++) {
a[i] = b[i];
}
free(b);
free(c);
}
Copy the codeExtension: if the assignment statement for (j=n-1; j>=0; J -) to the for (j = 0; j<=n-1; J++), the code is still correct, but the sorting is no longer stable.
6. Merge sort
Merge sort Uses the divide-and-conquer algorithm to sort two subarrays and then merge the two subarrays. The time is O(NlgN). The code is as follows:
/* */ mergeSort(int a[], int l, int u) {if (l < u) {
int m = l + (u-l) / 2; mergeSort(a, l, m); mergeSort(a, m + 1, u); merge(a, l, m, u); }} /** * merge(int a[], int l, int m, int u) {int n1 = m-l + 1; int n2 = u - m; int left[n1], right[n2]; int i, j;for (i = 0; i < n1; i++) /* left holds a[l..m] */
left[i] = a[l + i];
for (j = 0; j < n2; j++) /* right holds a[m+1..u] */
right[j] = a[m + 1 + j];
i = j = 0;
int k = l;
while (i < n1 && j < n2) {
if (left[i] < right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
}
while (i < n1) /* left[] is not exhausted */
a[k++] = left[i++];
while (j < n2) /* right[] is not exhausted */
a[k++] = right[j++];
}
Copy the codeExtension: What about a non-recursive implementation of merge sort?
The non-recursive implementation of merge sort is actually the most natural way to do it, which is to merge in pairs, then merge in fours, and so on, from the bottom up. The code is as follows:
Void mergeSortIter(int a[], int n) {int I, s=2;while (s <= n) {
i = 0;
while(i+s <= n){ merge(a, i, i+s/2-1, i+s-1); i += s; } // Merge (a, I, I + S /2-1, n-1); s*=2; } // Merge (a, 0, s/2-1, n-1); }Copy the code7. Radix sort, bucket sort
The idea of radix sort is to sort each bit of the number separately (note that it must be a stable sort, such as counting sort, otherwise the result will be wrong), and finally get the whole sort. Suppose sorting N numbers, if the number has D bits, and the maximum possible value of each bit is K, then the stable sorting of each bit takes O(N+K) time, and the total time is O(d(N+K)) time. When D is constant and K=O(N), the total time complexity is O(N).
The idea of bucket sorting is to divide the interval [0,1) into N sub-intervals of the same size, distribute the N inputs evenly among each bucket, and then use insertion sorting for the linked list of each bucket, and finally list all the elements of the bucket successively.
These two kinds of sorting are used in a limited number of scenarios, so the code will be skipped. See Chapter 8 of Introduction to Algorithms for more details.
Data structures and algorithms interview series-quicksort for sorting algorithms
Summary of 0.
Quicksort is also based on divide-and-conquer, similar to merge sort, except that there is no merge at the end of the quicksort partition. Quicksort an array A[p..r] consists of three steps:
- Partition: array
A[p...r]Is divided into two subarraysA[p...q-1]和A[q+1...r],A[p...q-1]Is less than or equal to every element inA[q]And theA[q+1...r]Each element is greater thanA[q]. The partitioning process is shown in the following figure. - Solution: Sort the subarrays separately by recursively calling quicksort.
- Merge: Because the two subarrays are already sorted and sized, no action is required.
Quicksort algorithm is not a complex algorithm, but the actual code is the most error-prone code, write the wrong easy to loop or partition error, this code see here.
1. Naive quicksort
One drawback of this naive quicksort is that in extreme cases where all elements are equal (or the elements themselves are ordered, such as a[] = {1,2,3,4,5}, etc.), the naive fast algorithm is O(N^2) and O(N LGN) if the array is balanced.
/ / void quickSort(int a[], int l, int u) {/ / void quickSort(int a[], int l, int u) {if (l >= u) return; int q = partition(a, l, u); quickSort(a, l, q-1); quickSort(a, q+1, u); } /** * int partition(int a[], int l, int u) {int I, q=l;for (i = l+1; i <= u; i++) {
if (a[i] < a[l])
swapInt(a, i, ++q);
}
swapInt(a, l, q);
return q;
}
Copy the code2. Improved – bidirectional partition quicksort
An improved method is to adopt bidirectional partition, using two variables I and J. I scans from left to right, moves over small elements, and stops when encountering large elements. J scans from right to left, moving large elements and stopping at small elements. Then test if I and j cross, stop if they do, otherwise swap the values of the elements I and j correspond to.
Notice that if we have the same elements in the array, we stop scanning and swap the element values of I and j when we encounter the same elements. This increases the number of swaps, but it turns the worst-case case where all the elements are the same from O(N^2) to something like O(NlgN). For example, if array A={2,2,2,2,2}, the naive quicksort method is used to divide n elements into 1 and n-1 each time, and the time complexity is O(n ^2). After bidirectional partition, the position of the first partition is 2, which can basically balance the two parts. The code is as follows:
/** * quick sort - double partition function */ int int lr (int a[], int l, int u, int pivot) {int I = l; int j = u+1;while (1) {
do {
i++;
} while(a[i] < pivot && i <= u); // I <=u.do {
j--;
} while (a[j] > pivot);
if (i > j) break; swapInt(a, i, j); } // a[I...u] is greater than or equal to the pivot element t, and the pivot element is on the left, so it cannot be swapped with I. You can only swap with j. swapInt(a, l, j);returnj; } /** * quickSortLR(int a[], int l, int u) {if (l >= u) return;
int pivot = a[l];
int q = partitionLR(a, l, u, pivot);
quickSortLR(a, l, q-1);
quickSortLR(a, q+1, u);
}
Copy the codeAlthough bidirectional partitioning solves the problem that all elements are the same, it still achieves O(N^2) complexity for an already sorted array. While (a[I]
3. Continue to improve – random method and trinary method to get hub elements
In order to solve the above problems, it can be further improved to obtain the hub elements by randomly selecting the hub elements or taking the center of three numbers, and then divide the hub elements bidirectionally. The triplet refers to sorting three values from array A[L… u] and using the middle value as the pivot element. If group A[] = {1, 3, 5, 2, 4}, then we sort A[0], A[2] and A[4], select the median A[4](element 4) as the pivot element, and swap it to A[L]. Finally, the array becomes A[] = {4 3 5 2 1}. And then sort it both ways as before.
Int pivotRandom(int a[], int l, int u) {int rand = randInt(l, u); swapInt(a, l, rand); // Swap hub elements to position Lreturna[l]; } /** * pivotMedian3(int a[], int l, int u) {int m = l + (u)-l) / 2; /* * * * * */if( a[l] > a[m] )
swapInt(a, l, m);
if( a[l] > a[u] )
swapInt(a, l, u);
if( a[m] > a[u] ) swapInt(a, m, u); /* assert: a[l] <= a[m] <= a[u] */ swapInt(a, m, l); // Swap hub elements to position Lreturn a[l];
}
Copy the codeIn addition, when the data is basically ordered, you can get good performance by using insert sort, and it is faster than quicksort when sorting small subarrays. You can use insert sort when the array size is small, but quicksort when the array size is large.
4. Write non-recursive quicksort
Non-recursive quicksort writing is really rare, but it’s always good to get your hands on it. You need to use stacks, and pay attention to the order in which you push them. The code is as follows:
Void quickSortIter(int a[], int n) {Stack * Stack = stackNew(n); int l = 0, u = n-1; int p = partition(a, l, u);if(p-1 > l) {// The left half of the two boundary values push(stack, p-1); push(stack, l); }if(p+1 < u) {// Push (stack, u); push(stack, p+1); }while(! IS_EMPTY(stack)) {// if the stack is not empty, then the loop partition process l = pop(stack); u = pop(stack); p = partition(a, l, u);if (p-1 > l) {
push(stack, p-1);
push(stack, l);
}
if(p+1 < u) { push(stack, u); push(stack, p+1); }}}Copy the codeData Structures and Algorithms interview questions series – Summary of random algorithms
Summary of 0.
Random algorithms involve a lot of probability theory knowledge, sometimes it is difficult to watch the derivation process carefully, of course, it is good to fully understand the derivation process, if not understand the derivation process, at least remember the conclusion is necessary. This article summarizes some of the most common random algorithms, which I wrote a few years ago when I was looking for a job. It should be noted that the random function randInt(a, b) assumes that it can randomly produce integers in the range [a,b], i.e., each integer is equally likely to be produced (although this is not always possible in practice, but don’t worry too much about it, a lot of things in this world are random). The code for this article is here.
1. Arrange arrays randomly
Given an array A that contains elements 1 through N, our goal is to construct A uniform random arrangement of the array.
A common approach is to assign each element of an array A[I] A random priority P[I], and then sort the array by that priority. For example, if our array is A ={1, 2, 3, 4}, if the selected priority group is P ={36, 3, 97, 19}, then we can get the sequence B={2, 4, 1, 3}, because 3 has the highest priority (97), and 2 has the lowest priority (3). This algorithm needs to generate a sequence of precedence series, and it also needs to sort the array using the sequence of precedence series, which I won’t describe in detail here, but there’s a better way to get a randomly arranged array.
A better way to generate randomly arranged arrays is to “in-place” a given array, which can be done in O(N) time. The pseudocode is as follows:
RANDOMIZE-IN-PLACE ( A , n )
forI please 1 to ndoSwap A[I] ↔ [RANDOM(I, n)]Copy the codeAs shown in the code, at iteration I, element A[I] is randomly selected from element A[I…n], and after iteration I, we never change A[I] again.
The probability that A[I] is at any position j is 1/n. This is easy to derive, for example, that the probability of A[1] being at position 1 is 1/n, which is obvious, because the probability of A[1] not being replaced by an element from 1 to n is 1/n, and then it doesn’t change A[1] anymore. And the probability that A[1] is at position 2 is also 1/n, because A[1] must be at position 2 at the first time with A[k] (k=2… The probability of the first exchange with A[k] is (n-1)/n, while the probability of the second substitution is 1/(n-1), so the total probability is (n-1)/n * 1/(n-1) = 1/n. You can do the same thing for other cases.
Of course, this condition can only be A necessary condition for random arrays, that is, the probability that A[I] is at position j with A probability of 1/n does not necessarily mean that it can produce random arrays. Because the number of possible permutations is less than n! Although the probability is equal, the number of permutations does not meet the requirement. There is a counter example of this in the introduction to algorithms.
The algorithm randomize-in-place can generate uniform random permutation, and its proof process is as follows:
Firstly, the concept of k permutation is given. The so-called K permutation is the permutation of k elements selected from n elements, so it has n! /(n-k)! K permutations.
Loop invariant: Before iteration I of the for loop, for each possible i-1 permutation, the probability that subarray A[1…i-1] contains the i-1 permutation is(n-i+1)! / n!.
-
Initialization: before the first iteration, I =1, then the loop invariant means that for each permutation of 0, the probability that subarray A[1…i-1] contains that permutation is (n-1+1)! / n! = 1. A[1…0] is an empty array with zero elements, so the probability that A contains all possible zeros is 1. The invariant holds.
-
Maintain: Assume that the probability of the array’s i-1 permutation occurring in A[1…i-1] is (n-i+1)! / n! , then after iteration I, the probability of all I permutations of the array appearing in A[1… I] is (n-i)! / n! . Here’s how to derive this conclusion:
- Consider a special permutation of I p = {x1, x2. xi}, it is arranged by an I -1 p’ ={x1, x2… , xI – 1} followed by an xiComposition. Set two event variables E1 and E2:
-
E1 is the event in which the algorithm places the permutation P ‘to A[1…i-1], and the probability is Pr(E1) = (n-i+1)! / n! .
-
E2 is the event that puts XI into A[I] at iteration I. So we get the I arranged in the probability of A [1… I] is Pr studying E1} {E2 = Pr Pr {E1} {E2 | E1}. And Pr | E1} {E2 = 1 / (n – I + 1), so studying E1} {E2 Pr = {E2 | E1} {E1} Pr Pr = 1 / (n – I + 1) * (n – I + 1)! / n! = (n − I)! / n! .
-
End: I =n+1 at the end, so it follows that A[1…n] is A given permutation of n with A probability of 1/n! .
C implementation code is as follows:
void randomInPlace(int a[], int n)
{
int i;
for(i = 0; i < n; i++) { int rand = randInt(i, n-1); swapInt(a, i, rand); }}Copy the codeextension
If the above random permutation algorithm is written as follows, can it also produce uniform random permutation?
PERMUTE-WITH-ALL( A , n )
forI please 1 to ndoSwap A[I] ↔ [RANDOM(1, n)]Copy the codeNote that this algorithm does not produce uniform random permutations. Assuming n=3, the algorithm can produce 3*3*3=27 outputs with 3 elements only 3! =6 different permutations, so that the probability of each permutation is equal to 1/6, then the number of permutations m must be such that m/27 is equal to 1/6, and obviously, no such integer is acceptable. In fact, the probability of each permutation is as follows. For example, the probability of {1,2,3} is 4/27, not 1/6.
| Rows of columns | Any rate |
|---|---|
| < 1, 2, 3 > | 4/27 |
| < 1, 3, 2 > | 5/27 |
| 3 > < 2, 1, | 5/27 |
| < 2, 3, 1 > | 5/27 |
| < 3, 1, 2 > | 4/27 |
| < 3, 2, 1 > | 4/27 |
2. Select a number at random
Given a stream of integers of unknown length, how do we randomly select a number? (Randomness means that each number has the same probability of being picked.)
Solution 1: If the data stream is not very long, it can be stored in an array and then randomly selected from the array. Of course they’re talking about unknown length, so this solution has limitations if the length is too large to be stored in memory.
Solution 2: If the data stream is very long, we can do this:
- If the data flow ends after the first digit, the first digit is required.
- If the data stream ends after the second number, then the probability that we pick the second number is 1/2, and we replace the previous random number with the second number with a probability of 1/2 to get a new random number.
- .
- If the data stream ends after the NTH digit, the probability that we select the NTH digit is 1/n, that is, we replace the previously selected random number with the NTH digit with a probability of 1/n to obtain a new random number.
An easy way to do this is to use the random function f(n)=bigrand()%n, where Bigrand () returns a large random integer. When the data stream reaches the NTH number, if f(n)==0, it replaces the previously selected random number, ensuring that each number is selected with a probability of 1/n. For example, when n=1, f(1)=0, the first number is selected; when n=2, the probability of the second number being selected is 1/2; and so on, when the number length is N, the probability of the NTH number being selected is 1/n. The rand() function already returns a large random number on Linux/MacOS, just like bigrand()) :
void randomOne(int n)
{
int i, select = 0;
for (i = 1; i < n; i++) {
int rd = rand() % n;
if(rd == 0) { select = i; }}printf("%d\n", select);
}
Copy the code3. Select M numbers randomly
The program input contains two integers m and n, where m
Solution 1: Consider a simple example. When m=2 and n=5, we need to select two ordered integers from 0 to 4 with medium probability and cannot repeat them. If we use the following criteria: Bigrand () % 5 < 2, then we have a 2/5 chance of picking 0. But we can’t pick 1 with the same probability, because if we pick 0, we should pick 1 with a 1/4 probability, and if we don’t pick 0, we should pick 1 with a 2/4 probability. The pseudocode selected is as follows:
select = m
remaining = n
for i = [0, n)
if (bigrand() % remaining < select)
print i
select--
remaining--
Copy the codeAs long as the condition m<=n is satisfied, the program outputs m ordered integers, no more, no less. It’s not going to do more than one, because every time I pick a number, SELECT –, I’m not going to do any more select when I get to zero. And it’s not going to be less, because every time remaining, when the select/remaining is equal to 1, it’s going to pick something. The probability of each subset being selected is equal. For example, there are C(5,2)=10 subsets, such as {0,1}, {0,2}… And so on, each subset has a 1 in 10 chance of being selected.
For a more general derivation, there are C(n,m) subsets of n choose M. Consider a particular sequence of m, such as 0… M-1, then the probability of selecting it is m/n * (m-1)/(n-1)*…. 1/(n-m+1)=1/C(n,m), and you can see that the probabilities are equal.
Grandpa Knuth proposed this algorithm very early, and his implementation is as follows:
void randomMKnuth(int n, int m)
{
int i;
for (i = 0; i < n; i++) {
if ((rand() % (n-i)) < m) {
printf("%d ", i); m--; }}}Copy the codeSolution 2: You can also use the idea of randomly arranging the array in front. First, arrange the first M numbers randomly, and then sort the m numbers and output it. The code is as follows:
void randomMArray(int n, int m)
{
int i, j;
int *x = (int *)malloc(sizeof(int) * n);
for(i = 0; i < n; i++) x[i] = i; // Random number groupfor(i = 0; i < m; i++) { j = randInt(i, n-1); swapInt(x, i, j); } // Sort the first m elementsfor (i = 0; i < m; i++) {
for(j = i+1; j>0 && x[j-1]>x[j]; j--) { swapInt(x, j, j-1); }}for (i = 0; i < m; i++) {
printf("%d ", x[i]);
}
printf("\n");
}
Copy the code4. Rand7 Generates rand10 problems
Given that a function rand7() can generate random numbers from 1-7 with equal probability for each number, give a function rand10() that can generate random numbers from 1-10 with equal probability for each number.
Solution 1: To generate random numbers 1-10, we either run RAND7 () twice or simply multiply a number to get the range value we want. As shown in formulas (1) and (2) below.
Independence idx = 7 * (rand7 () - 1) + rand7 () - (1) correct independence idx = 8 * rand7 () - 7 - (2) errorsCopy the codeFormula (1) above can generate random numbers from 1 to 49, why? Since the possible values of RAND7 () are 1-7, two RAND7 () may produce 49 combinations, which are exactly the 49 numbers 1-49, and the probability of each number is 1/49, so we can discard the ones greater than 40, and then take (IDX-1) % 10 + 1. Formula (2) is wrong because it produces numbers with unequal probability and does not produce 49 numbers.
1 2 3 4 5 6 7 8 9 10 1 4 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 * * 7 * * * * * * *Copy the codeThe solution is based on a method called rejected sampling. The main idea is to generate a random number within the target range, then directly return. If the generated random number is not in the target range, the value is discarded and re-sampled. Since the numbers in the target range are equally likely to be selected, such a uniform distribution is generated. The code is as follows:
int rand7ToRand10Sample() {
int row, col, idx;
do {
row = rand7();
col = rand7();
idx = col + (row-1)*7;
} while (idx > 40);
return 1 + (idx-1) % 10;
}
Copy the codeSince row ranges from 1-7 and COL ranges from 1-7, the IDX values range from 1-49. Values greater than 40 are discarded, leaving numbers in the range 1-40 that are returned by modulo. Let’s calculate the expected number of samples needed to get a number in the range 1-40:
E(# calls to rand7) = 2 * (40/49) +4 * (40/49) + 6 (9/49) * * 2 * (40/49) (9/49) +... Up = ∑ 2 k * * (40/49) (9/49) k - 1 k = 1 = (80/49) = 2.45/9/49 (1 -) 2Copy the codeSolution 2: The above method takes about 2.45 calls to rand7 to get a number in the range 1-10, which can be optimized again. For numbers greater than 40, we don’t have to discard them immediately. We can subtract 40 from the numbers 41-49 to get a random number from 1-9, while RAND7 generates a random number from 1-7 to generate a random number from 1-63. We can directly return 1-60 and discard 61-63, so that only 3 numbers need to be discarded. Compared with the previous 9, the efficiency is improved. For numbers 61-63, minus 60 to 1-3, RAND7 produces 1-7, which can be reused to produce numbers 1-21. For numbers 1-20 we return directly, and for numbers 21 we discard. At this point, the number of discarded is only 1, optimization is further. Of course, the number of calls to RAND7 has also increased. The code is as follows, and the optimized expectation is about 2.2123.
int rand7ToRand10UtilizeSample() {
int a, b, idx;
while (1) {
a = randInt(1, 7);
b = randInt(1, 7);
idx = b + (a-1)*7;
if (idx <= 40)
return 1 + (idx-1)%10;
a = idx-40;
b = randInt(1, 7);
// get uniform dist from 1 - 63
idx = b + (a-1)*7;
if (idx <= 60)
return 1 + (idx-1)%10;
a = idx-60;
b = randInt(1, 7);
// get uniform dist from 1-21
idx = b + (a-1)*7;
if (idx <= 20)
return1 + (idx-1)%10; }}Copy the code5. Interesting probability questions
1) Weighing the ball problem
There are 12 balls, one of which is a bad ball. You are given a scale that requires you to weigh it the least number of times to determine which ball is broken and whether it is lighter or heavier.
Solution: We have summarized the binary search algorithm before, we know that binary search can speed up the search of ordered arrays. Similarly, in a number game, for example, if you were asked to guess a number between 1 and 64, you would be sure to guess it in six times using dichotomy. But the sphere-balancing problem is different. Let’s call the ball problem there are 12 balls, and the bad ball could be any one of them, so there’s 12 possibilities. And the bad ball could be heavy or light, so there are 12*2 = 24 possibilities. Each time, the balance can output three possibilities: balance, left weight and right weight. In other words, the possibility of a problem can be reduced to 1/3 by weighing once, so a total of 24 possibilities can be weighed in three times (3^3 = 27).
Why is the most intuitive way to call it6 -Not optimal? in6 -When you weigh it, the probability of balance is zero, and the optimal strategy would be to make the balance equally likely each time it is weighed, so that all the possibilities of the answer are equally divided.
How to implement it? Number the balls 1-12 and use the method of 4 and 4 weights.
- We will first
1 2 3 4和5 6 7 8Carry out the first weighing. - If you balance the first time, the bad ball is definitely there
9-12The number. Then you’re left with only9-12Four balls, the probability is zero9-10-11-12-9 + 10+ 11+ 12+These 8 possibilities. The following will9 10 11和1 2 3Call the second time: if equilibrium, then12No. 1 ball is a bad ball. Weigh no. 12 ball and No. 1 ball for the third time to confirm whether they are light or heavy. If it is not balanced, if it is heavy, it means that the bad ball is heavy. Continue to weigh the 9 and 10 balls. The heavy ball is the bad ball, and the balanced ball is 11. - If the first time is not balanced, the bad ball must be in
1-8 -The number. The remaining possibilities are 11+ 2+ 3+ 4+ 5- 6- 7- 8-orOne, two, three, four, five, six, seven, eightIf it is1 2 3 4If it’s heavy on this side, it can be1 2 6和3, 4, 5If it’s balanced, it must be7 8If it is lighter, weigh 7 and 1 again, then you can determine which 7 and 8 is the bad ball. If it’s not balanced, let’s say it’s1 2 6If this side is heavy, you can tell1 2The weight or5Lighter. Why is that? Because if it is3 + 4 + 6 -,1 2 3 4比5 6 7 8Heavy, but1 2 6Should be better than3, 4, 5Light. In other cases, you can find the bad ball at most 3 times.
The diagram below illustrates the principle more clearly.
2) Boys and girls
What is the ratio of boys to girls in countries where boys are preferred? In a country where boys are preferred, every family wants to have a boy, and if they have a girl, they have another one until they have a boy. What would be the ratio of boys to girls in such a country?
Solution: 1:1 again. For all first-born children, the male-to-female ratio is 1:1; For all second children born, the male-to-female ratio is 1:1; . For every NTH child born, the ratio is still 1:1. So the total ratio of men to women is 1:1.
3) Dating problems
Question: two people make an appointment at 5 to 6 o ‘clock in a place to meet, the first to wait for 20 minutes to leave, the probability of these two people can meet.
Solution: set respectively in the 5 X points and 5 Y to arrive, then they can meet the condition that | x-y | < = 20, while the scope for S = {(X, Y) : 0=< x <= 60, 0=< y <= 60}, if the axis is drawn, the situation is the area represented by the axis, probability is (60^ 2-40 ^2) / 60^2 = 5/9.
4) Hat problem
There are n customers. Each of them gives a hat to the waiter, who returns it to the customer in a random order. What is the expected number of customers who get their hat?
Solution: It is easier to solve the problem using indicated random variables. Let’s define a random variable X as equal to the number of customers who can get their hats, and we want to calculate E[X]. For I =1, 2… N, define Xi =I {customer I gets his hat}, then X=X1+X2+… Xn. Since the order of returning hats is random, the probability of each customer getting his hat is 1/n, i.e. Pr(Xi=1)=1/ N, thus E(Xi)=1/ N, so E(X)=E(X1 + X2 +… Xn)= E(X1)+E(X2)+… E(Xn)=n*1/n = 1, that is, about 1 customer can get his hat.
5) The birthday Paradox
How many people must there be in a room for two people to have the same birthday?
Solution: Define the indicator variable Xij= {I and J have the same birthday} for each pair (I, j) of people in room K, then Xij=1 if I and J have the same birthday, otherwise Xij=0. The probability of two people having the same birthday Pr(Xij=1)=1/n. If (X)=E(∑ki=1∑ KJ = I +1Xij) = C(k,2)*1/n = K (k-1)/2n, let k(K-1)/2n >=1, k>=28, that is, there must be at least 28 people, Can expect two people to have the same birthday.
6) Probability inverse problem
Question: If the probability of seeing a car pass in 30 minutes on the motorway is 0.95, what is the probability of seeing a car pass in 10 minutes? (Assuming constant probability)
Solution: If the probability of seeing a car pass in 10 minutes is x, then the probability of not seeing a car pass is 1-x, and the probability of not seeing a car pass in 30 minutes is (1-x)^3, which is 0.05. So we get the equation (1-x)^3 = 0.05, and solving the equation gives us x is about 0.63.
Data Structures and Algorithms interview questions series – Summary of recursive algorithms
Summary of 0.
In front of the summary of random algorithm, this time to write the recursive algorithm before the article combing, this article is mainly inspired by the teacher Song Jinsong wrote “Linux C programming” recursive chapter. The most can reflect the essence of the algorithm is not recursion, I hope this article to learn recursion or recursion confused friends can help, if there is a mistake, also ask all the cattle correct. See the binary_tree directory in the repository for recursion examples of binary trees, and the rest of the code in this article.
1. Preliminary study on recursive algorithm
This section of content is mainly extracted from “Linux C one-stop programming”, the author is Song Jinsong teacher, this is I think currently see one of the best technical books on Linux C programming, strongly recommended!
A simple example of recursion is taking the factorial of integers, n! =n*(n-1)! , zero! = 1. The following recursive program can be written:
int factorial(int n)
{
if (n == 0)
return 1;
else {
int recurse = factorial(n-1);
int result = n * recurse;
returnresult; }}Copy the codeFactorial is a recursive function that calls itself. A recursive function is a function that calls itself directly or indirectly. If confused, think of the factorial(n-1) step as calling another function – another function with the same name and the same code – jumping into its code and then returning to the next step of the factorial(n-1) call.
To prove the correctness of the recursive algorithm, we can follow the results step by step. I remember when I just learned recursive algorithms, THERE is always a feeling of confusion, always thinking of recursion step by step to see the results of execution. It’s okay to have fewer levels of recursion, but if you have more levels of recursion, you have no idea what level of recursion you’re following. For example, factorial, if it’s just factorial of 3 that’s not a big problem, but if it’s factorial of 100 that’s really annoying.
In fact, we don’t need to follow every function to see the result. For example, when we call printf in our own function, we don’t drill in to see how it prints because we trust it to do the job. We write the factorial function as follows:
int recurse = factorial(n-1);
int result = n * recurse;
Copy the codeAt this point, if we believe factorial is correct, passing n-1 it will return n-1 factorial. , then the result = n * (n – 1)! =n! So this is factorial of n.
Of course this is a little odd: we haven’t written factorial yet, why should we believe factorial is correct? If you believe that the recursive function you are writing is correct, call it, and then write the recursive function based on that, then it will be correct and therefore worth believing that it is correct.
It’s a little tricky, but let’s prove factorial mathematically rigorously. Well, the correctness of factorial depends on the correctness of factorial of n-1, and as long as factorial is correct, there is no doubt that it will return the result multiplied by n, then our implementation is correct. So to prove factorial is to prove factorial of n-1, and in the same way to prove factorial of n-1 is to prove factorial of n-2, and so on, and so on, and so on, and finally: And to prove factorial of 1 is to prove factorial of 0. The correctness of factorial(0) does not depend on the other function call. It is a small branch of the program. This one that we wrote according to the definition of factorial, must be correct, so the implementation of factorial 1 is correct, so factorial 2 is correct, and so on, and factorial n is correct.
In fact, this is the mathematical induction that I learned in middle school. To prove by mathematical induction, I only need to prove two points: correct Base Case and correct recursion relationship. Remember to write Base Case when writing a recursive function, otherwise even if the recursion is correct, the whole function is not correct. If the factorial function misses the Base Case, it will loop indefinitely.
2. Recursive classical problems
From our discussion of a simple example of factorial in the previous section, we learned the essence of recursive algorithms: to understand functions functionally, you need to believe that the function you are writing is correct, call it on that basis, and it will be correct. So here’s how to understand recursion from a couple of common algorithms, and here’s what I think, and I welcome better ideas.
2.1) Hannotta problem
The hannott tower problem is A common problem in which n plates of different sizes are placed on top of tower A, in bottom-up order from largest to smallest. It is required that all n plates be moved to another tower C, with the aid of one tower B, but that large plates cannot be placed on small plates at any time.
Solution: The basic idea is to move n-1 plates from the top to B through C, then move the bottom plate to C, and then move n-1 plates from the top of B to C through A. The total time complexity f(n)=2f(n-1)+1, so f(n)=2 to the n-1.
/** ** / void hano(char a, char b, char c, int n) {if (n <= 0) return;
hano(a, c, b, n-1);
move(a, c);
hano(b, a, c, n-1);
}
void move(char a, char b)
{
printf("%c->%c\n", a, b);
}
Copy the code2.2) Find the depth of binary tree
The depth here refers to the maximum height of the binary tree from the root to the leaf. For example, if there is only one node, the depth is 1, and if there are N layers, the height is N.
int depth(BTNode* root)
{
if (root == NULL)
return 0;
else{ int lDepth = depth(root->left); Int rDepth = depth(root->right); // Get the right subtree depthreturnlDepth>rDepth? lDepth+1: rDepth+1; // the depth of the binary tree is +1.Copy the codeSo how do we understand depth functionally? We know that the purpose of this function is to find the depth of the binary tree, which means that if we do depth, depth(root) will return the correct depth of the binary tree at root. So in our code depth(root->left) returns the depth of the left subtree, and depth(root->right) returns the depth of the right subtree. Although we haven’t finished writing depth at this point, we believe that depth will do the job correctly. So we get lDepth and rDepth, and then by comparison return the larger value plus 1 as the depth of the binary tree.
If this is confusing, imagine that the function depth(root->left) called in depth is another function with the same name that does the same thing. In Base Case, when root==NULL, the depth is 0 and the function returns 0.
2.3) Judge whether the binary tree is balanced
A balanced binary tree is one where the depth difference between the left and right subtrees of any node is no more than 1. To determine whether a binary tree is balanced, a recursive algorithm can be used.
int isBalanceBTTop2Down(BTNode *root)
{
if(! root)return 1;
int leftHeight = btHeight(root->left);
int rightHeight = btHeight(root->right);
int hDiff = abs(leftHeight - rightHeight);
if (hDiff > 1) return 0;
return isBalanceBTTop2Down(root->left) && isBalanceBTTop2Down(root->right);
}
Copy the codeRoot is a balanced binary tree, that is, the depth difference between the left and right subtrees of all nodes is not greater than 1. First check whether the root satisfies the condition. If not, return 0. If yes, we need to determine whether the left and right subtrees are both balanced binary trees, if they are both, return 1, otherwise 0.
2.4) Permutation algorithm
The permutation algorithm is also a good example of recursion. I remember when I first looked at the layer upon layer of code, the head was big, but now it’s really much easier to understand from a functional point of view. First look at the code:
Void permute(int a[], int k, int n) {void permute(int a[], int k, int n) {if (k == n-1) {
printIntArray(a, n); // Output array}else {
int i;
for(i = k; i < n; i++) { swapInt(a, i, k); // permute(a, k+1, n); SwapInt (a, I, k); // Restore the original sequence}}}Copy the codeThe perm(a, k, n) function outputs all permutations of array A starting at position K, with array length n. So when we call our program, we call perm(a, 0, n), which is all permutations of the output array starting at position 0, which is all permutations of the array. The base condition is k==n-1, the last element has been reached, the permutation has been completed, and the output is direct. Otherwise, each element starting at position K swaps with the value of position K (including itself), and then goes through the next permutation, remembering to restore the original sequence when it’s done.
If the array a aan na a =3, then the program calls perm(a, 0, 3) : Swap 0, 0 for the first time and execute perm(a, 1, 3). Swap 0, 0 again and the array is restored to its original value. Perm (a, 1, 3) is executed. When the array is finished, swap 1, 0 again, and the array is restored to its original value. Swap 2,0 for the third time and execute perm(a, 1, 3). Swap 2,0 and restore the array to its original value.
That is, functionally, we first determine the 0th position and then call perm(a, 1, 3) to print all permutations starting with 1. The possible value of the 0th position is a[0], a[1],a[2]. This ensures the possible value of the 0th position by swapping. Remember to restore the initial value after each swap.
If a={1,2,3}, then the output of the program is: 1 2 3, 1 3,2 1 3,2 3 1, 3 1 2. That is, the permutation of the first value in order 1 is printed, followed by the permutation of the first value in order 2 and 3.
2.5) Combination algorithm
The combinatorial algorithm can also be implemented recursively, but it is similar to the 0-1 knapsack problem. So either you pick it or you don’t pick it, and you don’t pick repeated numbers. The complete code is as follows:
Void combination(int a[], int n) {int *select = (int *)calloc(sizeof(int), n); // select an auxiliary array to store the selected number int k;for(k = 1; k <= n; k++) { combinationUtil(a, n, 0, k, select); / / void combinationUtil(int a[], int n, int I, int k, int *select) {/ / void combinationUtil(int a[], int n, int I, int k, int *select) {if (i > n) return; // If the location is outside the range of the array, it will return a segment errorif(k == 0) {// Select the selected number int j;for (j = 0; j < n; j++) {
if (select[j])
printf("%d ", a[j]);
}
printf("\n");
} else{ select[i] = 1; combinationUtil(a, n, i+1, k-1, select); Select [I] = 0; select[I] = 0; combinationUtil(a, n, i+1, k, select); Int I +1; int I +1; int I +1;Copy the code2.6) Print the string in reverse order
This is relatively simple, the code is as follows:
void reversePrint(const char *str)
{
if(! *str)return;
reversePrint(str + 1);
putchar(*str);
}
Copy the code2.7) Reverse linked list
List inversions are usually implemented iteratively, but if you want to be a bit different, you can use recursion, as shown in the asList directory of the repository.
/** * list in reverse order, recursive implementation. */ ListNode *listReverseRecursive(ListNode *head) {if(! head || ! head->next) {return head;
}
ListNode *reversedHead = listReverseRecursive(head->next);
head->next->next = head;
head->next = NULL;
return reversedHead;
}
Copy the codeData Structures and Algorithms interview questions series – Summary of backpack questions
Summary of 0.
Knapsack problem includes 0-1 knapsack problem, complete knapsack problem, partial knapsack problem and so on. Among them, the simplest is partial knapsack problem, which can be solved by greedy method, while other knapsack problems often need dynamic programming to solve. This article mainly comes from “knapsack problem nine lectures”, I chose the relatively simple 0-1 knapsack problem and complete knapsack problem for summary. At the same time gives the implementation code, if there is an error, please point out the shrimp. The code for this article is here.
1. Part of the backpack problem
There are N items and a backpack of capacity C. The ith item has a weight w[I] and a value V [I]. Figure out which items to pack into the backpack maximize the sum of values. Note that you don’t want to load the whole thing, you can load only parts of an item.
Solution: Part of the backpack problem is often solved by a greedy algorithm that calculates the value per unit weight of each item v[I]/ W [I], then starts with the item with the largest unit value, and then takes the item with the second largest value until the backpack is full. Following this greedy strategy is bound to get the maximum sum of values, which is relatively simple, the implementation code will be omitted.
2. 0-1 backpack problem
0-1 Backpack problem description
There are N items and a backpack of capacity C. The ith item has a weight w[I] and a value V [I]. Figure out which items to pack into the backpack maximize the sum of values. Note that items can only be taken or not taken, which is what 0-1 is all about. You can think of the partial backpack problem as taking gold dust, and the 0-1 backpack problem as taking gold nuggets, one divisible, one divisible.
Analysis of the
This is the most basic backpack problem, characterized by: each item has only one, you can choose to put or not put. State is defined by subproblem: f[I][W] represents the maximum value that can be obtained by putting the first I items into a backpack of capacity C. Then its state transition equation is:
f[i][c] = max{f[i-1][c], f[i-1][c-w[i]]+v[i]}
Copy the codeThis equation is so important that almost all backpack related problems derive from it. So it’s worth explaining it in detail: the subproblem of putting the former I-item in a backpack of capacity C can be transformed into a problem involving only the former I-1 item if only the strategy for the i-item (putting or not putting) is considered.
- If item I is not placed, then the problem is converted to
The first I-1 item is placed in a backpack of capacity V, the value off[i-1][c]; - If I put item I, then the problem is converted to
The first I-1 item goes into the remaining c-W [I] backpackThe maximum value that can be gained isf[i-1][c-w[i]]Plus the value v[I] gained by putting in the ith item.
Optimizing spatial complexity
Both the time and space complexity of the above methods are O(CN), where the time complexity can no longer be optimized, but the space complexity can be optimized to O(N). F [I -1][c] and f[I -1][c-w[I]] can be stored in a one-dimensional array. The trick here is to change the values of f[I][c] from c= c… 0 starts backwards, so that f[c-w[I]] is guaranteed to store the value of f[i-1][c-w[I] when evaluating f[c]. Note that this cannot be done from c=0… C =C…w[I] C =C…w[I]
fori=0.. N-1forc=C.. w[i] f[c]=max{f[c],f[c-w[i]]+v[i]};Copy the codeThe final implementation code is as follows:
int knap01(int N, int C, int w[], int v[])
{
int *f = (int *)calloc(sizeof(int), C+1);
int i, c;
for (i = 0; i < N; i++) {
for (c = C; c >= w[i]; c--) {
f[c] = max(f[c], f[c-w[i]] + v[i]);
}
printf("%d: ", i+1);
printIntArray(f, C+1); // Print f array}return f[C];
}
Copy the codeThe test results are as follows: pack the 1st and 2nd items (indexed from 0) with a backpack capacity of 10, total weight of 4+5=9, and maximum value of 5+6=11.
Parameter: w = [3, 4, 5] // Item weight list V = [4, 5, 6] // Item value list C = 10 Result (print array f, I is the selected item index, C is the backpack weight, value is the backpack item value) : i/c 0 1 2 3 4 5 6 7 8 9 10 0: 0 0 0 4 4 4 4 4 4 4 4 1: 0 0 0 4 5 5 5 9 9 9 9 2: 0 0 0 4 5 6 6 9 10 11 11 KNap01 max: 11Copy the codeInitialization details
In the knapsack problem that we’ve seen for optimal solutions, there are actually two very different ways of asking. Some problems ask for the optimal solution when the backpack is exactly full, while others don’t ask for the backpack to be full. One difference between the two methods is that they are implemented differently at initialization.
If the first method requires that the backpack is exactly full, then f[1..C] except f[0] is 0 at initialization and all f[1..C] is set to -∞, so that the final f[N] can be guaranteed to be an optimal solution that is exactly full of backpack. If you do not require the backpack to be full, but want the price to be as high as possible, you should set f[0..C] all to 0 when initializing.
Why is that? To put it this way: the initialized F array is actually the legal state when nothing can be put into the backpack. If the backpack is exactly full, then only the backpack with the capacity of 0 can be “just full” of something with the value of 0, and the backpack with the other capacity has no legal solution and belongs to the undefined state, and their value should be -∞. If the backpack does not have to be full, then the backpack of any size has a legal solution of “nothing,” which has a value of zero, so the initial state values are all zero.
3. Complete knapsack problem
Problem description
There are N items and a backpack of capacity C, with an infinite number of items for each item. Item I has a weight of W [I] and a value of V [I]. Figure out which items to put into the backpack so that the total weight of the items does not exceed the backpack capacity, and the total value of the items can not be only partial.
The basic idea
This problem is very similar to the 0-1 backpack problem, except that there are an infinite number of items per item. That is, from the point of view of each item, the strategy associated with it is no longer take or not take two, but take 0, take 1, take 2… And so on. If still according to the solution 01 knapsack thought, let f[I][c] represents the former I items exactly into a backpack capacity of C maximum weight. You can still write the state transition equation for each item with a different strategy, like this:
f[i][c] = max{f[i-1][c-k*w[i]]+ k*w[i]| 0<=k*w[i]<=c }
Copy the codeThere are O(CN) states to solve, but the time to solve each state is no longer constant. The time to solve the state F [I][C] is O(C /w[I]). The total complexity can be considered as O(CN* σ (C/W [I])), which is relatively large. The implementation code is as follows:
Int knapComplete(int N, int C, int w[], int v[]) {int *f = (int *)calloc(sizeof(int), C+1); int *f = (int *)calloc(sizeof(int), C+1); int i, c, k;for (i = 0; i < N; i++) {
for (c = C; c >= 0; c--) {
for(k = 0; k <= c/w[i]; k++) { f[c] = max(f[c], f[c-k*w[i]] + k*v[i]); }}printf("%d: ", i+1);
printIntArray(f, C+1);
}
return f[C];
}
Copy the codeUsing the same example as the 0-1 knapsack problem, the result of running the program is as follows. The maximum value is 13, that is, two items weighing 3 and one weighing 4 are selected for the highest total value, which is 4*2 + 5 = 13.
i/c: 0 1 2 3 4 5 6 7 8 9 10
0: 0 0 0 4 4 4 8 8 8 12 12
1: 0 0 0 4 5 5 8 9 10 12 13
2: 0 0 0 4 5 6 8 9 10 12 13
KNapComplete max: 13
Copy the codeConvert to 0-1 knapsack problem
Since 01 knapsack problem is the most basic knapsack problem, then we can consider the complete knapsack problem into 01 knapsack problem to solve. The simplest idea is to convert item I into item C/ W [I], which has the same cost and value, given that item I can choose at most C/ W [I], and then solve the 01 backpack problem. This doesn’t improve the time complexity of the basic idea at all, but it does give us the idea of turning the full knapsack problem into the 01 knapsack problem: breaking one item into multiple items.
A more efficient conversion method is to disassemble the i-th item into several articles of weight W [I]*2^ K and value W [I]*2^ K, where K satisfies w[I]*2^k<=C. This is the binary idea, because no matter how many ith items are chosen by the optimal strategy, it can always be represented as a sum of 2 to the k items. This is a big improvement in breaking each item into order (log C/w[I]) pieces. But we have a better algorithm for O(CN).
The — O(CN) solution was further optimized
We can use the reverse order of traversal to solve the 0-1 knapsack problem, so as to obtain the O(CN) solution, the pseudo-code is as follows:
fori=0.. N-1forc=w[i].. C f[c]=max{f[c],f[c-w[i]]+v[i]};Copy the codeThis pseudocode differs from the 0-1 knapsack pseudocode only in the loop order of C. The reason why 0-1 knapsack is based on v=V.. Zero in reverse order to loop. This is because state F [I][c] in loop I is guaranteed to be recursively derived from state F [i-1][c-w[I]]. In other words, this is to ensure that each item is selected only once, and that the “pick i-in” strategy is considered based on a subresult f[i-1][C-W [I]] that has never already selected i-in. Now the characteristic of the complete backpack is exactly that each item can be selected unlimited, so when considering the strategy of “adding an item of the I”, it needs a subresult f[I][c-w[I]] that may already be selected into the I item, so c=w[I] can and must be used. The sequential cycle of C. That’s how this simple program works. The implementation code is as follows:
*/ int knapCompleteLike01(int N, int C, int w[], int v[]) {int *f = (int *)calloc(sizeof(int), C+1); int i, c;for (i = 0; i < N; i++) {
for (c = w[i]; c <= C; c++) {
f[c] = max(f[c], f[c-w[i]] + v[i]);
}
printf("%d: ", i+1);
printIntArray(f, C+1);
}
return f[C];
}
Copy the codeData Structures and Algorithms interview questions series – Summary of numerical questions
Summary of 0.
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. The end of factorial contains 0 problem
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 code4. A sequence of positive integers whose sum is 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 code6. Maximum 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 codeSeries of articles
- Data Structures and Algorithms – C Pointers, arrays, and structures
- 1. Data Structures and Algorithms — Strings
- 2. Data Structures and Algorithms — Linked lists
- 3. Data structures and algorithms
- 4. Data Structures and Algorithms — Binary heap
- 5. Data Structures and Algorithms — Binary Tree Basics
- 6. Data Structure and Algorithm interview questions series — Binary tree interview questions summary
- 7. Data structures and Algorithms — Binary search algorithm
- 8. Data Structures and Algorithms interview questions series — The basics of sorting algorithms
- 9. Data Structures and Algorithms interview questions series — Quicksort sorting algorithms
- 10. Data Structures and Algorithms interview Questions series — Summary of Random Algorithms
- 11. Data Structures and Algorithms – Summary of Recursive algorithms
- 12. Data Structures and Algorithms interview Questions series – Summary of backpack questions
- 13. Data Structures and Algorithms – Summary of number questions
other
In addition, there are also docker related technical notes, MIT6.828 operating system learning Notes, Python source code analysis notes and other articles in my Jane book blog. Please correct them.
The resources
- Programming Abecas 2nd edition Chapter 9
- Rotate the binary lookup of the array
- Introduction to Algorithms
- Merge sort (recursive implementation + non-recursive implementation + natural merge sort) – geeker
- Data Structures and Algorithms -C language implementation
- Implement Rand10() Using Rand7() – LeetCode Articles
- The beauty of mathematics set pieces: why so fast fast row – liu peng not | Mind Hacks
- Google interview questions compiled online
- Jinsong “Linux C programming” recursion chapter
- Data structure and algorithm -C language implementation
- Backpack problem nine lectures
- The beauty of the programming
- The concrete mathematical
- Microsoft, Google, etc
- Reverse Bits – LeetCode
I recruit a cover the campaign in digging in the autumn, the autumn for full details of job searching, with a gifts | the nuggets skill in writing essay
