preface
The previous article covered the concepts of stack and queue, and also demonstrated in code how to define stack and queue structures using sequential and chained storage, respectively.
For queues, I believe you should be familiar, queues are generally used with multi-threading, in iOS development is also often used, there is no more to say.
This article focuses on how to use the idea of stack to solve some problems.
Stack thinking exercises
Parentheses matching
Haha, mention this topic all feel a little embarrassed 😅, because this topic before the interview of the author encountered (did not make, cool 😅). I’m sure I can do it now. That’s learning.
Enter a string containing parentheses (){}[] and check whether the parentheses match. For example :(()[]{}){[()]} this type is matched. For example :([){]} this type is not matched, need to print the brackets do not match.
ç” æ¡ˆ : This topic is obviously to use the idea of stack to solve (I was interviewed at the time also thought of, but how can not define the stack, awkwardness). Solution idea:
- When the open parenthesis is entered
{[(, the symbols are pushed (also called pushed). - When the close parenthesis is entered
}]), and the top element of the stack:- If it is
{} [] ()If it matches, it pushes the top element off the stack and continues; - If they do not match, for example
{], [}, [), {), (], (}, empty stack),],}This tells you that the input parentheses don’t match, so just print the parentheses don’t match.
- If it is
- If nothing goes wrong until the input is complete, you need to check again to see if there are any more elements in the stack (that is, if the stack is empty).
- If the stack is empty, it’s just fine. The parentheses match.
- If it’s not empty, sorry, there’s too many parentheses, it doesn’t match.
The code is as follows:
#import <Foundation/Foundation.h>
#define MaxCount 100
#define l1 '{'
#define r1 '} '
#define l2 '['
#define r2 '] '
#define l3 '('
#define r3 ') '
typedef struct _Stack{
char s[MaxCount];
int top;
} Stack;
// Create a stack
Stack createStack(a) {
Stack st;
st.top = - 1; // -1 means there is nothing in the stack
for (int i = 0; i < MaxCount; i++) {
st.s[i] = ' ';
}
return st;
}
/ / into the stack
void inStack(Stack *st, char c) {
if (st->top < - 1 || st->top >= MaxCount - 1) {
printf("Stack full, cannot be loaded \n");
return ;
}
st->top++;
st->s[st->top] = c;
}
/ / out of the stack
int outStack(Stack *st) {
if (st->top < - 1) {
printf("There are no more elements in stack, can't exit stack \n");
return 0;
}
return st->s[st->top--];
}
// Iterate over the print
void foreachStack(Stack st) {
for (int i = 0; i < st.top + 1; i++) {
printf("%c", st.s[i]);
}
printf("\n");
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
Stack st = createStack();
char c;
scanf("%c", &c);
while(c ! ='\n') {
// Other characters do not count
if (c == l1 || c == l2 || c == l3 || c == r1 || c == r2 || c == r3) {
printf("%c", c);
// If it is left parenthesis
if (c == l1 || c == l2 || c == l3) {
inStack(&st, c);
}
else {
// If it is a close parenthesis, check whether the top element matches the input parenthesis
if((c == r1 && st.s[st.top] == l1) || (c == r2 && st.s[st.top] == l2) || (c == r3 && st.s[st.top] == l3)) { outStack(&st); }else {
printf("Parentheses do not match ---->%c\n", c);
return 0; }}}// Enter the next character
scanf("%c", &c);
}
if (st.top == - 1) {
printf("Parentheses match \n");
}
else {
printf("Parentheses do not match, remaining parentheses:"); foreachStack(st); }}return 0;
}
Copy the codeHexadecimal conversion
This is actually a math problem, but think about how do you do a base conversion mathematically? Yeah, just use short division.
The following is directly sticky code, not the principle can see the link above.
#import <Foundation/Foundation.h>
// Define extensible stack (purely on a whim)
typedef struct _Stack {
int *data; / / data
int top; // Index at the top of the stack
int size; / / size
} Stack;
Stack initStack(void) {
Stack s;
s.data = malloc(sizeof(int) * 20);
s.top = - 1;
s.size = 20;
return s;
}
void extensionStack(Stack *s) {
s->data = realloc(s->data, sizeof(int) * (s->size + 20));
if (s->data) {
s->size += 20;
}
else {
NSLog(@"Expanding space failed"); }}void curtailStack(Stack *s) {
s->data = realloc(s->data, sizeof(int) * (s->size) - 20);
if (s->data) {
s->size -= 20;
}
else {
NSLog(@"Space reduction failed"); }}void checkStackSize(Stack *s) {
if (s->top > s->size - 5) {
extensionStack(s);
}
if (s->top < s->size - 25) { curtailStack(s); }}void inStack(Stack *s, int inData) {
checkStackSize(s);
s->data[s->top + 1] = inData;
s->top++;
}
void outStack(Stack *s, int *outData) {
checkStackSize(s);
*outData = s->data[s->top];
s->top--;
}
/ / logical area
// Convert decimal to other bases below decimal
void decConversionOther(int data, int targetSystem) {
Stack s = initStack();
while (data > 0) {
inStack(&s, data % targetSystem);
data = data / targetSystem;
}
int i = s.top;
printf("%d:", targetSystem);
while (i >= 0) {
printf("%d", s.data[i]);
i--;
}
printf("\n");
}
// Convert from decimal to hexadecimal
void decConversionHex(int data) {
Stack s = initStack();
while (data > 0) {
inStack(&s, data % 16);
data = data / 16;
}
int i = s.top;
printf("Base 16:");
while (i >= 0) {
if (s.data[i] < 10) {
printf("%d", s.data[i]);
}
else {
switch (s.data[i]) {
case 10:
printf("A");
break;
case 11:
printf("B");
break;
case 12:
printf("C");
break;
case 13:
printf("D");
break;
case 14:
printf("E");
break;
case 15:
printf("F");
break;
default:
break;
}
}
i--;
}
printf("\n");
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
decConversionOther(7.2);
decConversionOther(24.2);
decConversionHex(0xF2CD24);
}
return 0;
}
Copy the codeString encoding
The encoding rule is k[encoDED_string], indicating that the encoded_string inside the square brackets is repeated k times. Note that k is guaranteed to be a positive integer. You can assume that the input string is always valid; There are no extra Spaces in the input string, and the input square brackets are always formatted. In addition, you can assume that the raw data does not contain numbers, and that all numbers represent only the number of repetitions k, such as no input like 3a or 2[4].
For example, s = “3[a]2[BC]”, return “aaabcBC”. S = “3[a2[c]]”, return “accaccacc”. S = “2[ABC]3[CD]ef”, return “abcabccdCDcdef”.
In this case, it is similar to matching parentheses, except that it is more troublesome to find the characters in the middle of [] and the digits before [].
Answer:
- Traversal format string, no
]Push all of s into the stack. - encounter
], loop out the elements in the stack s and determine whether the stack is empty and whether the elements out of the stack are numbers. - Encountered during the process of unloading the stack
[Before, all the strings were going to be copied n times; encounter[And then all the numbers that are out of the stack, that’s the number of times that you’re going to copy them. - After finding these two, copy n copies of the string, push it onto stack S, and continue through step 2.
The code is as follows:
#import <Foundation/Foundation.h>
#import <stdlib.h>
// Define an extensible stack
typedef struct _Stack {
char *data; / / data
int top; // Index at the top of the stack
int size; / / size
} Stack;
Stack initStack(void) {
Stack s;
s.data = malloc(sizeof(char) * 20);
s.top = - 1;
s.size = 20;
return s;
}
void extensionStack(Stack *s) {
s->data = realloc(s->data, sizeof(char) * (s->size + 20));
if (s->data) {
s->size += 20;
}
else {
NSLog(@"Expanding space failed"); }}void curtailStack(Stack *s) {
s->data = realloc(s->data, sizeof(char) * (s->size) - 20);
if (s->data) {
s->size -= 20;
}
else {
NSLog(@"Space reduction failed"); }}void checkStackSize(Stack *s) {
if (s->top > s->size - 5) {
extensionStack(s);
}
if (s->top < s->size - 25) { curtailStack(s); }}void inStack(Stack *s, char inData) {
checkStackSize(s);
s->data[s->top + 1] = inData;
s->top++;
}
void outStack(Stack *s, char *outData) {
checkStackSize(s);
if (outData) {
*outData = s->data[s->top];
}
s->top--;
}
char* encodeStr(char *forStr) {
int fl = (int)strlen(forStr); // Format the length of the string
Stack s = initStack();
Stack c = initStack();
Stack n = initStack();
for (int i = 0; i < fl; i++) {
if(forStr[i] ! ='] ') {
inStack(&s, forStr[i]);
}
else {
BOOL isNum = NO;
char topC;
// The loop can be executed until isNum becomes YES; After YES, the top element of the stack must be a number
while (s.top >= 0&& (! isNum || (s.data[s.top] >='0' && s.data[s.top] <= '9'))) {
outStack(&s, &topC);
if (topC == '[') {
isNum = YES;
continue;
}
// push the character into the corresponding character stack
inStack(isNum ? &n : &c, topC);
}
// Convert characters in stack n to numbers
char *numStr = malloc(sizeof(char) * strlen(n.data));
char top;
for (int j = 0; j < strlen(n.data); j++) {
outStack(&n, &top);
numStr[j] = top;
}
// Get a number based on the string
int num = atoi(strlen(numStr) > 0 ? numStr : "1");
// Convert elements in stack C to character arrays
char *cArr = malloc(sizeof(char) * strlen(c.data));
for (int j = 0; j < strlen(c.data); j++) {
outStack(&c, &top);
cArr[j] = top;
}
for (int k = 0; k < num; k++) {
for (int x = 0; x < strlen(cArr); x++) { inStack(&s, cArr[x]); }}// At the end of this round, the stack is empty to be on the safe side, even though both n and c are out of the stack
n.top = - 1;
c.top = - 1;
free(cArr);
s.data[s.top + 1] = '\ 0'; // As a closing character}}free(n.data);
free(c.data);
return s.data;
}
/ / logical area
int main(int argc, const char * argv[]) {
@autoreleasepool {
char *formatStr = "2[abc][cd]ef"; // Format string
char *resultStr = encodeStr(formatStr);
printf("%s\n", resultStr);
}
return 0;
}
Copy the codeDelete duplicate letters
Given a string containing only lowercase letters, remove duplicate letters from the string so that each letter appears only once. Ensure that the lexicographic order of the returned result is minimal (the relative position of other characters must not be disturbed).
In the last sentence, the order of the dictionary should be as small as possible, and the relative position of other characters should not be disturbed.
Since we only consider lower-case letters, we can define two 26-size int arrays, one to hold the number of occurrences of each letter, and the other to hold whether the letter corresponding to the subscript has been pushed.
The code is as follows:
#import <Foundation/Foundation.h>
// Delete duplicate letters
char* removeDuplicateLetters(char *s)
{
if(! s ||strlen(s) < 2) {
return s;
}
int top = - 1; // as the top index of the stack
char *resStack = malloc(sizeof(char) * 26); // Save the result stack
int isInStack[26] = {0}; // Whether the corresponding letter has been pushed
int countStack[26] = {0}; // The number of remaining occurrences of the corresponding letter
// Find the number of occurrences of each letter
char *p = s;
while (*p) {
countStack[*p - 'a'] + +; p++;// Find the next character
}
p = s;
int i = 0;
while (*p) {
i = *p - 'a';
// Check whether the current letter is already in the stack.
if(! isInStack[i]) {// Loop the top letter of the stack to determine whether the stack needs to be removed
while(top ! =- 1 && // Not empty stack
*p < resStack[top] && // The current letter is smaller than the top element of the stack
countStack[resStack[top] - 'a'] > 0) // There is also a letter at the top of the stack, you can delete this first, anyway, it will be added later
{
isInStack[resStack[top] - 'a'] = 0; // Set the corresponding letter to unpushed
top--; / / out of the stack
}
// Push the current letter to the stack
resStack[++top] = *p;
// Sets the current letter to pushed
isInStack[i] = 1;
}
countStack[i]--;
p++;
}
return resStack;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
char *s = removeDuplicateLetters("xyzbcabcxyz");
printf("%s\n", s);
}
return 0;
}
Copy the codeOther exercises
The daily temperature
Based on the daily temperature list, a list is generated indicating how many more days you need to wait for the temperature to exceed that day. If it does not rise, 0 is used.
Answer:
- Violent method, direct double cycle, one by one, using subtraction subscripts, can calculate the next temperature exceeded the number of days needed.
- The jump method, which loops forward from the last day.
- If [I + 1] > [I], then day I is 1.
- If [I] == [I], then [I] = 0; if [I] == [I], then [I] = 0; [I] = [I + 1] + 1;
- If [I + 1] < [I], it’s back to the brute force method.
In general, the jump method can be used to calculate the results of the cycle according to the results already calculated, reducing the number of comparisons, a bit of dynamic programming feeling JIo.
The code is as follows:
#import <Foundation/Foundation.h>
int randTem(void) {
return 60 + arc4random() % 20;
}
/ / method of violence
void bfFunc(int *tem, int tSize) {
// Prints the next temperature to exceed
for (int i = 0; i < tSize; i++) {
int next = 0;
for (int j = i + 1; j < tSize; j++) {
if (tem[j] > tem[i]) {
next = j - i;
break; }}printf("%-5d", next);
}
printf("\n");
}
// Jump comparison method
void skipFunc(int *tem, int tSize) {
int a[tSize];
a[tSize - 1] = 0;
// Reverse traversal to reduce the number of loops
for (int i = tSize - 2; i >= 0; i--) {
if (tem[i] < tem[i + 1]) {
a[i] = 1;
}
else if (tem[i] == tem[i + 1]) {
if (a[i + 1] = =0) {
a[i] = 0;
}
else {
a[i] = a[i + 1] + 1; }}else {
a[i] = 0;
for (int j = i + 2; j < tSize; j++) {
if (tem[j] > tem[i]) {
a[i] = j - i;
break; }}}}for (int i = 0; i < tSize; i++) {
printf("%-5d", a[i]);
}
printf("\n");
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int *tem = malloc(sizeof(int) * 50);
int tSize = 50;
for (int i = 0; i < tSize; i++) {
tem[i] = randTem();
printf("%-5d", tem[i]);
}
printf("\n\n");
printf("Violence: \n");
bfFunc(tem, tSize);
printf("Jump method: \n");
skipFunc(tem, tSize);
}
return 0;
}
Copy the codeYang hui triangle
The original Yang Hui triangle is the first, in the computer is generally stored as the second structure.
1 1
1 1 1 1
1 2 1 -----> 1 2 1
1 3 3 1 1 3 3 1
1 4 6 4 1 1 4 6 3 1
Copy the codeIn fact, this topic needs to pay attention to three points:
- Use a two-dimensional array for storage.
- Arr [I][0] = arr[I][I] = 0.
- Arr [I][J] = ARR [i-1][J-1] + ARR [i-1][J].
The code is as follows:
#import <Foundation/Foundation.h>
int main(int argc, const char * argv[]) {
@autoreleasepool {
int a[10] [10];
for (int i = 0; i < 10; i++) {
a[i][0] = 1;
a[i][i] = 1;
for (int j = 1; j < i; j++) {
a[i][j] = a[i - 1][j - 1] + a[i - 1][j]; }}for (int i = 0; i < 10; i++) {
for (int j = 0; j <= i; j++) {
printf("%-5d", a[i][j]);
}
printf("\n"); }}return 0;
}
Copy the codeClimb the stairs
If there are n stairs, only one or two can go at a time, how many kinds of way to ask?
The first time to meet this problem, may be very confused, do not know where to start, fortunately, the author is not the first time to encounter this problem (has n times 😂)
There are two ways to solve the problem: forward and reverse.
I’m already on the NTH floor. How did I get to the NTH floor? There are only two ways to do this:
- One floor at a time from n-1.
- Two floors at a time from n-2.
So by this point, does that mean that n steps is equal to n minus 1 steps plus n minus 2 steps? Think about 🤔, it seems so.
That formula from above, don’t tell me you can’t see it’s a recursion? f(n) = f(n – 1) + f(n – 2)
And then there’s the code, the recursive solution
/ / the recursive method
int climbStairs(int stairs) {
if (stairs == 1) {
return 1; // If there is only one layer, there is only one way to go
}
else if (stairs == 2) {
return 2; // If there are two layers, there are two ways to go
}
else {
return climbStairs(stairs - 1) + climbStairs(stairs - 2); }}Copy the codePositive thinking, you said reverse thinking is a little difficult, not necessarily can think of, that’s ok, let’s talk about how to use positive thinking to solve.
| Number of stairs n | How many ways are there |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 (not 4) |
| 5 | 8 |
| 6 | 13 |
| 7 | 21 |
The so-called forward thinking is to find the rule, enumerate several sets of data, find the rule between them, and then find another set of arrays to verify, if there is no problem, almost found the rule.
From the above, we enumerated 7 groups of data, found a rule, the number of the first two groups of moves add up to the current group of moves, is it also indirectly confirmed the reverse analysis just got the rule that n stairs = N – 1 stairs + N – 2 stairs?
So that’s the rule. That’s right. By the way, and so on? Why does this rule look so familiar? Is it like Fibonacci numbers?
Yes, in fact, the nature of the stair climbing problem is the Fibonacci sequence. So let’s do it in a non-recursive way.
/ / the recursion
int climbStairs2(int stairs) {
if (stairs == 1) {
return 1;
}
else if (stairs == 2) {
return 2;
}
else {
int f1 = 1; / / first order
int f2 = 2; / / two order
for (int i = 3; i <= stairs; i++) {
f2 = f1 + f2;
f1 = f2 - f1;
}
returnf2; }}Copy the codeFor the record, the Fibonacci sequence evolved from the problem of rabbits giving birth to babies, but the problem of climbing stairs happens to follow the same rule.
I mean, there are so many algorithms, it’s not realistic to memorize all the algorithms, but what we need to do is remember what is the nature of the algorithm?
- Climbing stairs –> Essentially Fibonacci numbers
- The Fibonacci sequence is that the sum of the first two terms equals the last one
- Solution –> Loop and recursion.
So through the essence of step by step derivation, no problem can not be solved, but memorized code, remember the moment, remember not the world, to use the time will not derive, destined to cool… (Digress)
conclusion
This article will mainly bring the idea of stack into the algorithm, a deeper understanding of the characteristics and usage of stack.
In addition, it records some classic algorithm problems, the nature of the problem, the idea of solving the problem, and the code of solving the problem.
(Direct point is useless, select can copy yo)