preface
As a veteran rookie for many years, I have arranged this data structure and algorithm interview questions series, feeling the style of “interview building aircraft carrier, work screw” in most companies. For campus recruitment, if you don’t have much practical/internship experience, large companies tend to like to examine data structures and algorithms. For example, Microsoft especially likes to write algorithm questions in the campus recruitment, and the difficulty is not small, I also suffered a lot when LOOKING for a job after graduation.
It has been more than a month since the first article was finished. After the diligent urging of @nuggets – Yuzu Grapefruit tea, it is basically finished today. Nearly a month of spare time in this above, in addition to the integration of the blog, but also the code re-entry and testing, cost a lot of energy. The main sources of this series include: Introduction to Algorithms, Programming Pearls, Data Structures and Algorithms -C Language Implementation, and interview questions are mostly from LeetCode, Geeksforgeeks, the Beauty of Programming, etc.
The blog series named Data Structure and Algorithm interview questions series is my summary of data structure and algorithm when I was looking for a job six years ago, including basic parts and classic interview questions of various companies, which was first published on CSDN. Since the previous blog post was messy and didn’t unify the implementation code, it seemed like a lot of inconvenience. Is sorted out for a series of friends in need of reference. 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. The total number of articles in the series is up to 40,000 words, so we also integrate the two articles for you to have the need of small friends, if this series of help you, welcome to like or on github star✨✨, thank you very much.
Data Structures and Algorithms – C Pointers, arrays, and structures
Summary of 0.
When using C language to realize some common data structures and algorithms, C language foundation can not be less, especially Pointers and structures and other knowledge.
1. About ELF files
Object files and executables compiled by C in Linux are ELF format. Executables are divided by segments, and object files are divided by sections. A segment contains one or more sections. You can see the complete section and segment information using the readelf command. Look at a chestnut 🌰 :
char pear[40];
static double peach;
int mango = 13;
char *str = "hello";
static long melon = 2001;
int main()
{
int i = 3, j;
pear[5] = i;
peach = 2.0 * mango;
return 0;
}
Copy the codeThis is a simple C language code, now analyze the location of each variable storage. Mango, melon and Peach belong to the data section, and pear and Peach belong to the common section. Peach and melon are added static, indicating that they can only be used in this file. The string “HelloWorld” corresponding to STR is stored in the RoData section.
The main function belongs to the Text section, and the local variables I and j in the function allocate space on the stack at run time. Note that the global uninitialized variables peach and Pear are in the common section for strong and weak symbols. That actually ends up in the BSS segment when the link becomes an executable. Similarly, the text section and the Rodata section belong to the same segment in the executable.
For more ELF content, see The Self-Cultivation of the Programmed Ape.
Pointer to 2.
Think that the most afraid of learning C language is pointer, of course, “C and pointer” and “C expert programming” and “high quality C programming” in the face of pointer have a very good explanation, system review or reading bar, here I summed up some basic and easy to wrong points. The environment is ubuntu14.10 32-bit system, compilation tool GCC.
2.1 Error point of pointer
1 demo1.c ***/ intmain()
{
char *str = "helloworld"; //[1]
str[1] = 'M'; //[2] char arr[] ="hello"; //[3]
arr[1] = 'M';
return 0;
}
Copy the codeIn demo1.c, we define a pointer and an array to point to a string, and then modify the value of a character in the string. After compiling, we will find an error at [2]. Why? Generating assembly code with the command gcc-s demo1.c shows that helloWorld at [1] is stored in the Rodata section and is read-only, while helloWorld at [3] is stored on the stack. So [2] reported an error and [3] normal. In C, string constants are created as in [1] and assigned to Pointers, and string constants are stored in the Rodata section. If the assignment is to an array, it is stored on the stack or in the data section (as in [3]). Take a look at example 2, which shows more error prone points.
C ***/ char *GetMemory(int num) {char *p = (char *)malloc(sizeof(char) * num);return p;
}
char *GetMemory2(char *p) {
p = (char *)malloc(sizeof(char) * 100);
}
char *GetString(){
char *string = "helloworld";
return string;
}
char *GetString2(){
char string[] = "helloworld";
return string;
}
void ParamArray(char a[])
{
printf("sizeof(a)=%d\n", sizeof(a)); // sizeof(a)=4, the argument is passed as a pointer} intmain()
{
int a[] = {1, 2, 3, 4};
int *b = a + 1;
printf("delta=%d\n", b-a); // delta=4, note that the int array step is 4printf("sizeof(a)=%d, sizeof(b)=%d\n", sizeof(a), sizeof(b)); //sizeof(a)=16, sizeof(b)=4 ParamArray(a); /* int *p = 0; *p = 17; */ char *str = NULL; str = GetMemory(100); strcpy(str,"hello"); free(str); // free memory STR = NULL; // Avoid wild pointer // error versions because function arguments are passed copies. /* char *str2 = NULL; GetMemory2(str2); strcpy(str2,"hello");
*/
char *str3 = GetString();
printf("%s\n", str3); // Error version, return stack pointer, compiler will have a warning. /* char *str4 = GetString2(); * /return 0;
}
Copy the code2.2 Pointers and Arrays
Partial Pointers and array contents were also mentioned in 2.1. Pointers and arrays can be converted to each other in C under certain circumstances, such as char * STR =” helloWorld “, which can be accessed by STR [1] as the second character, or *(STR +1). In addition, the use of arrays and Pointers in function arguments is equivalent. But Pointers and arrays are not the same in some ways, which requires special attention.
For example, I define an array char a[9] = “abcdefgh”; (note that the string is automatically filled with \0), then the process of reading the character ‘b’ with a[1] looks like this:
- First of all, array A has an address, let’s say 9980.
- We take the offset, which is the index * the size of the element, which is 1, char is also 1, so we add 9980 to 9981, and we get the address of the first element of array A. (If the array is int, the offset is 1 * 4 = 4)
- Take the value at address 9981, which is ‘b’.
So if we define a pointer char *a = “abcdefgh”; , we take the value of the first element by a[1]. Unlike the array flow:
- First, pointer A has an address of its own, let’s say 4541.
- Then, take the value of a from 4541, which is the address of the string “abcdefgh”, let’s say 5081.
- And then we do the same thing we did before, 5081 plus offset 1, 5082, which is b.
As you can see from the above illustration, Pointers have one more step than arrays, although the results appear to be consistent. Therefore, the following mistake is easier to understand. Defining an array in demo3.c and then declaring and referencing it with a pointer in demo4.c is obviously an error. Extern char p[]; Extern char p[3] = extern char p[3] = extern char P [3] = extern char P
/***
demo3.c
***/
char p[] = "helloworld";
/***
demo4.c
***/
extern char *p;
int main()
{
printf("%c\n", p[1]);
return 0;
}
Copy the code3. The typedef and # define
Typedefs and #define are both commonly used, but they are not the same. A typedef can fit multiple declarators, whereas #define generally has only one definition. In a continuous declaration, a typedef defines a type that guarantees that all declared variables are of the same type. #define does not. In addition, a typedef is a completely encapsulated type, and no other types can be added after the declaration. As shown in the code.
#define int_ptr int *int_ptr i, j; // I is an int * and j is an int. typedef char * char_ptr; char_ptr c1, c2; //c1 and c2 are char * types.#define peach intunsigned peach i; Typdef int banana; unsigned banana j; // Error, typedef declares a type that cannot extend other types.Copy the codeIn addition, typedefs are common in structure definitions, such as the one in the following code. It should be noted that [1] and [2] are very different. When you define struct foo as a typedef, as in [1], you define the structure type foo in addition to its own structure tag foo, so you can declare variables directly in foo. As defined in [2], bar cannot be used to declare a variable because it is a structural variable, not a structural type.
It is also important to note that a structure has its own namespace, so it is legal to use fields in a structure with the same name as those in [3]. Structures will be explored in more detail in the next section, as there are many structures available in Python source code as well.
typedef struct foo {int i; } foo; //[1] struct bar {int i; } bar; //[2] struct foo f; // Correct, use the structure tag foo foo f; Struct bar b; // Correct, use the structure tag bar bar b; Bar is already a structure variable and can be initialized directly, such as bar. I = 4; struct foobar {int foorbar; }; //[3] The definition of legalCopy the code4. Structure
Structs are often used when defining linked lists and tree structures when learning about data structures. Like this one:
struct node {
int data;
struct node* next;
};
Copy the codeIt’s kind of weird when you’re defining a linked list, why do you define it like this, it looks like a struct node isn’t defined yet why do you use a next pointer to point to a struct node that’s defined by this structure?
4.1 Incomplete types
Here are some incomplete types in C. C can be divided into function types, object types and incomplete types. Object types can also be classified as scalar types and non-scalar types. Arithmetic types (such as int, float, char, etc.) and pointer types are scalar types, while defining complete structures, unions, arrays, etc., are non-scalar types. An incomplete type is one that does not define a complete type, such as the following:
struct s;
union u;
char str[];
Copy the codeVariables with incomplete types can be combined into a full type by multiple declarations. For example, the following two words declare that the STR array is legal:
char str[];
char str[10];
Copy the codeIn addition, if two source files define the same variable, they can be compiled as long as they are not all strongly typed. For example, the following is legal, but if int I in file1.c; I’m going to make it strong like int I = 5; Then something goes wrong.
//file1.c
int i;
//file2.c
int i = 4;
Copy the code4.2 Incomplete type structure
Struct node *next is an incomplete type, and next is a pointer to an incomplete type. However, when the compiler finds that struct node *next is an incomplete type, Pointers themselves are fully typed, because any pointer takes up four bytes on a 32-bit system. By the end of the definition, the struct node is a full type, so next is a pointer to a full type.
4.3 Structure initialization and size
Structure initialization is relatively simple, but it is important to note that when a structure contains Pointers, if you want to do things like copy strings, you need to allocate extra memory for Pointers. The student variable stu and pointer to the structure pstu are used to assign memory. If you want to copy a string to the memory it points to, you will need to display the allocated memory.
struct student {
char *name;
int age;
} stu, *pstu;
int main() { stu.age = 13; // strcpy(stu.name,"hello"); Stu. name = (char *)malloc(6); strcpy(stu.name,"hello"); / / rightreturn 0;
}
Copy the codeStruct size involves an alignment problem with the following rules:
- The struct variable starts with the widest member length, if any
#pragma pack(n), then take the widest member length and the smaller value of n, default pragma n=8) integer multiple - The structure size is an integer multiple of the length of the widest member
- The offset of each member of the structure relative to the head address of the structure is an integer multiple of the size of each member itself (if there is pragma pack(n), it is the smaller value of n and the size of the member). Therefore, the following structures S1 and S2 have the same contents, but have different fields order and sizes.
Sizeof S1 = 8, sizeof S2 = 12.if defined#pragma pack(2),Sizeof (S1) = 8; sizeof(S2)=8
typedef struct node1
{
int a;
char b;
short c;
}S1;
typedef struct node2
{
char b;
int a;
short c;
}S2;
Copy the code4.4 Flexible Array
A flexible array means that the last member of a structure can be an array of unknown size, so that a variable length string can be stored in the structure. As shown in the code. ** Note that the flexible array must be the last member of the structure. The flexible array does not occupy the size of the structure.** You can also write the array as char STR [0].
Note: In Python, the flexible array declaration does not use an empty array or a char STR [0]. Instead, it uses a char STR [1], that is, the array size is 1. This is because the ISO C standard does not allow arrays of size 0 to be declared (the gcc-pedanti parameter can be checked for ISO C compliance), so you often see arrays of size 1 declared for portability. Of course, many compilers such as GCC use array size 0 as a non-standard extension, so declaring empty or size 0 flexible arrays in GCC will compile normally.
struct flexarray {
int len;
char str[];
} *pfarr;
int main()
{
char s1[] = "hello, world";
pfarr = malloc(sizeof(struct flexarray) + strlen(s1) + 1);
pfarr->len = strlen(s1);
strcpy(pfarr->str, s1);
printf("%d\n", sizeof(struct flexarray)); / / 4printf("%d\n", pfarr->len); / / 12printf("%s\n", pfarr->str); // hello, world
return 0;
}
Copy the code5. To summarize
- Const is not a constant in C, so you cannot define an array using const variables, as in
const int N = 3; int a[N];This is wrong. - Pay attention to memory allocation and freeing, eliminate wild Pointers.
- It is legal to link weak symbols with strong symbols in C.
- Note the difference between Pointers and arrays.
- A typedef is different from #define.
- Note the initialization of the structure containing Pointers and the use of flexible arrays.
Data Structures and Algorithms – Strings
Summary of 0.
As the basic content of data structure, string is also one of the basic skills often examined in interviews, such as the implementation of strcpy, STRCMP and other basic functions, palindrome string, string search, regular expression and so on. See the code for this article here.
1. Basic operations
Let’s start with the implementation of some basic string functions. The following code is taken from the MIT6.828 course.
// String length int strlen(const char *s) {int n;for(n = 0; *s ! ='\ 0'; s++)
n++;
returnn; } char *strcpy(char * DST, const char * SRC) {char *ret; ret = dst;while((*dst++ = *src++) ! ='\ 0') / *do nothing */;
returnret; } char *strcat(char * DST, const char * SRC) {int len = strlen(DST); strcpy(dst + len, src);returndst; } // string comparison int STRCMP (const char *p, const char *q) {while (*p && *p == *q)
p++, q++;
return(int) ((unsigned char) *p - (unsigned char) *q); Char * STRCHR (const char *s, char c) {for (; *s; s++)
if (*s == c)
return (char *) s;
return0; Void *memset(void *v, int c, size_t n) {char *p; int m; p = v; m = n;while (--m >= 0)
*p++ = c;
returnv; Void *memmove(void * DST, const void * SRC, size_t n) {const char *s; char *d; s = src; d = dst;if (s < d && s + n > d) {
s += n;
d += n;
while (n-- > 0)
*--d= * --s;
} else
while (n-- > 0)
*d++ = *s++;
return dst;
}
Copy the code2. String-related interview questions
2.1 Longest callback substring
Given a string, find the longest substring of the string. A palindrome string is a string that looks the same from left to right, aba, CDDC are palindrome strings. The string abbacdc has a substring of abba and CDC, so its longest substring is abba.
An easy mistake to make
At first glance, you might think of something like this: invert the string S to get the new string S’, and then find the longest common substring of S and S’.
- Such as
S = caba.S' = abac, then the longest common substring of S and S’ isabaThis is correct. - But if the
S = abacdfgdcaba.S’ = abacdgfdcaba, then the longest common substring of S and S’ isabacdObviously this is not a palindrome string. So this approach is wrong.
Determines whether a string is a palindrome string
To find the longest substring, you first solve the problem of determining whether a string is a palindrome string. The most obvious way to do this is to set two variables I and j, pointing to the beginning and the end of the string, to see if they are equal, and then I ++, j–, until I >= j. The following code checks whether the string STR [I, j] is a palindrome string, that is, whether the substring STR from I to j is a palindrome string, which will be used later.
*/ int isPalindrome(string s, int start, int end) {for (; start < end; ++start,--end) {
if(s[start] ! = s[end])return 0;
}
return 1;
}
Copy the codeSolution 1: Brute force method to find the largest string
The brute force method evaluates all substrings of a string and, if it is a palindrome string, updates the length of the longest palindrome. Since there may be (1+N)*N/2 substrings of length N, it takes O(N) time to determine each substring, so it takes O(N^3) time to find the longest substring.
O(N^3) */ string longestPalindrome(string s) {int len = s.length(), maxLen = 1; int start=0, i, j; /* Traverses all substrings of the string, updating the length of the longest palindrome if the substring is a palindrome string */for (i = 0; i < len - 1; i++) {
for (j = i + 1; j < len; j++) {
ifInt pLen = j - I + 1; int pLen = j - I + 1; int pLen = j - I + 1;if(pLen > maxLen) { start = i; // Update the longest palindrome starting position maxLen = pLen; // Update the length of the longest palindrome}}}}return s.substr(start, maxLen);
}
Copy the codeSolution 2: Dynamic programming method
Because the brute force method needs a lot of repeated calculations to determine palindromes, it can be improved by dynamic programming method. Assuming we know that “bab” is a palindrome, “ababa” must also be a palindrome.
Let's define P[I, j] =trueIf the substring P[I, j] is a palindrome string. Then P[I, j] <- (P[I +1, j-1] &&s [I] = s[j]). Base Case: P[i, i ] =true
P[i, i+1 ] = true <- s[i] = s[i+1]
Copy the codeAccordingly, the implementation code is as follows:
/** * longest substring - dynamic programming method, the time complexity of this method is O(N^2), space complexity is O(N^2). */ /** * the longest loop substring - dynamic programming method, the time complexity of this method is O(N^2), space complexity is O(N^2). * * idea: define P[I, j] = 1 if the substring P[I, j] is a palindrome string. * then P[I, j] <- (P[I +1, j-1] &&s [I] == s[j]). * * Base Case: * P[ i, i ] <- 1 * P[ i, i+1 ] <- s[i] == s[i+1] */ string longestPalindromeDP(string s) { int n = s.length(); int longestBegin = 0, maxLen = 1; int **P; int i; P*/ P = (int **)calloc(n, sizeof(int *));for (i = 0; i < n; i++) {
P[i] = (int *)calloc(n, sizeof(int));
}
for (i = 0; i < n; i++) {
P[i][i] = 1;
}
for (int i=0; i<n-1; i++) {
if (s[i] == s[i+1]) {
P[i][i+1] = 1;
longestBegin = i;
maxLen = 2;
}
}
/*依次求P[i][i+2]...P[i][i+n-1]等*/
int len = 3;
for (; len <= n; ++len) {
for (i = 0; i < n-len+1; ++i) {
int j = i + len - 1;
if(s[i] == s[j] && P[i+1][j-1]) { P[i][j] = 1; longestBegin = i; maxLen = len; }}} /* Free memory */for (i = 0; i< n; i++)
free(P[i]);
free(P);
return s.substr(longestBegin, maxLen);
}
Copy the codeSolution 3: Center method
There is an even easier way to find the longest loop substring using O(N^2) time without extra space. We know that palindrome strings are symmetrical in the center of the string, such as ABBA and ABA. A better approach is to start in the middle, because palindrome strings are symmetrical in the center of the string. A string of length N can have 2n-1 centers of symmetry, and the reason why it’s 2n-1 instead of N is because the point of symmetry can be between two characters, such as abba, where the point of symmetry is between the first letter B and the second letter B. The implementation code is as follows:
Void expandAroundCenter(string s, int l, int r, int *longestBegin, int *longestBegin, int *longestBegin, int *longestBegin, int *longestBegin, int *longestBegin, int *longestBegin, int *longestBegin, int *longestBegin int *longestLen) { int n = s.length();while(l>=0 && r<=n-1 && s[l]==s[r]) { l--, r++; } *longestBegin = l + 1; *longestLen = r - l - 1; } /** * longest substring - center method, time O(N^2). */ string longestPalindromeCenter(string s) { int n = s.length();if (n == 0)
return s;
char longestBegin = 0;
int longestLen = 1;
for(int i = 0; i < n; i++) { int iLongestBegin, iLongestLen; expandAroundCenter(s, i, i, &iLongestBegin, &iLongestLen); // The longest palindrome string centered around position Iif(iLongestLen > longestLen) { longestLen = iLongestLen; longestBegin = iLongestBegin; } expandAroundCenter(s, i, i+1, &iLongestBegin, &iLongestLen); // The longest palindrome string centered around the position between I and I +1if(iLongestLen > longestLen) { longestLen = iLongestLen; longestBegin = iLongestBegin; }}return s.substr(longestBegin, longestLen);
}
Copy the code2.2 Switching Sort
Given a character array containing R, G, and B characters, it is required to sort all characters in RGB order. For example, given an array char s[] = “RGBBRGGBGB”, then RRGGGGBBBB should be sorted.
Solution 1: This problem is somewhat similar to the method used in quicksort to partition the array, but there are three characters, so you need to call the partition method twice, the first partition with B, the second partition with G, so that the original character array can be divided into RGB order. This method is natural and easy to think of. The code is as follows. The disadvantage of this method is that you need to traverse the array twice.
void swapChar(char *s, int i, int j) { char temp = s[i]; s[i] = s[j]; s[j] = temp; Void partition(char *s, int lo, int hi, char t) {int m = lo-1, I;for (i = lo; i <= hi; i++) {
if(s[i] ! = t) { swapChar(s, ++m ,i); }}} /** * rgbSortTwice(char *s) {int len = strlen(s); partition(s, 0, len-1,'G'); RBBRBBGGGG partition(s, 0, len-1,'B'); RRGGGGBBBB} RRGGGGBBBB}Copy the codeSolution 2: There is a method that only traverses the array once, but the number of swaps is not reduced. It mainly sets two variables R and G to indicate the position of the current r and G characters respectively, traversing the number group.
-
1) If the ith position is character R, it should be exchanged with the last character of the preceding indicator variable R, namely, the character at ++ R, and ++ G. At this time, it should also be determined whether the character stored in the swapped I is G. If it is G, it should be exchanged with the character at G;
-
2) If the ith position is G, swap it with the character at ++ G. Plus plus g always points to the next place where we should swap g, plus plus r points to the next place where we should swap R.
-
3) If the i-th position is character B, do nothing and continue traversing.
Void rgbSortOnce(char *s) {int len = strlen(s); int lo = 0, hi = len - 1; int r, g, i; // r = lo - 1; // r = lo - 1;for (i = lo; i <= hi; i++) {
if (s[i] == 'R'SwapChar (s, ++ R, I); ++g;if (s[i] == 'G'SwapChar (s, G, I) swapChar(s, G, I); }else if (s[i] == 'G'SwapChar (s, ++ G, I); }else{// do nothing with B}}}Copy the codeSolution 3: If swapping is not considered, you can directly count the number of characters in RGB, and then reassign the array to RGB from scratch. That’s so much easier, haha. But if you have a different problem, and you want to arrange positive numbers, negative numbers, and 0 in a certain order, then you have to swap.
2.3 Maximum sliding window
Given an array A, there is A sliding window of size W that slides from the left to the end. You can only see w numbers in this window, and you can only move one position at a time. Our goal is to find the maximum number of w digits per window and store these maximum values in array B.
For example, array A = [1 3-1-3 5 3 6 7], window size w = 3. Then the window sliding process is as follows:
Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3-1 1-3 [5 3 6] 7 6 1 3-1 1-3 5 [3 6 7] 7 Input: array A and w size output: array B, where B[I] stores the maximum number of w digits from A[I] to A[I + W-1].Copy the codeSolution 1: Simple implementation
One of the simplest ideas is to Max out w digits for each move and save it. It takes O(w) time to Max out W digits for each move, whereas the sliding process takes N-W +1 swipes, where n is the array size, so the total time is O(NW).
Int maxInArray(int A[], int n) {int Max = A[0], I;for (i = 1; i < n; i++) {
if(A[i] > max) { max = A[i]; }}returnmax; } /* * maxSlidingWindowSimple(int A[], int n, int w, int B[]) {int I;for (i = 0; i <= n-w; i++)
B[i] = maxInArray(A + i, w);
}
Copy the codeSolution 2: maximum heap solution
The first method is simple in thought, but time complex, so it needs to be improved. You can use a maximum heap to hold W numbers, which takes O(LGW) time each time a number is inserted, and O(1) time to get the maximum from the heap (the average size of the heap is about W). As the window slides from left to right, some numbers in the heap are invalidated (because they are no longer contained in the window). If the array itself is ordered, the heap size increases to N. Since the heap size does not remain constant at w, the time complexity of this algorithm is O(NLGN).
/ / void maxSlidingWindowPQ(int A[], int n, int w, int B[]) {typedef pair<int, int> pair; priority_queue<Pair> Q; // The priority queue holds the values in the windowfor(int i = 0; i < w; i++) Q.push(Pair(A[i], i)); // Build a maximum heap of w elementsfor (int i = w; i < n; i++) {
Pair p = Q.top();
B[i-w] = p.first;
while (p.second <= i-w) {
Q.pop();
p = Q.top();
}
Q.push(Pair(A[i], i));
}
B[n-w] = Q.top().first;
}
Copy the codeSolution 3: bidirectional queue solution
The maximum heap solution preserves redundant elements in the heap. For example, if the original element in the heap is [10 5 3] and the new element is 11, then there will be [11 5 3] in the heap. In fact, we can clear the entire queue and then add 11 to the queue, that is, only hold in the queue [11]. A bidirectional queue can be used, where the maximum sliding window is always stored at the head of the queue and the data in the queue is always sorted from largest to smallest. When a value greater than the current sliding window maximum is encountered, the queue is emptied and the new maximum is inserted into the queue. If a value less than the current maximum is encountered, it is inserted directly to the end of the queue. Check whether the current maximum value is in the valid range. If it is not, delete it from the queue. As each element enters and leaves the queue at most once, the time complexity of the algorithm is O(N).
Void maxSlidingWindowDQ(int A[], int n, int w, int B[]) {deque<int> Q; void maxSlidingWindowDQ(int A[], int n, int w, int B[]);for (int i = 0; i < w; i++) {
while(! Q.empty() && A[i] >= A[Q.back()]) Q.pop_back(); Q.push_back(i); }for (int i = w; i < n; i++) {
B[i-w] = A[Q.front()];
while(! Q.empty() && A[i] >= A[Q.back()]) Q.pop_back();while(! Q.empty() && Q.front() <= i-w) Q.pop_front(); Q.push_back(i); } B[n-w] = A[Q.front()]; }Copy the code2.4 Longest common subsequence
Given two sequences X = < x1, x2… , xm > and Y = < y1, y2… Ym >, hoping to find the common subsequence (LCS) of the maximum length of X and Y.
Analysis: The simplest way to solve LCS is to use brute force method, enumerating all subsequences of X, and then checking whether they are subsequences of Y one by one, and recording the largest sequence found, and finally taking the largest subsequence. But all of the subsequences of X have 2 to the m, and this method takes exponential time, which is not very practical, but the LCS problem actually has optimal substructure properties.
Optimal substructure of LCS:
Let X = < x1, x2… , xm > and Y = < y1, y2… , yn > are two sequences, and let Z = < z1, z2… , zk > is any LCS of X and Y.
-
- If xm = yn, zk = xm = yn, and Zk-1Is Xm-1And Yn-1One LCS of theta.
-
- If xm! = yn, zk! = xmAnd Z is Xm-1One LCS of Y.
-
- If xm! = yn, zk! = ynAnd Z is X and Yn-1One LCS of theta.
Therefore, we can define c[I, j] as the length of an LCS of sequence Xi and Yj, then we can get the following recursion:
C/I, j = 0 / / I = 0 or j = 0 c/I, j = c [] I - 1, j - 1 + 1 / / I, j > 0, And Xi = Yj c/I, j = Max (c/I - 1, j, c [I]] [j - 1) / / I, j > 0, and Xi! = YjCopy the codeFrom this we can write the following code to find the length of the LCS and the LCS, using an auxiliary array B to store the LCS path. Here is a recursive algorithm for LCS length, the use of dynamic programming algorithm code see this source code.
/** * LCS- recursive algorithm */#define UP 1
#define LEFT 2
#define UPLEFT 3
int lcsLengthRecur(char *X, int m, char *Y, int n, int **b)
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1]) {
b[m][n] = UPLEFT;
return lcsLengthRecur(X, m-1, Y, n-1, b) + 1;
}
int len1 = lcsLengthRecur(X, m-1, Y, n, b);
int len2 = lcsLengthRecur(X, m, Y, n-1, b);
int maxLen;
if (len1 >= len2) {
maxLen = len1;
b[m][n] = UP;
} else {
maxLen = len2;
b[m][n] = LEFT;
}
returnmaxLen; } /** * print the LCS using the auxiliary array b */ voidprintLCS(int **b, char *X, int i, int j)
{
if (i == 0 || j == 0)
return;
if (b[i][j] == UPLEFT) {
printLCS(b, X, i-1, j-1);
printf("%c ", X[i-1]);
} else if (b[i][j] == UP) {
printLCS(b, X, i-1, j);
} else {
printLCS(b, X, i, j-1); }}Copy the codeThe process of printing LCS is shown below (figure taken from Introduction to Algorithms) :
2.5 All Strings are arranged
Given an array of characters char arr[] = “ABC”, print the full array of characters in the array.
Solution: Output full permutation using recursion. The perm(arr, k, len) function outputs all permutations of the character array arr starting at position k. The array length is len. The base condition is k == len-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 len=3, then perm(arr, 0, 3) is called: swap 0, 0, and execute perm(arr, 1, 3). Swap 0, 0 again, and restore the array to its original value. Perm (arr, 1, 3) is executed. After that, the array is swapped again, and the array is restored to its original value. Swap 2,0 for the third time and execute perm(arr, 1, 3). Swap 2,0 for the third time and restore the array to its original value.
The program output is ABC, ACB, BAC, BCA, CBA, CAB. That is, the first permutation of a is printed, followed by the first permutation of B and C.
Void perm(char *arr, int k, int len) {//k is the starting position and len is the size of the arrayif (k == len-1) {
printf("%s\n", arr);
return;
}
for(int i = k; i < len; i++) { swapChar(arr, i, k); // Switch perm(arr, k+1, len); SwapChar (arr, I, k); // Restore the original sequence}}Copy the code2.6 Regular Expressions
Implementation of a simple version of the regular expression, support ^, $,. Features.
Regular expression basics: A regular expression is itself a sequence of characters that defines a collection of strings that can be matched. In common Unix/Linux regular expressions, the character ^ indicates the beginning of a string and $indicates the end of a string. Thus, ^x matches only x at the beginning of a string, x$matches only x at the end, ^x$matches only x in a single string, and ^$matches only empty strings. Character. Can match any character. So pattern x.y matches xay, x2y, and so on, but it does not match xy or xaby. Obviously ^.$can match any single character string. A set of characters written in square brackets [] can match any of these characters. For example, [0123456789] can match any number. This pattern can also be abbreviated to [0-9].
The following is the main function match for regular expression matching, and the parameters are regexp and text. If the regular expression begins with ^, the body must match the rest of the expression from the beginning. Otherwise, we go down the string and use matchhere() to see if the text matches somewhere. Once a match is found, the job is done. Note the use of do-while. Some expressions can match an empty string (for example, $can match an empty string at the end of the string, and * can match any number of characters, including zero). So, even if we encounter an empty string, we still need to call Matchhere ().
int match(const char *regexp, const char *text)
{
if (regexp[0] == A '^')
return matchhere(regexp+1, text);
do {
if (matchhere(regexp, text))
return 1;
} while(*text++ ! ='\ 0');
return 0;
}
Copy the codeThe recursive function matchhere() does most of the matching:
- if
regexp[0]=='\0'If the match is successful, 1 is returned. - If the end of the expression is zero
$, the successful matching condition is that the text also reaches the end, that is, the judgment*text=='\0'. If the text is at the end, the match succeeds; otherwise, the match fails. - If the text is not at the end, and
regexp[0] == *textorregexp=='.'(.Represents matching any character), a recursive call to Matchhere continues the next match. - if
regexp[1]=='*', the process is slightly complicated, for examplex*. At this point we callmatchstarThe first argument is the asterisk argument (x*In thex), followed by the schema after the asterisk and the corresponding body string.
int matchhere(const char *regexp, const char *text)
{
if (regexp[0] == '\ 0')
return 1;
if (regexp[0]=='$' && regexp[1]=='\ 0')
return *text == '\ 0';
if (regexp[1] == The '*')
return matchstar(regexp[0], regexp+2, text);
if(*text ! ='\ 0' && (regexp[0] == '. ' || regexp[0] == *text))
return matchhere(regexp+1, text+1);
return 0;
}
int matchstar(int c, const char *regexp, const char *text)
{
do {
if (matchhere(regexp, text))
return 1;
} while(*text ! ='\ 0' && (*text++ == c || c == '. '));
return 0;
}
Copy the codeExample:
char *regexp="abc", text="dagabcdefg"The match is successful.char *regexp="^abc", *text="abcdefg"The match is successful.char *regexp="^abc", *text="bcdefgabc"Failed to match.char *regexp="abc$", *text="defghabc"The match is successful.
2.7 KMP algorithm and BM algorithm
String matching famous KMP algorithm and BM algorithm, online information is more, you can see grep string search algorithm Boyer-Moore from shallow to deep (faster than KMP 3-5 times) and string matching KMP algorithm.
Data Structures and algorithms – Linked lists
Summary of 0.
As a basic data structure, linked lists are used in many places. Such as Linux kernel code, Redis source code, Python source code are used. In addition to one-way linked lists, there are also two-way linked lists. This article focuses on one-way linked lists (including some circular linked list topics, will be noted in the title, the other cases are to discuss simple one-way linked lists). Bidirectional linked lists are well implemented in Redis, and I have a copy of them in my repository for testing purposes. The code for this article is here.
Definition 1.
First define a one-way linked list structure, as follows, define the linked list node and linked list two structures. Here I did not define a linked list structure, save the head pointer, tail pointer, linked list length and other information, the purpose is also to practice pointer operation.
Typedef struct ListNode {struct ListNode *next; int value; } listNode;Copy the code
2. Basic operations
On the basis of the list definition in the previous section, we complete several basic operation functions, including initialization of the list, adding nodes to the list, removing nodes from the list, etc.
/** * create a ListNode */ ListNode *listNewNode(int value) {ListNode *node;if(! (node = malloc(sizeof(ListNode))))return NULL;
node->value = value;
node->next = NULL;
returnnode; } /** * insert a header into a node. */ ListNode *listAddNodeHead(ListNode *head, int value) { ListNode *node;if(! (node = listNewNode(value)))return NULL;
if (head)
node->next = head;
head = node;
returnhead; } /** * inserts a node with value. */ ListNode *listAddNodeTail(ListNode *head, int value) { ListNode *node;if(! (node = listNewNode(value)))return NULL;
returnlistAddNodeTailWithNode(head, node); } /** * insert into nodes. */ ListNode *listAddNodeTailWithNode(ListNode *head, ListNode *node) {if(! head) { head = node; }else {
ListNode *current = head;
while (current->next) {
current = current->next;
}
current->next = node;
}
returnhead; } /** * remove the node with value from the linked list. */ ListNode *listDelNode(ListNode *head, int value) { ListNode *current=head, *prev=NULL;while (current) {
if (current->value == value) {
if (current == head)
head = head->next;
if (prev)
prev->next = current->next;
free(current);
break;
}
prev = current;
current = current->next;
}
returnhead; } /** * list traversal. */ void listTraverse(ListNode *head) { ListNode *current = head;while (current) {
printf("%d", current->value);
printf("- >");
current = current->next;
if(current == headbreak;
}
printf("NULL\n"); } /** * initializes a linked list with an array of len elements. */ ListNode *listCreate(int a[], int len) { ListNode *head = NULL; int i;for (i = 0; i < len; i++) {
if(! (head = listAddNodeTail(head, a[i])))return NULL;
}
returnhead; } /** * listLength function */ int listLength(ListNode *head) {int len = 0;while (head) {
len++;
head = head->next;
}
return len;
}
Copy the code3. List related interview questions
3.1 Reverse linked list
Given a unidirectional linked list 1->2->3->NULL, the reverse order becomes 3->2->1->NULL.
Solution: The common method is to connect each node in reverse order in a circular way, as follows:
/** * list reverse order, non-recursive implementation. */ ListNode *listReverse(ListNode *head) { ListNode *newHead = NULL, *current = head;while (current) {
ListNode *next = current->next;
current->next = newHead;
newHead = current;
current = next;
}
return newHead;
}
Copy the codeIf it’s a bit of a show-off, let’s do a recursive solution like this:
/** * 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 code3.2 Linked list Replication
Given a one-way linked list, copy and return the new list header.
Solution: There are also two possible solutions, non-recursive and recursive, as follows:
/** * ListNode *listCopy(ListNode *head) {ListNode *current = head, *newHead = NULL, *newTail = NULL;while (current) {
ListNode *node = listNewNode(current->value);
if(! NewHead = newTail = node; }else {
newTail->next = node;
newTail = node;
}
current = current->next;
}
returnnewHead; } /** *list copy - recursive */ ListNode *listCopyRecursive(ListNode *head) {if(! head)return NULL;
ListNode *newHead = listNewNode(head->value);
newHead->next = listCopyRecursive(head->next);
return newHead;
}
Copy the code3.3 Linked list merging
Given two ordered unidirectional lists, please merge the two lists so that the combined lists are still ordered (note: the two lists have no common nodes, i.e. do not cross). Such as chain table 1 is 1 – > 3 – > 4 – > NULL, chain table 2 is 5-2 – > > 6-7-8 – > > > NULL, then the combined list for 1 – > 2 – > 3 – > 4 – > 5 – > 6-7-8 – > > > NULL.
Solution: This is very similar to the last step of merge sort, just merge two ordered lists together. Two Pointers are used to traverse the two linked lists separately, and the smaller value nodes are merged into the resulting linked list. If a list is merged and another list has nodes, the rest of the other list is added to the end of the resulting list. The code looks like this:
/** *listMerge - non-recursive */ ListNode *listMerge(ListNode *list1, ListNode *list2) {ListNode dummy; ListNode *tail = &dummy; ListNode *tail = &dummy;if(! list1)return list2;
if(! list2)return list1;
while (list1 && list2) {
if (list1->value <= list2->value) {
tail->next = list1;
tail = list1;
list1 = list1->next;
} else{ tail->next = list2; tail = list2; list2 = list2->next; }}if (list1) {
tail->next = list1;
} else if (list2) {
tail->next = list2;
}
return dummy.next;
}
Copy the codeOf course, to implement a recursion is not difficult, the code is as follows:
ListNode *listMergeRecursive(ListNode *list1, ListNode *list2)
{
ListNode *result = NULL;
if(! list1)return list2;
if(! list2)return list1;
if (list1->value <= list2->value) {
result = list1;
result->next = listMergeRecursive(list1->next, list2);
} else {
result = list2;
result->next = listMergeRecursive(list1, list2->next);
}
return result;
}
Copy the code3.4 Link list intersection judgment
Given two unidirectional lists list1 and list2, determine whether the two lists intersect. If it intersects, find out where it intersects.
Solution 1: It is possible to directly traverse list1 and then determine whether each node of List1 is in List2, but the complexity of this solution is O(length(list1) * length(list2)). Length (length(list1) + length(list2))); space (length(list1)); space (length(list1)); So we can figure out where we’re going to intersect. Of course, there are better ways to find intersecting nodes.
Solution 2: If two lists intersect, their nodes from the intersection must be the same. If the length of list1 is len1, the length of List2 is len2, and len1 > len2, then we only need to traverse len1 through len1-LEN2 nodes first, and then the two nodes together. If the node is equal, the node will be the first intersection node.
/** * if the list intersects, return the intersecting node, otherwise return NULL. */ ListNode *listIntersect(ListNode *list1, ListNode *list2) { int len1 = listLength(list1); int len2 = listLength(list2); int delta = abs(len1 - len2); ListNode *longList = list1, *shortList = list2;if (len1 < len2) {
longList = list2;
shortList = list1;
}
int i;
for (i = 0; i < delta; i++) {
longList = longList->next;
}
while (longList && shortList) {
if (longList == shortList)
return longList;
longList = longList->next;
shortList = shortList->next;
}
return NULL;
}
Copy the code3.5 Determine whether the linked list has rings
Given a linked list, determine whether there are rings in the list.
Solution 1: The easy way to think about it is to use a hash table to record the nodes that have appeared and walk through the linked list. If a node appears repeatedly, it indicates that the linked list has a ring. If the hash table is not used, a visited field can also be added to the ListNode structure of the linked ListNode to mark it, and the visited field marked as 1 can also be detected. Since we haven’t implemented a hash table yet, this method code will be added later.
Solution 2: A better method is the Floyd loop detection algorithm, which was first developed by Robert. Freud invented it. The linked list is traversed by using two Pointers fast and slow, the fast pointer taking two steps at a time and the slow pointer taking one step at a time. If fast and slow meet, then there is a ring, otherwise there is no ring. (Note that if the list has only one node and no loop, it does not enter the while loop)
Detectloop (ListNode *head) {ListNode *slow, *fast; ListNode *head (ListNode *head) {ListNode *slow, *fast; slow = fast = head;while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
printf("Found Loop\n");
returnslow; }}printf("No Loop\n");
return NULL;
}
void testListDetectLoop()
{
printf("\nTestListDetectLoop\n"); int a[] = {1, 2, 3, 4}; ListNode *head = listCreate(a, ALEN(a)); listDetectLoop(head); Head ->next->next->next = head; listDetectLoop(head); }Copy the codeExtension: how to find the entry point of a linked list ring if a ring is detected?
First, let’s prove why the algorithm mentioned in solution 2 above is correct. If the list does not have a loop, because the fast pointer takes 2 steps each time, it must reach the end of the list before the slow pointer, and will not meet.
If there is a ring, it is assumed that the fast and slow Pointers meet after s cycles, then the distance traveled by the fast Pointers is 2s, and the distance traveled by the slow Pointers is S. Assuming that the number of nodes in the ring is R, the following conditions must be met in order to meet, that is, the number of encounters meets s = nr. That is, the next encounter from the starting point requires r cycles.
2s - s = nr => s = nr
Copy the codeAs shown in the figure below, ring length r=4, then the next encounter from the starting point needs to go through 4 cycles.
So how do we find the entry point of the ring? It can be seen from the previous that r times are required for the first encounter, and the distance traveled by the slow pointer is S = R. Set the total length of the linked list as L, the distance from the head of the list to the ring entrance as A, and the distance from the ring entrance to the encounter point as X, then L = a + R, and a = (L-x-a) can be deduced. Wherein, L-x-a is the distance from the encounter point to the ring entrance point, that is, the distance a from the list head to the ring entrance is equal to the distance from the encounter point to the ring entrance.
s = r = a + x => a + x = (L-a) => a = L-x-a
Copy the codeTherefore, after judging the existence of a ring in the linked list, the traversal starts from the encounter point and the head node respectively, and the two Pointers take a step each time. When the two Pointers are equal, it is the entry point of the ring.
/** *findLoopNode(ListNode *head) {ListNode *meetNode = listDetectLoop(head);if(! meetNode)return NULL;
ListNode *headNode = head;
while(meetNode ! = headNode) { meetNode = meetNode->next; headNode = headNode->next; }return meetNode;
}
Copy the code3.6 Linked lists simulate addition
Given two linked lists, the node value of each list is the digit on the digit digit, try to find the sum of the digits represented by the two linked lists, and return the result as a linked list. Suppose the two linked lists are respectively list1 and list2. The values of each node of List1 are the ones, tens, and hundreds digits of the number 513, and the values of each node of List2 are the digits of the number 295. The two numbers add up to 808, so the output is printed in order from the ones to the hundreds, and the linked list of results is returned as follows.
List1: (3 -> 1 -> 5 -> NULL) List2: (5 -> 9 -> 2 -> NULL) result: (8 -> 0 -> 8 -> NULL)Copy the codeSolution: This topic is interesting, need to be familiar with linked list operation. We consider the process of adding two digits from the lowest digit to the highest digit, marking the carry flag if there is a carry, and terminating until the highest digit. Set the node of the current bit to current, then:
Current -> data = list1 -> data + list2 -> data + carry (where carry is 1, otherwise 0)Copy the codeThe non-recursive code is as follows:
/** *listEnumarateAdd(ListNode *list1, ListNode *list2) {int carry = 0; ListNode *result = NULL;while (list1 || list2 || carry) {
int value = carry;
if (list1) {
value += list1->value;
list1 = list1->next;
}
if(list2) { value += list2->value; list2 = list2->next; } result = listAddNodeTail(result, value % 10); carry = ( value >= 10 ? 1:0); }return result;
}
Copy the codeThe non-recursive implementation is as follows:
/ * * * list analog addition - * / ListNode * listEnumarateAddRecursive recursive method (ListNode * list1, ListNode * list2, int carry) {if(! list1 && ! list2 && carry==0)return NULL;
int value = carry;
if (list1)
value += list1->value;
if(list2) value += list2->value; ListNode *next1 = list1 ? list1->next : NULL; ListNode *next2 = list2 ? list2->next : NULL; ListNode *more = listEnumarateAddRecursive(next1, next2, (value >= 10 ? 1:0)); ListNode *result = listNewNode(carry); result->value = value % 10; result->next = more;return result;
}
Copy the code3.7 Ordered unidirectional circular linked lists are inserted into nodes
Given an ordered one-way circular linked list, insert a node and keep the list ordered, as shown below.
Solution: Before we solve this problem, let’s look at the simplified version, which is to insert nodes into an ordered, non-cyclic, one-way linked list, and still keep the order. The code of this question is believed to be familiar to most people, generally divided into two cases to consider:
- 1) If the original linked list is empty or the inserted node has a minimum value, the node is directly inserted and set as the head node.
- 2) If the original linked list is not empty, find the first node whose value is greater than the value of the node and insert it in front of the node. If the inserted node has the largest value, it is inserted at the end.
The implementation code is as follows:
*/ ListNode *sortedListAddNode(ListNode *head, int value) {ListNode *node = listNewNode(value);if(! Head | | head - > value > = value) {/ / situation 1 node - > next = head; head = node; }elseListNode *current = head;while(current->next ! = NULL && current->next->value < value) current = current->next; node->next = current->next; current->next = node; }return head;
}
Copy the codeOf course, both cases can be handled together, using second-level Pointers. As follows:
Void sortedlistaddnodehead (ListNode, ListNode, ListNode, ListNode, ListNode) int value) { ListNode *node = listNewNode(value); ListNode **current = head;while ((*current) && (*current)->value < value) {
current = &((*current)->next);
}
node->next = *current;
*current = node;
}
Copy the codeIn the case of circular lists, there are two things to consider:
- 1) prev->value ≤ value ≤ current->value: insert between prev and current.
- 2) Value is the maximum or minimum value: insert to the intersection of head and tail, if it is the minimum value reset head value.
The code is as follows:
*/ ListNode *sortedLoopListAddNode(ListNode *head, int value) {ListNode *node = listNewNode(value); ListNode *current = head, *prev = NULL;do {
prev = current;
current = current->next;
if (value >= prev->value && value <= current->value)
break;
} while(current ! = head); prev->next = node; node->next = current;if(current == head && value < current->value)return head;
}
Copy the code3.8 Output the penultimate KTH node of the linked list
Given a simple one-way linked list, output the KTH node to the end of the list.
Solution 1: If it’s the KTH node, you don’t have to think about it. What’s new about this problem is that it’s going to output the penultimate KTH node. An intuitive way to think about it is, given a list of length L, the KTH node to the end is L minus K plus 1. If the length of the list is 3, the second-to-last node is the second node of the sequence. You need to walk through the list twice, once to find the length and once to find the node.
*/ ListNode *getLastKthNodeTwice(ListNode *head, int K) {int len = listLength(head);if (k > len)
return NULL;
ListNode *current = head;
int i;
for(i = 0; i < len-k; Current = current->next;return current;
}
Copy the codeSolution 2: Of course, a better way is to iterate once, set two Pointers p1,p2, first p1 and p2 both point to head, and then P2 takes k steps forward, so that there are k nodes between p1 and P2. And then p1 and P2 move forward at the same time, and p2 goes to the end of the list and P1 points to the KTH node. The code is as follows:
*/ ListNode *getLastKthNodeOnce(ListNode *head, int K) {ListNode *p1, *p2; p1 = p2 = head;for(; k > 0; k--) {
if(! P2) // The list length is insufficient Kreturn NULL;
p2 = p2->next;
}
while (p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
Copy the codeData structures and algorithms – Stacks
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.
Summary of 0.
As a basic data structure, stack is used in many places, such as function recursion, prefix and suffix expression conversion, etc. This article will use C array to realize the stack structure (use the linked list implementation can see the linked list section, use the header method to build the linked list), and several common stack related interview questions are analyzed, the code of this article is here.
Definition 1.
We use structs to define stacks and flexible arrays to store elements. Several macros are defined to calculate the number of elements in a stack and whether the stack is empty or full.
typedef struct Stack {
int capacity;
int top;
int items[];
} Stack;
#define SIZE(stack) (stack->top + 1)
#define IS_EMPTY(stack) (stack->top == -1)
#define IS_FULL(stack) (stack->top == stack->capacity - 1)
Copy the code2. Basic operations
There are three basic operations on the stack:
- Push: Pushes an element onto the stack.
- Pop: Pops the top element of the stack and returns.
- Peek: Fetching the top element of the stack, but not modifying the stack.
As shown in the figure:
The code is as follows:
Stack *stackNew(int capacity)
{
Stack *stack = (Stack *)malloc(sizeof(*stack) + sizeof(int) * capacity);
if(! stack) {printf("Stack new failed\n");
exit(E_NOMEM);
}
stack->capacity = capacity;
stack->top = -1;
return stack;
}
void push(Stack *stack, int v)
{
if (IS_FULL(stack)) {
printf("Stack Overflow\n");
exit(E_FULL);
}
stack->items[++stack->top] = v;
}
int pop(Stack *stack)
{
if (IS_EMPTY(stack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
return stack->items[stack->top--];
}
int peek(Stack *stack)
{
if (IS_EMPTY(stack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
return stack->items[stack->top];
}
Copy the code3. Stack related interview questions
3.1 Suffix expression
Given a suffix expression 6 5 2 3 + 8 * + 3 + *, find the value of the suffix expression.
Solution: Postfix expressions, also known as inverse Polish expressions, can be evaluated using stacks to assist storage. Then its evaluation process is as follows:
- 1) Iterate through the expression, the number encountered is first put into the stack, then the stack is
[6 2, 3, 5]。 - 2) Read on
+, then pop up 3 and 2 to calculate3 + 2And the result is equal to5And will5Push it onto the stack. The stack is zero5 5] [6。 - 3) read
8, put it directly on the stack,[6] 5 5 8。 - 4) read
*That pop up8和5To calculate the8 * 5And will result40Push it onto the stack[40] 6 5. And then the process is similar, read+That will be40和5Pop up,40 + 5The results of the45Push into the stack, and the stack becomes[6] 45, read 3 and put it on the stack45 3 [6]. And so on, and so on288.
Code:
int evaluatePostfix(char *exp)
{
Stack* stack = stackNew(strlen(exp));
int i;
if(! stack) {printf("New stack failed\n");
exit(E_NOMEM);
}
for(i = 0; exp[i]; ++ I) {// If it is a number, press it directlyif (isdigit(exp[i])) {
push(stack, exp[i] - '0');
} elseInt val1 = pop(stack); int val1 = pop(stack); int val2 = pop(stack); switch (exp[i]) {case '+': push(stack, val2 + val1); break;
case The '-': push(stack, val2 - val1); break;
case The '*': push(stack, val2 * val1); break;
case '/': push(stack, val2/val1); break; }}}return pop(stack);
}
Copy the code3.2 stack reverse
Given a stack, reverse it.
Solution 1: If you don’t care about space complexity, you can create another secondary stack, pop all the data from the original stack and push it to the secondary stack.
Solution 2: If you come across this question in an interview, you are expected to do it in a better way. You can first implement a function that inserts elements at the bottom of the stack, and then recursively reverse the stack without using a secondary stack.
*/ void insertAtBottom(Stack * Stack, int v) {if (IS_EMPTY(stack)) {
push(stack, v);
} else{ int x = pop(stack); insertAtBottom(stack, v); push(stack, x); } /** * Stack reverse */ void stackReverse(Stack * Stack) {if (IS_EMPTY(stack))
return;
int top = pop(stack);
stackReverse(stack);
insertAtBottom(stack, top);
}
Copy the code3.3 Design a stack containing min functions
Design a stack such that push, pop, and MIN (fetching the smallest element in the stack) can be completed in constant time.
Analysis: At first, it is easy to think of a method, which is to create an additional minimum binary heap to hold all the elements, so that each time to fetch the smallest element only O(1) time. However, in order to build a minimum heap for push and pop operations, O(LGN) time is required (assuming n elements in the stack).
Solution 1: Auxiliary stack method
So in order to do that, you can use a helper stack and you can use a helper stack to hold the smallest element, which is simple and elegant. Let the secondary stack be named minStack and the top element of the stack be the smallest element in the current stack. This means that
- 1) To get the smallest element in the current stack, just return the top element of the minStack.
- 2) Each time a push operation is performed, check whether the element of push is less than or equal to the element at the top of the minStack. If so, push that element into the minStack as well.
- 3) When performing the POP operation, check whether the pop element is equal to the current minimum value. If it is equal, the element needs to be popped out of the minStack.
Code:
void minStackPush(Stack *orgStack, Stack *minStack, int v)
{
if (IS_FULL(orgStack)) {
printf("Stack Full\n");
exit(E_FULL);
}
push(orgStack, v);
if (IS_EMPTY(minStack) || v < peek(minStack)) {
push(minStack, v);
}
}
int minStackPop(Stack *orgStack, Stack *minStack)
{
if (IS_EMPTY(orgStack)) {
printf("Stack Empty\n");
exit(E_EMPTY);
}
if (peek(orgStack) == peek(minStack)) {
pop(minStack);
}
return pop(orgStack);
}
int minStackMin(Stack *minStack)
{
return peek(minStack);
}
Copy the codeExample:
Another approach uses the memory difference without the need for a secondary stack, which is more subtle:
- The stack has at most one more space for storing the stack minimum.
pushIs the difference between the current element and the smallest element in the stack before it is pressed (the element at the top of the stack), then by comparing the size of the current element with the smallest element in the current stack, and pushing the smaller value of them as the new minimum.popWhen the function executes, firstpopTwo values out of the top of the stack, which are the smallest values in the current stackminAnd the difference between the last pushed element and the minimum value in the previous stackdelta. According to thedelta < 0ordelta >= 0To get the value of the element that was pushed on the stack and the new minimum value of that element after it is pushed off the stack.minThe function just takes the top element of the stack.
Code:
void minStackPushUseDelta(Stack *stack, int v)
{
if(IS_EMPTY(stack)) {// Empty stack, push v twice; push(stack, v); }else {
int oldMin= pop(stack); Int delta = v - oldM; int delta = v - oldMin;
int newMin = delta < 0 ? v : oldMin; push(stack, delta); // The difference between v and the minimum value in the previous stack push(stack, newM)in); } int minStackPopUseDelta(Stack * Stack) {int min = pop(Stack); int delta = pop(stack); int v, oldMin;
if(delta < 0) {// The last element is smaller than min, then min is the last element v = min; oldMin = v - delta;
} else{// The last value pressed is not the minimum value, then min is oldMin. oldMin = min;
v = oldMin + delta;
}
if(! IS_EMPTY(stack)) {// If the stack is not empty, the oldM is pressedin
push(stack, oldMin);
}
return v;
}
int minStackMinUseDelta(Stack *stack)
{
return peek(stack);
}
Copy the codeExample:
Push (3) : [3] 3 push (4) : 1 3 [3] push (2) : 1-1, 2] [3 push (5) : 1-1 3 2] [3 push (1) : 1-3-1 1 [3] min () : 1, pop () : 1, 3 2] [3 1-1 min () : 2, pop () : 5, 1-1, 2] [3 min () : 2, pop () : 2, 3] [3 1 min () : 3, pop () : 4, [3] 3 min () : 3, pop () : 3. []Copy the code3.4 Find out the number of stacks and the sequence of out stacks
Find the number of stacks
Given a stack sequence, try to find all possible stack sequences. For example, if the stack sequence is 1, 2, 3, there are five possible stack sequences: 1, 2, 3, 1, 3, 2, 3, 1, 2, 1.
Solution: ask to solve the stack sequence number, still calculate relatively easy. Many articles have analyzed this problem, and the final answer is the Cattelan number, which means that the total number of stack sequences of n elements is equal to C(2n, n) – C(2n, n-1) = C(2n, n)/(n+1), For example, the total stack number of 3 elements is C(6, 3) / 4 = 5.
If you don’t analyze the general term formula, can you write a program to find the number of sequences out of the stack? The answer is yes, according to the current state of the stack, we can add the total number of the two cases of pushing an element and pushing an element to get the total number of the stack.
/** * count stacks * -in: Number of elements in the stack * -out: number of elements out of the stack * -wait*/ int sumOfStackPopSequence(Stack * Stack, intin, int out, int wait)
{
if(out == stack->capacity) {// All elements out of the stack, return 1return 1;
}
int sum = 0;
if (wait> 0) sum += sumOfStackPopSequence(stack,in + 1, out, wait - 1);
if (in> 0) sum += sumOfStackPopSequence(stack,in - 1, out + 1, wait);
return sum;
}
Copy the codeFind all out stack sequences
Given an input sequence input[] = {1, 2, 3}, print all possible stack sequences.
Solution: This is a bit difficult, not only the stack number, need to print all the stack sequence, need to use backtracking method, backtracking method is much more difficult than simple recursion, later there is time to separate a backtracking method article. For each input, there are two situations: whether the elements in the original stack are removed from the stack first or removed from the stack first. Here, two stacks are used to achieve this, where the stack STK is used to simulate the entry and exit of the stack, and the stack output is used to store the value of the exit stack. Note that the exit condition is that when all input elements are traversed, there may be elements in both stack STK and output. It is necessary to print the stack OUTPUT from the bottom of the stack first, and then print the stack STK from the top of the stack. Another point is that the branch ends when the simulation stack we are using, STK, is empty. The code is as follows:
void printStackPopSequence(int input[], int i, int n, Stack *stk, Stack *output)
{
if(i >= n) { stackTraverseBottom(output); // output prints stackTraverseTop(STK) from the bottom of the stack; // STK prints from the top of the stackprintf("\n");
return;
}
push(stk, input[i]);
printStackPopSequence(input, i+1, n, stk, output);
pop(stk);
if (IS_EMPTY(stk))
return;
int v = pop(stk);
push(output, v);
printStackPopSequence(input, i, n, stk, output);
push(stk, v);
pop(output);
}
Copy the codeData Structures and Algorithms – Binary heap
Summary of 0.
The heap described in this article is a binary heap. A binary heap is an array object that can be viewed as a complete binary tree. Each node in the tree corresponds to the element in the array that holds the value of that node. Every layer of the tree is filled except the last. Binary heap can be used to implement heap sorting, priority queue, etc. The code address for this article is here.
1. Binary heap definition
Use array to implement binary heap, binary heap two attributes, where LENGTH(A) represents the LENGTH of array A, and HEAP_SIZE(A) represents the number of elements stored in A heap, where LENGTH(A) <= HEAP_SIZE(A), That is, although A[0,1… n-1] can contain valid values, elements after A[HEAP_SIZE(A)-1] do not belong to the corresponding heap.
The root of the tree corresponding to the binary heap is A[0]. Given the subscript I of A node, it is easy to calculate its father and son nodes. Note that in the later example diagram we annotate elements counting from 1, whereas in the implementation code we count from 0.
#define PARENT(i) ( i > 0 ? (i-1)/2 : 0)
#define LEFT(i) (2 * i + 1)
#define RIGHT(i) (2 * i + 2)
Copy the codeNote: the heap is full at every level, so the maximum number of elements in a heap of height h is 1+2+2^2+… 2^h = 2^(h+1) -1 (full binary tree), the number of elements is at least 1+2+… Plus 2 to the h minus 1 plus 1 is 2 to the h. The number of elements 2^h <= n <= 2^(h+1) -1, so h <= LGN < h+1, so h = LGN. The height of a binary heap with n elements is LGN.
2. Keep the nature of the heap
This paper mainly establishes a maximum heap, the principle of the minimum heap is similar. To preserve the nature of the heap, the maxHeapify(int A[], int I) function drops the heap array A in the maximum heap, making the subtree rooted in I the maximum heap.
void maxHeapify(int A[], int i, int heapSize)
{
int l = LEFT(i);
int r = RIGHT(i);
int largest = i;
if (l <= heapSize-1 && A[l] > A[i]) {
largest = l;
}
if (r <= heapSize-1 && A[r] > A[largest]) {
largest = r;
}
if(largest ! = I) {// If the maximum is not I, the I and largest elements need to be swapped and maxHeapify is recursively called. swapInt(A, i, largest); maxHeapify(A, largest, heapSize); }}Copy the code-
In each step of the algorithm, the largest element is selected from A[I], A[left] and A[right], and its subscript is stored in largest. If A[I] is the largest, then the subtree rooted in I is already the largest heap, and the program ends.
-
Otherwise, if one of the children of I has the largest element, swap A[I] with A[largest], so that I and its children satisfy the maximum heap property. In addition, the value of the node with subscript largest becomes A[I] after the swap, and the subtree with this node as the root may violate the property of maximum heap, so maxHeapify() is recursively called on this subtree.
When maxHeapify() operates on A subtree of size N with I as the root node, the running time is O(1) of adjusting A[I], A[left], A[right]. Plus the time to recursively call maxHeapify on a subtree rooted in some child of I. The subtree root of I is at most 2n/3(when the bottom layer is just half full), so we can deduce that T(N) <= T(2n/3) + O(1), so T(N)=O(lgN).
Here is an example running maxHeapify(heap, 2). A[] = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1}, the heap size is 10.
3. Build a maximum heap
We can know that the array A [0, 1,…, N – 1], A [N / 2,…, N – 1) elements are leaf nodes of the tree. Nodes 6-10 in the figure above are leaf nodes. Each leaf node can be regarded as the largest heap with only one element, so we only need to call maxHeapify() on the other nodes.
void buildMaxHeap(int A[], int n)
{
int i;
for(i = n/2-1; i >= 0; i--) { maxHeapify(A, i, n); }}Copy the codeAnd the reason why this function is true, we need to prove it, we can prove it using loop invariants.
Loop invariant: before the for loop begins, nodes I +1, I +2… N minus one is the biggest root.
Initialization: before the loop starts iterating, I = N/2-1, node N/2, N/2+1… N minus one are all leaves, and they’re all the largest number of roots.
Hold: because the children of node I are labeled larger than I, these children are the root of the largest heap according to the definition of the loop invariant, so after maxHeapify(), I becomes the root of the largest heap, and I +1, I +2… N minus one is still the largest heap.
Termination: when the process terminates, I =0, so nodes 0, 1, 2… N minus one is the root of the biggest heap, and in particular, node 0 is the root of the biggest heap.
Although each call to maxHeapify() takes O(lgN) for O(N) calls, it is not exact to say that the running time is O(NlgN). To be exact, the running time is O(N), which will not be proved here. See Introduction to Algorithms for proof.
4. The heap sort
Start by creating A maximum heap with buildMaxHeap(), because the largest element in the array is at A[0], and get to the final correct position by directly interchanging it with A[n-1]. Call maxHeapify(heap, 0, –heapSize) to maintain the maximum heap nature until the heap size decreases from N to 1.
void heapSort(int A[], int n)
{
buildMaxHeap(A, n);
int heapSize = n;
int i;
for(i = n-1; i >= 1; i--) { swapInt(A, 0, i); maxHeapify(A, 0, --heapSize); }}Copy the code5. Priority queue
Finally, a maximum priority queue is implemented, with four operations, as shown below:
The key, the insert (PQ): Inserts the key into the queue.maximum(PQ): Returns the element with the largest keyword in the queueextractMax(PQ): Removes and returns the element with the largest keyword in the queueincreaseKey(PQ, i, key): increments the value of the keyword at queue I to key
Here we define a structure, PriorityQueue, for ease of operation.
typedef struct PriorityQueue {
int capacity;
int size;
int elems[];
} PQ;
Copy the codeThe operation code of the final priority queue is as follows:
/** * Create priority queue from array */ PQ *newPQ(int A[], int n) {PQ * PQ = (PQ *)malloc(sizeof(PQ) + sizeof(int) *n); pq->size = 0; pq->capacity = n; int i;for (i = 0; i < pq->capacity; i++) {
pq->elems[i] = A[i];
pq->size++;
}
buildMaxHeap(pq->elems, pq->size);
return pq;
}
int maximum(PQ *pq)
{
return pq->elems[0];
}
int extractMax(PQ *pq)
{
int max = pq->elems[0];
pq->elems[0] = pq->elems[--pq->size];
maxHeapify(pq->elems, 0, pq->size);
return max;
}
PQ *insert(PQ *pq, int key)
{
int newSize = ++pq->size;
if (newSize > pq->capacity) {
pq->capacity = newSize * 2;
pq = (PQ *)realloc(pq, sizeof(PQ) + sizeof(int) * pq->capacity);
}
pq->elems[newSize-1] = INT_MIN;
increaseKey(pq, newSize-1, key);
return pq;
}
void increaseKey(PQ *pq, int i, int key)
{
int *elems = pq->elems;
elems[i] = key;
while(i > 0 && elems[PARENT(i)] < elems[i]) { swapInt(elems, PARENT(i), i); i = PARENT(i); }}Copy the codeData Structures and Algorithms – Binary tree Basics
Summary of 0.
Before we talk about binary trees, let’s see what a tree is. The basic units of a tree are nodes, and the links between nodes are called branches. The topmost node of a tree is called the root node, and the nodes below are children. A node can have zero or more children, and a node with no children is called a leaf.
Binary tree refers to a tree with no more than two children. It is a very classical data structure. The binary search tree (BST) is an ordered binary tree, and BST must meet the following conditions:
- If the left subtree of any node is not empty, the values of all nodes in the left subtree are less than the values of its root node.
- If the right subtree of any node is not empty, the value of all nodes in the right subtree is greater than or equal to the value of its root node. (Some books define that BST cannot have the same value node, this paper inserts the same value node into the right subtree)
- The left and right subtrees of any node are binary search trees respectively.
Next, this paper will sort out the definition, the addition and deletion of binary search trees, and the recursive and non-recursive traversal of binary trees. The next article will be a comprehensive analysis of classic interview questions related to binary trees. The code for this article is here.
Definition 1.
Let’s first define a binary tree node as follows:
typedef struct BTNode {
int value;
struct BTNode *left;
struct BTNode *right;
} BTNode;
Copy the codeValue stores the value, and the left and right Pointers point to the left and right children, respectively. Binary search trees can use the same structure as binary trees, except for insertion or lookup.
2. Basic operations
Let’s look at some basic operations of binary tree and binary lookup tree, including BST insertion node, BST lookup node, BST maximum and minimum value, number and height of binary tree nodes, etc. Binary search tree (BST) -specific operations are distinguished by a BST prefix, while other functions are common to binary trees.
1) Create a node
To allocate memory, initialize the value
/** * create BTNode */ BTNode *newNode(int value) {BTNode *node = (BTNode *)malloc(sizeof(BTNode)); node->value = value; node->left = node->right = NULL;return node;
}
Copy the code2) BST inserts nodes
Insertion nodes can be implemented recursively or nonrecursively, if the value to be inserted is larger than the root node value, then inserted into the right subtree, otherwise inserted into the left subtree. See the figure below (from Resources 1, 2, and 3) :
/** *bstInsert(BTNode *root, int value) {/** *bstInsert(BTNode *root, int value)if(! root)return newNode(value);
if (root->value > value) {
root->left = bstInsert(root->left, value);
} else {
root->right = bstInsert(root->right, value);
}
returnroot; } /** * BST insert node, non-recursive method */ BTNode *bstInsertIter(BTNode *root, int value) {BTNode *node = newNode(value);if(! root)return node;
BTNode *current = root, *parent = NULL;
while (current) {
parent = current;
if (current->value > value)
current = current->left;
else
current = current->right;
}
if (parent->value >= value)
parent->left = node;
else
parent->right = node;
return root;
}
Copy the code3) BST deletes nodes
Deleting a node is a little more complicated, and there are three cases to consider:
- Delete the leaf node, easy to do, remove the node and the parent of the leaf node
leftorrightThe pointer is null.
- If the node to be deleted has two children, you need to find the largest node in the left subtree of the node (use the following one)
bstSearchIterFunction), and replace its value to the node to be deleted, and then recursively call the deletion function to delete the maximum node of the node’s left subtree.
- If the node to be deleted has only one child, remove the node and fill the value of the child into the deleted node (determine whether it is a left child or a right child).
/** * BTNode *bstDelete(BTNode *root, int value) {BTNode *parent = NULL, *current = root; BTNode *node = bstSearchIter(root, &parent, value);if(! node) {printf("Value not found\n");
return root;
}
if(! node->left && ! // Case 1: the node to be deleted is a leaf nodeif(node ! = root) {if (parent->left == node) {
parent->left = NULL;
} else{ parent->right = NULL; }}else {
root = NULL;
}
free(node);
} else if(node->left && node->right) {// Case 2: The node to be deleted has two children BTNode *predecessor = bstMax(node->left); bstDelete(root, predecessor->value); node->value = predecessor->value; }elseBTNode *child = (node->left)? node->left : node->right;if(node ! = root) {if (node == parent->left)
parent->left = child;
else
parent->right = child;
} else {
root = child;
}
free(node);
}
return root;
}
Copy the code4) BST lookup node
Note that the parent is also recorded in a non-recursive lookup.
/** *bstSearch(BTNode *root, int value) {if(! root)return NULL;
if (root->value == value) {
return root;
} else if (root->value > value) {
return bstSearch(root->left, value);
} else {
returnbstSearch(root->left, value); }} /** *bstSearchIter(BTNode *root, BTNode **parent, int value) {if(! root)return NULL;
BTNode *current = root;
while(current && current->value ! = value) { *parent = current;if (current->value > value)
current = current->left;
else
current = current->right;
}
return current;
}
Copy the code5) BST minimum node and maximum node
The minimum node is recursively found from the left subtree, and the maximum node is recursively found from the right subtree.
/** * BST minimum node */ BTNode *bstMin(BTNode *root)
{
if(! root->left)return root;
return bstMin(root->left); } /** * BST Max */ BTNode *bstMax(BTNode *root) {if(! root->right)return root;
return bstMax(root->right);
}
Copy the code6) Number and height of binary tree nodes
/** * btSize(BTNode *root) {if(! root)return 0;
returnbtSize(root->left) + btSize(root->right) + 1; } /** * binary tree height */ int btHeight(BTNode root) {if(! root)return 0;
int leftHeight = btHeight(root->left);
int rightHeight = btHeight(root->right);
int maxHeight = leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
return maxHeight;
}
Copy the code3. Binary tree traversal
Recursive traversal – pre-order, mid-order, post-order, layer
Binary tree traversal recursive implementation is relatively simple, directly give the code. What is worth mentioning here is the sequential traversal. First, the height of the binary tree is calculated, and then the auxiliary function is called to traverse the nodes of each layer in turn. This method is easier to understand, although it will be higher in time complexity.
/ / void preOrder(BTNode *root) {if(! root)return;
printf("%d ", root->value); preOrder(root->left); preOrder(root->right); } /** * order traversal in binary tree */ voidinOrder(BTNode *root)
{
if(! root)return;
inOrder(root->left);
printf("%d ", root->value);
inOrder(root->right); } /** * postOrder(BTNode *root) {/** postOrder(BTNode *root) {if(! root)return;
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->value); } /** * levelOrder(BTNode *root) {int btHeight = height(root); int level;for(level = 1; level <= btHeight; level++) { levelOrderInLevel(root, level); Void levelOrderInLevel(BTNode *root, int level) {/** * levelOrderInLevel(BTNode *root, int level) {if(! root)return;
if (level == 1) {
printf("%d ", root->value);
return;
}
levelOrderInLevel(root->left, level-1);
levelOrderInLevel(root->right, level-1);
}
Copy the codeNon-recursive traversal – pre-order, mid-order, post-order, hierarchical
- The easiest of the non-recursive traversals is sequential traversal, which uses a stack to hold nodes, accesses the root node first, then pushes the right child and the left child one by one, and repeats the process. Middle-order traversal is a little more complicated, requiring traversing the left subtree first, then the root, and finally the right subtree.
- Back-order traversal uses a stack method
postOrderIter()It’s a little convoluted and fallible. So the two-stack version is recommended for interviewspostOrderIterWith2Stack()“Is easy to understand and write. - Sequential traversal uses queues to assist storage nodes, which is also simple.
- Here I’ve implemented another queue
BTNodeQueueAnd the stackBTNodeStackFor non-recursive traversal of binary trees.
/ * * * * * * * * * * * * * * * * * * * * * / / * * binary tree traversal - non-recursive / / * * * * * * * * * * * * * * * * * * * * * * * * * * / / sequence traversal - first non-recursive * / void preOrderIter (BTNode * root) {if(! root)return;
int size = btSize(root);
BTNodeStack *stack = stackNew(size);
push(stack, root);
while(! IS_EMPTY(stack)) { BTNode *node = pop(stack);printf("%d ", node->value);
if (node->right)
push(stack, node->right);
if(node->left) push(stack, node->left); } free(stack); } /** * order traversal - non-recursive */ voidinOrderIter(BTNode *root)
{
if(! root)return;
BTNodeStack *stack = stackNew(btSize(root));
BTNode *current = root;
while(current || ! IS_EMPTY(stack)) {if (current) {
push(stack, current);
current = current->left;
} else {
BTNode *node = pop(stack);
printf("%d ", node->value); current = node->right; } } free(stack); Void postOrderIter(BTNode *root) {BTNodeStack *stack = stackNew(btSize(root)); BTNode *current = root;do{// move to the left-most nodewhile(current) {// Push this node to the right child and itselfif(current->right) push(stack, current->right); push(stack, current); Current = current->left; } current = pop(stack);if (current->right && peek(stack) == current->right) {
pop(stack);
push(stack, current);
current = current->right;
} else {
printf("%d ", current->value); current = NULL; }}while(! IS_EMPTY(stack)); } /** * subsequent traversal - use two stacks for better understanding. */ void postOrderIterWith2Stack(BTNode *root) {if(! root)return;
BTNodeStack *stack = stackNew(btSize(root));
BTNodeStack *output = stackNew(btSize(root));
push(stack, root);
BTNode *node;
while(! IS_EMPTY(stack)) { node = pop(stack); push(output, node);if (node->left)
push(stack, node->left);
if (node->right)
push(stack, node->right);
}
while(! IS_EMPTY(output)) { node = pop(output);printf("%d ", node->value); /** * levelOrderIter(BTNode *root) {/** * levelOrderIter(BTNode *root) {if(! root)return;
BTNodeQueue *queue = queueNew(btSize(root));
enqueue(queue, root);
while (1) {
int nodeCount = QUEUE_SIZE(queue);
if (nodeCount == 0)
break;
btHeight
while (nodeCount > 0) {
BTNode *node = dequeue(queue);
printf("%d ", node->value);
if (node->left)
enqueue(queue, node->left);
if (node->right)
enqueue(queue, node->right);
nodeCount--;
}
printf("\n"); }}Copy the codeData structures and algorithms – Binary tree interview questions
Summary of 0.
After summarizing the basic operation of binary tree in the previous article, this article summarizes the common binary tree-related interview questions, which are mainly divided into six kinds of big questions, such as judgment, construction, storage, search, distance and mixing. All the code for this article is here.
1. Judgment questions
The judgment problem can be divided into three parts: whether a binary tree is a binary search tree, a binary complete tree, and whether two binary trees are isomorphic.
1.1 Determining whether a Binary tree is a binary search tree (BST)
Given a binary tree, determine whether the binary tree is a binary search tree.
A binary search tree is a binary tree, but it has some additional constraints that must be true for each node:
- All nodes in the left subtree of a node are less than or equal to that node.
- All nodes in the right subtree of a node have values greater than that node.
- The left and right subtrees of a node must also be binary search trees.
A wrong solution
At first glance, this problem is easy to implement: suppose the current node value is k, for each node in the binary tree, determine whether the value of its left child is less than k, and its right child is greater than k. If all nodes meet this condition, the binary tree is a binary search tree. The implementation code is as follows:
int isBSTError(BTNode *root)
{
if(! root)return 1;
if (root->left && root->left->value >= root->value)
return 0;
if (root->right && root->right->value < root->value)
return 0;
if(! isBSTError(root->left) || ! isBSTError(root->right))return 0;
return 1;
}
Copy the codeUnfortunately, this is a mistake, as the following binary tree satisfies the above criteria, but it is not a binary search tree.
10 / \ 5 15 -------- binary tree(1) Binary tree that meets the above criteria, but is not a binary search tree. / \ 20 JuneCopy the codeSolution 1: Brute force method
The above error solution is caused by incomplete judgment, which can be judged as follows:
- Determine whether the maximum value of the left subtree of the node is greater than or equal to the value of the node. If so, the binary tree is not a binary search tree. Otherwise, proceed to the next step.
- Determine whether the minimum value of the right subtree is less than or equal to the value of the node. If so, it is not a binary search tree. Otherwise, proceed to the next step.
- Recursively determine whether the left and right subtrees are binary search trees. (In code
bstMax和bstMinThe binary search () function returns the maximum and minimum nodes in a binary tree.
int isBSTUnefficient(BTNode *root)
{
if(! root)return 1;
if (root->left && bstMax(root->left)->value >= root->value)
return 0;
if (root->right && bstMin(root->right)->value < root->value)
return 0;
if(! isBSTUnefficient(root->left) || ! isBSTUnefficient(root->right))return 0;
return 1;
}
Copy the codeSolution 2: One pass
In the example of binary Tree (1) mentioned above, when we traverse to node 15, we know that the right subtree must all be >=10. When we go to the left child of node 15, node 6, we know that each of the left subtrees of node 15 has to be between 10 and 15. Obviously, node 6 does not meet the criteria, so it is not a binary search tree.
int isBSTEfficient(BTNode* root, BTNode *left, BTNode *right)
{
if(! root)return 1;
if (left && root->value <= left->value)
return 0;
if (right && root->value > right->value)
return 0;
return isBSTEfficient(root->left, left, root) && isBSTEfficient(root->right, root, right);
}
Copy the codeSolution 3: middle order ergodic solution
We can also simulate the tree’s middle order traversal to judge BST. We can directly save the result of middle order traversal to an auxiliary array, and then judge whether the array is in order to judge whether it is BST. Of course, we can determine the BST solution by reserving the previous pointer prev during traversal without using the auxiliary array. Prev = NULL initially.
int isBSTInOrder(BTNode *root, BTNode *prev)
{
if(! root)return 1;
if(! isBSTInOrder(root->left, prev))return 0;
if (prev && root->value < prev->value)
return 0;
return isBSTInOrder(root->right, root);
}
Copy the code1.2 Determine whether a binary tree is a complete binary tree
Problem: given a binary tree, the binary tree is a complete binary tree (complete binary tree definition: if the depth of a binary tree for h, in addition to the first h layer, other layers () ~ 1 h – 1 nodes can reach maximum number, the first h layer all nodes continuous focus on the left, this is the complete binary tree, as shown in the figure below).
Solution 1: Conventional solution – middle order traversal
First define the concept of a full node: that is, if a node has left and right child nodes, it is a full node. The variable flag is defined in the code to identify whether non-full nodes are found. A value of 1 indicates that the binary tree has non-full nodes. If there are non-full nodes in a complete binary tree, the remaining nodes in the traversal queue must be leaf nodes, and if the left child of a node is empty, the right child of a node must also be empty.
int isCompleteBTLevelOrder(BTNode *root)
{
if(! root)return 1;
BTNodeQueue *queue = queueNew(btSize(root));
enqueue(queue, root);
int flag = 0;
while (QUEUE_SIZE(queue) > 0) {
BTNode *node = dequeue(queue);
if (node->left) {
if (flag) return 0;
enqueue(queue, node->left);
} else {
flag = 1;
}
if (node->right) {
if (flag) return 0;
enqueue(queue, node->right);
} else{ flag = 1; }}return 1;
}
Copy the codeSolution 2: simpler method – determine the node number method
A simpler method is to judge the node ordinal method, because the node Ordinal Numbers of a complete binary tree are regular. For example, the left and right child Ordinal Numbers of node I are 2I +1 and 2I +2. For example, the root node ordinal number is 0, its left and right child Ordinal Numbers are 1 and 2 (if both exist). We can count the number of nodes in a binary tree, and then we can order all the nodes, and if it’s not a perfect binary tree, then there must be some nodes whose numbers are greater than or equal to the number of nodes. Binary tree(1), for example, is not a complete binary tree.
10(0) / \ 5(1) 15(2) - The number of nodes is 5. If it was a complete binary tree, the maximum number of nodes would be 4, and it's 6, so it's not. / \ 6 (5) 20 (6)Copy the codeThe implementation code is as follows:
int isCompleteBTIndexMethod(BTNode *root, int index, int nodeCount)
{
if(! root)return 1;
if (index >= nodeCount)
return 0;
return (isCompleteBTIndexMethod(root->left, 2*index+1, nodeCount) &&
isCompleteBTIndexMethod(root->right, 2*index+2, nodeCount));
}
Copy the code1.3 Judge the balanced binary tree
Determine if a binary tree is a balanced binary tree. A balanced binary tree means that the height difference between the left and right subtrees of any node is no more than 1.
__2__ / \ 1 4 ---- Balanced binary tree example \ / \ 3 5 6Copy the codeSolution 1: Top-down method
To determine whether a binary tree is balanced, calculate whether the height difference between the left and right subtrees is greater than 1 for each node, and the time complexity is O(N^2).
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 codeSolution 2: Bottom-up method
Because solution 1 repeatedly traverses many nodes, we can adopt a similar way of post-order traversal to judge the height difference between the left and right subtrees from bottom up, so the time complexity is O(N).
int isBalanceBTDown2Top(BTNode *root, int *height)
{
if(! root) { *height = 0;return 1;
}
int leftHeight, rightHeight;
if (isBalanceBTDown2Top(root->left, &leftHeight) &&
isBalanceBTDown2Top(root->right, &rightHeight)) {
int diff = abs(leftHeight - rightHeight);
returndiff > 1 ? 0:1; }return 0;
}
Copy the code1.4 Determine whether two binary trees are isomorphic
Given two binary trees whose roots are T1 and T2, determine whether the two binary trees are isomorphic. The so-called binary tree isomorphism means that they have the same structure. The following binary trees (1) and (2) are isomorphic, but they and (3) have different structures:
5 9 6 / \ / \ / 12 7 12 5 9 / \ / \ 4 3 5 8 10 Binary tree (1) binary tree (2)Copy the codeSolution: Whether the binary tree structure is the same, or recursive implementation, first judge whether the root is isomorphic, and then judge the left and right subtrees.
int isOmorphism(BTNode *t1, BTNode *t2)
{
if(! t1 || ! t2)return(! t1) && (! t2);return isOmorphism(t1->left, t2->left) && isOmorphism(t1->right, t2->right);
}
Copy the code2. Build class problems
The problem of constructing a class is to use two kinds of traversal order of binary tree to determine another traversal order of binary tree. In the last article, we analyzed the recursive and non-recursive implementation of pre-ordered, middle-ordered, post-ordered traversal of binary trees. Is it possible to uniquely determine a binary tree according to preorder, middle order, or preorder, or post-order, or middle-order, post-order?
The answer is that in a binary tree without repeated values, a binary tree cannot be uniquely determined by pre-order and post-order traversal, but can be uniquely determined by pre-order, middle-order or middle-order and post-order traversal.
1) Sequential and sequential traversal cannot uniquely determine a binary tree
A simple example is as follows: the pre-ordered traversal and post-ordered traversal of these two binary trees are the same, thus proving that pre-ordered traversal and post-ordered traversal cannot uniquely determine a binary tree.
1 1 / / 2 2 \ / 3 3 the first order traversal: 1 2 3 the last order traversal: 3 2 1Copy the code2) Pre-ordered and middle-ordered traversals can uniquely determine binary trees
Simple proof: Because the first element of sequential traversal is the root node, this element divides the sequential traversal sequence in the binary tree into two parts. The left side (assuming L elements) represents the left subtree. If there is no element on the left side, it means that the left subtree is empty. The right-hand side (assuming R elements) is the right subtree, and if it is empty, the right subtree is empty. According to the order of “root-left subtree – right subtree” in the preceding traversal, the left subtree is constructed from the sequence of L nodes starting from the second element of the preceding sequence and the sequence of L nodes left from the root of the middle sequence, and the right subtree is constructed from the sequence of the last R elements of the preceding sequence and the sequence of R elements to the right of the root of the middle sequence.
3) Middle-order and post-order traversal can uniquely determine the binary tree
Simple proof: assume the node number of binary tree is N, assume the middle order traversal is S1, S2… , Sn, and then sequence traversal is P1, P2… , Pn, since the last node Pn of post-order traversal is the root node, then the middle-order traversal can be divided into two parts according to Pn, in which L nodes on the left are left subtree nodes and R nodes on the right are right subtree nodes, then 1-L nodes in post-order traversal are post-order traversal of the left subtree, thus PL is the root of the left subtree. Similarly, the middle-order traversal can be divided into two parts until the binary tree is finally determined.
2.1 Build a binary tree based on pre-order and middle-order traversal
Given a binary tree traversal sequence, construct the binary tree (note: the binary tree has no duplicate values).
The binary tree is as follows: 7 / \ 10 2 / \ / 4 3 8 \ / 1 11Copy the codeSolution: Solve the problem according to the previous analysis.
- The first node in a sequential traversal is always the root. As in the binary tree above, the root is 7.
- You can observe that in the middle-order traversal, root 7 is the fourth value (starting from 0). Because the middle order traversal order is: left subtree, root node, right subtree. So it’s to the left of the root of 7
,10,3,1 {4}These four nodes belong to the left subtree, and root 7 is to the right11,8,2 {}It’s in the right subtree. - So we can write a recurrence from that. Notice how to get the position of the root in the middle traversal using a linear scan to find the position, every time you need to find it, okay
O(N)The entire algorithm takesO(N^2)The time. If you want to improve efficiency, you can also use a hash table to store and find the position of the root node in the middle order traversalO(1)In order to build the whole treeO(N)The time. - The call method is
buildBTFromPreInOrder(preorder, inorder, n, 0, n);, includingpreorder和inorderRespectively are the sequential sequential traversal number group,nIs the array size.
/** * auxiliary function to find the position of the root in the middle order traversal. */ int findBTRootIndex(int inorder[], int count, int rootVal) { int i;for (i = 0; i < count; i++) {
if (inorder[i] == rootVal)
return i;
}
return- 1; */ BTNode *buildBTFromPreInOrder(int preorder[], int inorder[], int n, int offset, int count) {if (n == 0) returnNULL; int rootVal = preorder[0]; int rootIndex = findBTRootIndex(inorder, count, rootVal); int leftCount = rootIndex - offset; Int rightCount = n-leftcount - 1; BTNode *root = btNewNode(rootVal); root->left = buildBTFromPreInOrder(preorder+1, inorder, leftCount, offset, count); root->right = buildBTFromPreInOrder(preorder+leftCount+1, inorder, rightCount, offset+leftCount+1, count);return root;
}
Copy the codeThe binary tree is constructed according to middle-order and back-order traversal
Given a binary tree with a middle-order and post-order traversal sequence, construct the binary tree (note: the binary tree has no duplicate values).
Middle order traversal: 4 10 3 1 7 11 8 2 Rear order traversal: 4 1 3 10 11 8 2 7 binary tree: 7 / \ 10 2 / \ / 4 3 8 \ / 1 11Copy the codeSolution: Similar to the previous problem, except that the root is taken from the last element in the sequence.
/* / BTNode *buildBTFromInPostOrder(int postorder[], int inorder[], int n, int offset, int count) {if (n == 0) returnNULL; int rootVal = postorder[n-1]; int rootIndex = findBTRootIndex(inorder, count, rootVal); int leftCount = rootIndex - offset; Int rightCount = n-leftcount - 1; BTNode *root = btNewNode(rootVal); root->left = buildBTFromInPostOrder(postorder, inorder, leftCount, offset, count); root->right = buildBTFromInPostOrder(postorder+leftCount, inorder, rightCount, offset+leftCount+1, count);return root;
}
Copy the code3. Storage problems
3.1 Binary search tree storage and recovery
Design an algorithm to save a binary search tree (BST) to a file, need to be able to restore the original binary search tree from the file, pay attention to the space-time complexity of the algorithm.
30
/ \
20 40
/ / \
10 35 50
Copy the codeTrain of thought
Binary tree traversal calculation method has preorder traversal, middle order traversal, after order traversal calculation method. But which of these can be used to save the BST to a file and recover the original BST from the file is a question to consider.
Suppose that the middle order traversal is used, because the middle order traversal of this BST tree is 10, 20, 30, 35, 40, 50. The possible structure is as follows, so the middle order traversal does not meet the requirements.
50/40/35/30/20/10Copy the codeSince middle order traversal can’t, how about post order traversal? After traversing the BST, the following results can be obtained: 10, 20, 35, 50, 40, 30. It is difficult to read these nodes and construct the original BST, because in the construction of binary tree, the parent node is constructed first and then the child node is inserted, and the sequential traversal sequence reads the child node first and then the parent node, so the subsequent traversal does not meet the conditions.
In summary, only sequential traversal satisfies the condition. The sequential traversal of the BST is 30, 20, 10, 40, 35, 50. One important observation is that the parent of a node is always printed before that node. With this observation, after we read the sequence of BST nodes from the file, we can always construct their parents before constructing the children. The code for writing the BST to the file is the same as the sequential traversal.
So what does read recovery do? Use the binary search tree bstInsert() method to perform N inserts. If the binary search tree is balanced, each insert takes O(lgN), O(NlgN), and O(N^2) in the worst case.
Void bstSave(BTNode *root, FILE *fp) {if(! root)return;
char temp[30];
sprintf(temp, "%d\n", root->value); fputs(temp, fp); bstSave(root->left, fp); bstSave(root->right, fp); } /** * restore binary tree from FILE */ BTNode *bstRestore(FILE *fp) {BTNode *root = NULL; char *s; char buf[30];while ((s = fgets(buf, 30, fp))) {
int nodeValue = atoi(s);
root = bstInsert(root, nodeValue);
}
return root;
}
Copy the code3.2 Binary tree storage and recovery
Design an algorithm that implements binary tree (note, not binary search tree BST) storage and recovery.
The binary search tree can be saved and restored using a sequential traversal in section 3.1. However, we can use the idea of sequential traversal, but we need to change it here. In order for nodes to be inserted into the correct positions during reconstruction of the binary tree, NULL nodes need to be saved when the binary tree is saved into the file using a preemptive traversal (special symbols such as # can be used to identify NULL nodes).
Note: in this case, there is a defect in using # to store NULL nodes. For example, in this method, the value of binary tree node cannot be #. If you want to be able to save various characters, you need to do it in another way.
30
/ \
10 20
/ / \
50 45 35
Copy the codeFor the binary tree above, save to a file as 30, 10, 50 # #, 20, 45 # #, 35 # #. Thus, the code for saving and restoring the implementation looks like this:
Void btSave(BTNode *root, FILE *fp) {if(! root) { fputs("#\n", fp);
} else {
char temp[30];
sprintf(temp, "%d\n", root->value); fputs(temp, fp); btSave(root->left, fp); btSave(root->right, fp); } /** * Recover binary tree from FILE */ BTNode *btRestore(BTNode *root, FILE *fp) {char buf[30]; char *s = fgets(buf, 30, fp);if(! s || strcmp(s,"#\n") = = 0)return NULL;
int nodeValue = atoi(s);
root = btNewNode(nodeValue);
root->left = btRestore(root->left, fp);
root->right = btRestore(root->right, fp);
return root;
}
Copy the code4. Find class problems
Search class problems mainly include: find the lowest common ancestor node of binary tree/binary search tree, or the largest subtree in the binary tree and the subtree is binary search tree, etc.
4.1 Lowest common ancestor node of binary search tree
Given a binary search tree (BST), find the lowest common ancestor node (LCA) of the two nodes in the tree. For example, in the following binary tree, the LCA of node 2 and node 8 is 6, while that of node 4 and node 2 is 2.
______6______ / \ __2__ __8__ / \ \ 0 4 July 9 / \ 3 5Copy the codeSolution: When we traverse the binary search tree from the top down, for each node traversed, the two nodes of the LCA may have the following four distributions:
- 1) Both nodes are in the left subtree of the tree: LCA must be in the left subtree of the current traversal node.
- 2) Both nodes are in the right subtree of the tree: LCA must be in the right subtree of the current traversal node.
- 3) One node is on the left and one node is on the right of the tree: LCA is the node currently traversed.
- 4) The current node is equal to one of these two nodes: LCA is also the current traversal node.
BTNode *bstLCA(BTNode *root, BTNode *p, BTNode *q)
{
if(! root || ! p || ! q)return NULL;
int maxValue = p->value >= q->value ? p->value : q->value;
int minValue = p->value < q->value ? p->value : q->value;
if (maxValue < root->value) {
return bstLCA(root->left, p, q);
} else if (minValue > root->value) {
return bstLCA(root->right, p, q);
} else {
returnroot; }}Copy the code4.2 The lowest common ancestor of binary tree (not necessarily BST)
Given two nodes in a binary tree, print the lowest common ancestor (LCA) of the two nodes. Note that the binary tree is not necessarily a binary search tree.
_______3______ / \ ___5__ ___1__ / \ \ 6 2 0 8 / \ 7 4Copy the codeSolution 1: Top-down method
It doesn’t have to be BST, so you can’t tell by the size of the value, but the general idea is the same: we can start from the root node and determine whether the left and right subtrees of the current node contain both nodes.
- If the left subtree contains two nodes, their lowest common ancestor must also be in the left subtree.
- If the right subtree contains two nodes, their lowest common ancestor must also be in the right subtree.
- If one node is in the left subtree and the other node is in the right subtree, the current node is their lowest common ancestor.
Since the position of node P and q needs to be judged repeatedly for each node, the total time complexity is O(N^2). Therefore, we can consider finding a more efficient method.
O(N^2) */ BTNode *btLCATop2Down(BTNode *root, BTNode *p, BTNode *q) {if(! root || ! p || ! q)return NULL;
if (btExist(root->left, p) && btExist(root->left, q)) {
return btLCATop2Down(root->left, p, q);
} else if (btExist(root->right, p) && btExist(root->right, q)) {
return btLCATop2Down(root->right, p, q);
} else {
returnroot; */ int btExist(BTNode *root, BTNode *node) {if(! root)return 0;
if (root == node) return 1;
return btExist(root->left, node) || btExist(root->right, node);
}
Copy the codeSolution 2: Bottom-up method
Because the top-down method has a lot of repeated judgments, we have this bottom-up method. Walk through a node from the bottom up, passing it up to its parent as soon as it encounters a node equal to p or q. The parent determines whether its left and right subtrees contain one of these nodes, and if so, the parent must be the LCA of these two nodes p and Q. If not, we pass up any children that contain either p or q, or NULL (if there is no p or Q in the left and right subtrees). Time complexity of this method is O(N).
O(N) */ BTNode */ btLCADown2Top(BTNode *root, BTNode *p, BTNode *q) {if(! root)return NULL;
if (root == p || root == q) return root;
BTNode *left = btLCADown2Top(root->left, p, q);
BTNode *right = btLCADown2Top(root->right, p, q);
if (left && right)
returnroot; // If p and q are in different subtreesreturnleft ? left: right; //p and q are in the same subtree, or p and q are not in the subtree}Copy the code4.3 Maximum binary search subtree of binary tree
Find the largest subtree in a binary tree. The subtree is a binary search tree. The largest subtree is the one with the largest number of nodes.
___10___
/ \
_5_ 15
/ \ \
1 8 7
___10____
/ \
_5_ 15 -------- subtree (1)
/ \
1 8
_5_
/ \ -------- subtree (2)
1 8
Copy the codeAccording to wikipedia’s definition of a subtree, the subtree of a binary tree T consists of some node of T and all of its descendants. In other words, subtree(2) is the correct answer because subtree(1) does not contain node 7 and does not satisfy the definition of a subtree.
Solution 1: top-down solution
The most natural solution is to traverse all nodes of the binary tree starting from the root node and determine whether the subtree rooted at the current node is BST. If so, the BST rooted at the current node is the largest BST. If not, the left and right subtrees are recursively called to return the subtree containing more nodes.
BTNode *largestSubBSTTop2Down(BTNode *root, int *bstSize) {if(! root) { *bstSize = 0;return NULL;
}
if(isBSTEfficient(root, NULL, NULL)) {// If the root tree isBST, set the result to root and return. *bstSize = btSize(root);returnroot; } int lmax, rmax; BTNode *leftBST = largestSubBSTTop2Down(root->left, &lmax); BTNode *rightBST = largestSubBSTTop2Down(root->right, &rmax); *bstSize = lmax > rmax? lmax : rmax; BTNode *result = lmax > rmax? leftBST : rightBST;return result;
}
Copy the codeSolution 2: Bottom-up solution
The time complexity of the top-down solution is O(N^2), and each node needs to determine whether it meets the conditions of BST, which can be optimized by the bottom-up method. We already know whether the subtree with the root of the bottom node is BST before judging whether the subtree with the root of the top node is BST. Therefore, as long as the subtree with the root of the bottom node is not BST, the subtree with the root of the top node must not be BST. We can record the number of nodes in the subtree, and then compare it with the binary tree of the parent node to find the maximum BST subtree.
BTNode *largestSubBSTDown2Top(BTNode *root, int *bstSize) {BTNode *largestBST = NULL; int min, max, maxNodes=0; findLargestSubBST(root, &min, &max, &maxNodes, &largestBST); *bstSize = maxNodes;returnlargestBST; } /** * return the number of BST nodes, Otherwise return -1 */ int findLargestSubBST(BTNode *root, int *min, int * Max, int *maxNodes, BTNode **largestSubBST) {if(! root)return 0;
int isBST = 1;
int leftNodes = findLargestSubBST(root->left, min, max, maxNodes, largestSubBST);
int currMin = (leftNodes == 0) ? root->value : *min;
if(leftNodes == -1 || (leftNodes ! = 0 && root->value <= *max)) isBST = 0; int rightNodes = findLargestSubBST(root->right, min, max, maxNodes, largestSubBST); int currMax = (rightNodes == 0) ? root->value : *max;if(rightNodes == -1 || (rightNodes ! = 0 && root->value > *min)) isBST = 0;if(! isBST)return- 1; *min = currMin;
*max = currMax;
int totalNodes = leftNodes + rightNodes + 1;
if (totalNodes > *maxNodes) {
*maxNodes = totalNodes;
*largestSubBST = root;
}
return totalNodes;
}
Copy the code5. Distance problems
5.1 Shortest distance between two nodes of a binary tree
Given two nodes in a binary tree, find the shortest distance between these two nodes (note: the shortest distance refers to the number of edges needed to get from one node to another node).
___1___
/ \
2 3
/ \ / \
4 5 6 7
\
8
Distance(4, 5) = 2
Distance(4, 6) = 4
Distance(3, 4) = 3
Distance(2, 4) = 1
Distance(8, 5) = 5
Copy the codeSolution: The distance between two nodes is easier to handle. First, calculate the lowest common ancestor node (LCA) of two nodes, and then calculate the sum of the distance between LCA and two nodes. The time complexity is O(N).
/** * Calculate the shortest distance between two nodes of the binary tree */ int distanceOf2BTNodes(BTNode *root, BTNode *p, BTNode *q) {if(! root)return 0;
BTNode *lca = btLCADown2Top(root, p, q);
int d1 = btDistanceFromRoot(lca, p, 0);
int d2 = btDistanceFromRoot(lca, q, 0);
returnd1+d2; } /** * calculate the distance between btDistanceFromRoot */ int btDistanceFromRoot(BTNode *root, BTNode *node, int level) {if(! root)return- 1;if (root == node) return level;
int left = btDistanceFromRoot(root->left, node, level+1);
if (left == -1)
return btDistanceFromRoot(root->right, node, level+1);
return left;
}
Copy the code5.2 Shortest distance between two nodes of binary search tree
Find the shortest distance between two nodes in a binary search tree.
Solution: Unlike the previous, this is a BST, so we can use the binary search tree features to simplify the distance calculation process, of course, it is perfectly OK to directly use 5.1 method, because it is a general calculation method.
/** * Calculate the shortest distance between two nodes of BST. */ int distanceOf2BSTNodes(BTNode *root, BTNode *p, BTNode *q) {if(! root)return 0;
if (root->value > p->value && root->value > q->value) {
return distanceOf2BSTNodes(root->left, p, q);
} else if(root->value <= p->value && root->value <= q->value){
return distanceOf2BSTNodes(root->right, p, q);
} else {
returnbstDistanceFromRoot(root, p) + bstDistanceFromRoot(root, q); */ int bstDistanceFromRoot(BTNode *root, BTNode *node) {/** * bstDistanceFromRoot(BTNode *root, BTNode *node) {if (root->value == node->value)
return 0;
else if (root->value > node->value)
return 1 + bstDistanceFromRoot(root->left, node);
else
return 1 + bstDistanceFromRoot(root->right, node);
}
Copy the code5.3 Maximum distance of nodes in a binary tree
Write a program to find the distance between the two farthest nodes in a binary tree.
Solution: The beauty of Programming has this problem, which is different from the previous problem, the distance between the two farthest nodes, and does not specify the location of the two nodes. There are two cases for calculating the maximum distance of a binary tree:
- 1) The path is the deepest node of the left subtree -> root node -> the deepest node of the right subtree.
- 2) The path does not pass through the root node, but is the maximum distance path of the left or right subtree, whichever is greater.
___10___ / \ _5_ 15 -- -- -- -- -- - 1 case / \ \ 1 8 7 10/5 / \ -- -- -- -- -- - 1 8 / \ 2, 3, 2 kinds of situationCopy the codeWe define the function maxDistanceOfBT(BTNode *root) to calculate the distance between the two nodes farthest from each other in the binary tree. We can recursively calculate the distance between the two nodes farthest from each other in the binary tree, and then compare the sum of the distance between the left and right subtrees, the distance between the right and left subtrees, and the maximum depth of the left and right subtrees. So we can figure out the distance between the two farthest nodes of the whole binary tree.
int btMaxDistance(BTNode *root, int *maxDepth)
{
if(! root) { *maxDepth = 0;return0; } int leftMaxDepth, rightMaxDepth; int leftMaxDistance = btMaxDistance(root->left, &leftMaxDepth); int rightMaxDistance = btMaxDistance(root->right, &rightMaxDepth); *maxDepth = max(leftMaxDepth+1, rightMaxDepth+1); int maxDistance = max3(leftMaxDistance, rightMaxDistance, leftMaxDepth+rightMaxDepth); // select * from max3; // select * from max3return maxDistance;
}
Copy the code5.4 Maximum width of a binary tree
Given a binary tree, find the maximum width of the binary tree. The width of a binary tree refers to the number of nodes at each level. For example, the following binary tree has a width of 1, 2, 3, 2 from top to bottom, so its maximum width is 3.
1 / \ 2 3 / \ 4 5 8 / \ 6 7Copy the codeSolution 1: Sequence traversal method
The easiest way to think about it is to use sequential traversal, then count the number of nodes for each layer, and then get the maximum number of nodes. Time complexity of this method is O(N^2). Of course, if optimized to use the queue to achieve the sequence traversal, O(N) time complexity can be obtained.
/** * btMaxWidth(BTNode *root) {int h = btHeight(root); int level, width; int maxWidth = 0;for (level = 1; level <= h; level++) {
width = btLevelWidth(root, level);
if (width > maxWidth)
maxWidth = width;
}
returnmaxWidth; } /** * btLevelWidth(BTNode *root, int level) {if(! root)return 0;
if (level == 1) return 1;
return btLevelWidth(root->left, level-1) + btLevelWidth(root->right, level-1);
}
Copy the codeSolution 2: Sequential traversal
We can start by creating an auxiliary array of size h of the height of the binary tree to store the width of each layer, initialized to 0. The binary tree is traversed by sequential traversal, and the width of each layer is set. And then finally, we take the maximum from this auxiliary array which is the maximum width of the binary tree.
/** * btMaxWidthPreOrder(BTNode *root) {int h = btHeight(root); int *count = (int *)calloc(sizeof(int), h); btLevelWidthCount(root, 0, count); int i, maxWidth = 0;for (i = 0; i < h; i++) {
if (count[i] > maxWidth)
maxWidth = count[i];
}
returnmaxWidth; } /** * calculates the width of each level of the binary tree from level and stores it in the array count. */ void btLevelWidthCount(BTNode *root, int level, int count[]) {if(! root)return;
count[level]++;
btLevelWidthCount(root->left, level+1, count);
btLevelWidthCount(root->right, level+1, count);
}
Copy the code6. Mixed questions
This kind of problem mainly investigates the combination of binary tree and linked list/array, and the form is novel.
6.1 Building a balanced binary search tree based on ordered arrays
Given an ordered array with elements in ascending order, try to construct a Balanced Binary Search Tree based on the elements. The definition of balance is that the height difference between the subtrees of a binary tree cannot be more than 1.
__3__ / \ 15 ---- Example of balanced binary search tree \ / \ 24 6Copy the codeSolution: If you want to select an element from an ordered array as the root, which element should you select? We should choose the middle element of the ordered array as the root. Once the middle element is selected as the root and created, the remaining elements are divided into two parts, which can be thought of as two arrays. This leaves the elements to the left of the root as the left subtree, and the elements to the right as the right subtree.
BTNode *sortedArray2BST(int a[], int start, int end)
{
if (start > end) return NULL;
int mid = start + (end-start)/2;
BTNode *root = btNewNode(a[mid]);
root->left = sortedArray2BST(a, start, mid-1);
root->right = sortedArray2BST(a, mid+1, end);
return root;
}
Copy the code6.2 Ordered unidirectional Linked list construction of balanced binary search tree
Given an ordered unidirectional list, construct a balanced binary search tree.
Solution: The most natural idea is to store the values of the nodes in the linked list in an array, and then implement the method in 6.1 with O(N) time. We can also take a bottom-up approach, where we no longer need to look for the middle element every time.
The following code still needs the length of the linked list as a parameter, the time complexity of calculating the length of the linked list is O(N), and the time complexity of the algorithm is also O(N), so the total time complexity is O(N). Note that the list position changes every time sortedList2BST is called. The list position always points to mid+1 after the function is called (if the return condition is met, the list position remains the same).
BTNode *sortedList2BST(ListNode **pList, int start, int end)
{
if (start > end) return NULL;
int mid = start + (end-start)/2;
BTNode *left = sortedList2BST(pList, start, mid-1);
BTNode *parent = btNewNode((*pList)->value);
parent->left = left;
*pList = (*pList)->next;
parent->right = sortedList2BST(pList, mid+1, end);
return parent;
}
Copy the codeFor example, if there are only two nodes 3->5->NULL in the linked list, then the initial start=0, end=1, mid=0, and then recursively call sortedList2BST(pList, start,mid-1), and then directly return NULL. SortedList2BST (pList, mid+1, end) returns node 5 and assigns it to the right child of root 3. This call with mid=1 and the list pointing to the end of the list.
6.3 Binary search tree is converted to an ordered circular list
Given a binary search tree (BST), convert it to a bidirectional ordered circular linked list.
Solution: As shown in the figure, we need to replace the left and right child Pointers of the BST with the prev and next Pointers to the first and last node of the bidirectional list, respectively. Most people’s first reaction is to walk through the binary tree in middle order, changing the left and right Pointers of the nodes in the tree. The extra consideration here is how to point the last node’s right pointer to the first node, as shown below.
When traversing a binary tree in middle order, each time we traverse a node, we can change the left pointer of that node to point to the node we traversed before, because we don’t need the left pointer in subsequent operations; At the same time, we also need to change the right pointer of the previous traversal node so that the right pointer of the previous traversal node points to the current node. For example, if we walk to node 2, we change the left pointer of node 2 to point to node 1, and we also need to change the right pointer of node 1 to point to node 2. Notice that the previous traversal node here is not the parent of the current node, but the previous smaller node of the current node.
It looks like we’ve solved the problem, but wait, we’re actually two important steps behind. 1) We do not assign head to the head node. 2) The last node pointer does not point to the first node.
The solution to these two problems is very simple: on each recursive call, update the right pointer to the current traversal node to point to the head, and update the left pointer to the head node to point to the current traversal node. When the recursive call ends, the first and last nodes of the list point to the correct location. Don’t forget the special case of a single node where both the left and right Pointers point to itself.
void bt2DoublyList(BTNode *node, BTNode **pPrev, BTNode **pHead)
{
if(! node)return; bt2DoublyList(node->left, pPrev, pHead); PPrev node->left = *pPrev;if(*pPrev) (*pPrev)->right = node; // The right of the previous node points to the current nodeelse*pHead = node; // If there is no previous node, set head to the current node (the current node is the smallest node). The left pointer of head points to the last node, and the right pointer of the last node points to the head node. // Save the right pointer to the current node, as it will be modified later in the code. BTNode *right = node->right; (*pHead)->left = node; node->right = (*pHead); *pPrev = node; // Update the previous node bt2DoublyList(right, pPrev, pHead); }Copy the codeThis solution is very clever, because the algorithm is an improvement on the middle order traversal, so its time complexity is O(N), N is the number of nodes. Of course, we add an extra assignment to each recursive call compared to a middle-order traversal.
Series 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
- C Expert Programming
- Linux C One-stop Programming
- High Quality C/C++ programming
- Structure byte alignment
- The flexible array
- Sliding Window Maximum – LeetCode
- Longest Palindromic Substring – LeetCode
- The programming of mission
- Introduction to algorithms
- MIT6.828 code
- Detect loop in a linked list – GeeksforGeeks
- Determine whether a single linked list has a ring, determine whether two linked list intersects the problem in detail
- Find first node of loop in a linked list – GeeksforGeeks
- Merge two sorted linked list without duplicates – GeeksforGeeks
- Stack Implementation in C – Techie Delight
- Stack | Set 4 (Evaluation of Postfix Expression) – GeeksforGeeks
- Reverse a stack using recursion – GeeksforGeeks
- Introduction to Algorithms Chapter 6 heapsort
- Insertion in BST | Recursive & Iterative Solution – Techie Delight
- Search given key in BST | Recursive & Iterative Solution – Techie Delight
- Iterative Postorder Traversal | Set 2 (Using One Stack) – GeeksforGeeks
- A program to check if a binary tree is BST or not – GeeksforGeeks
- Check whether a given Binary Tree is Complete or not | Set 1 (Iterative Solution) – GeeksforGeeks
- Check whether a binary tree is a complete tree or not | Set 2 (Recursive Solution) – GeeksforGeeks
- Serialization/Deserialization of a Binary Tree – LeetCode
- Lowest Common Ancestor of a Binary Search Tree (BST) — LeetCode
- Largest Subtree Which is a Binary Search Tree (BST) — LeetCode
- Find distance between two nodes of a Binary Tree – GeeksforGeeks
- Shortest distance between two nodes in BST – GeeksforGeeks
- Maximum width of a binary tree – GeeksforGeeks
- Convert Sorted List to Balanced Binary Search Tree (BST) — LeetCode
- Convert Binary Search Tree (BST) to Sorted doubly-linked List — LeetCode
- 100 questions (60)- Determining whether binary trees are balanced
I took part in the nuggets technical details of the campaign Autumn recruit job, writing essay with a gifts | the nuggets technology
