代码随想录算法训练营第十一天|Day11栈与队列

150. 逆波兰表达式求值

题目链接/文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html

思路

#define MAX_TOKENS 1000  
#define MAX_TOKEN_LEN 10    
typedef struct {  
    long long data[MAX_TOKENS];  
    int top;  
} Stack;   
void initStack(Stack *st) {  
    st->top = -1;  
}   
bool isStackEmpty(Stack *st) {  
    return st->top == -1;  
}   
bool isStackFull(Stack *st) {  
    return st->top == MAX_TOKENS - 1;  
}   
void push(Stack *st, long long value) {  
    if (!isStackFull(st)) {  
        st->data[++st->top] = value;  
    } else {  
        printf("Stack overflow\n");  
        exit(EXIT_FAILURE);  
    }  
}    
long long pop(Stack *st) {  
    if (!isStackEmpty(st)) {  
        return st->data[st->top--];  
    } else {  
        printf("Stack underflow\n");  
        exit(EXIT_FAILURE);  
    }  
}    
long long evalRPN(char *tokens[], int tokensSize) {  
    Stack st;  
    initStack(&st);   
    for (int i = 0; i < tokensSize; i++) {  
        if (strcmp(tokens[i], "+") == 0 || strcmp(tokens[i], "-") == 0 ||  
            strcmp(tokens[i], "*") == 0 || strcmp(tokens[i], "/") == 0) {  
            long long num1 = pop(&st);  
            long long num2 = pop(&st);  
            long long result;  
            if (strcmp(tokens[i], "+") == 0) result = num2 + num1;  
            else if (strcmp(tokens[i], "-") == 0) result = num2 - num1;  
            else if (strcmp(tokens[i], "*") == 0) result = num2 * num1;  
            else if (strcmp(tokens[i], "/") == 0) {   
                if (num1 == 0) {  
                    printf("Division by zero\n");  
                    exit(EXIT_FAILURE);  
                }  
                result = num2 / num1;  
            }  
            push(&st, result);  
        } else {  
            char *endptr;  
            long long num = strtoll(tokens[i], &endptr, 10);  
            if (*endptr != '\0') {  
                printf("Invalid number: %s\n", tokens[i]);  
                exit(EXIT_FAILURE);  
            }  
            push(&st, num);  
        }  
    }   
    long long result = pop(&st);  
    return result;  
}  

学习反思

栈与递归之间在某种程度上是可以转换的。

239. 滑动窗口最大值

题目链接/文章讲解/视频讲解：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html

思路

#define MAX_SIZE 100000 
typedef struct {  
    int *data; 
    int front; 
    int rear;    
    int size;    
    int capacity; 
} MyQueue;  
void initQueue(MyQueue *queue, int capacity) {  
    queue->data = (int *)malloc(capacity * sizeof(int));  
    queue->front = 0;  
    queue->rear = -1;  
    queue->size = 0;  
    queue->capacity = capacity;  
}   
void destroyQueue(MyQueue *queue) {  
    free(queue->data);  
    queue->data = NULL;  
    queue->front = queue->rear = queue->size = queue->capacity = 0;  
}  
int isEmpty(MyQueue *queue) {  
    return queue->size == 0;  
}    
void pop(MyQueue *queue, int value) {  
    if (!isEmpty(queue) && queue->data[queue->front] == value) {  
        queue->front++;  
        queue->size--;  
    }  
}   
void push(MyQueue *queue, int value) {  
    while (!isEmpty(queue) && value > queue->data[queue->rear]) {  
        queue->rear--;  
        queue->size--;  
    }  
    queue->rear++;  
    if (queue->rear >= queue->capacity) {  
        queue->rear = 0; 
    }  
    queue->data[queue->rear] = value;  
    queue->size++;  
} 
int front(MyQueue *queue) {  
    return queue->data[queue->front];  
}   
void adjustQueue(MyQueue *queue) {  
    if (queue->rear >= queue->capacity - 1) {  
        int newFront = queue->rear + 1;  
        if (newFront >= queue->capacity) {  
            newFront = 0;  
        }  
        for (int i = queue->rear; i >= queue->front; i--) {  
            int idx = (i + 1) % queue->capacity;  
            if (idx == newFront) {  
                break;  
            }  
            queue->data[idx] = queue->data[i];  
        }  
        queue->front = newFront;  
        queue->rear = newFront - 1;  
        queue->size = 0;  
    }  
}  
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {  
    MyQueue queue;  
    initQueue(&queue, numsSize);   
    int *result = (int *)malloc((numsSize - k + 1) * sizeof(int));  
    *returnSize = 0;  
    for (int i = 0; i < k; i++) {  
        push(&queue, nums[i]);  
    }  
    result[(*returnSize)++] = front(&queue);  
    for (int i = k; i < numsSize; i++) {  
        pop(&queue, nums[i - k]);  
        push(&queue, nums[i]);  
        result[(*returnSize)++] = front(&queue);  
    }    
    destroyQueue(&queue); 
    return result;  
}  

学习反思

想用一个大顶堆（优先级队列）来存放这个窗口里的k个数字，这样就可以知道最大的最大值是多少了，问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

347.前 K 个高频元素

题目链接/文章讲解/视频讲解：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

思路

typedef struct {
    int num;   
    int count;  
} Element;

int compare(const void *a, const void *b) {
    return ((Element *)a)->count - ((Element *)b)->count;
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
    int freq[10001] = {0}; 
    for (int i = 0; i < numsSize; i++) {
        freq[nums[i]]++;
    }
    Element *heap = (Element *)malloc(k * sizeof(Element));
    int heapSize = 0;
    for (int i = 0; i < 10001; i++) {
        if (freq[i] == 0) {
            continue; 
        }
        if (heapSize < k) {
            heap[heapSize].num = i;
            heap[heapSize].count = freq[i];
            heapSize++;
            qsort(heap, heapSize, sizeof(Element), compare);
        } else if (freq[i] > heap[0].count) { 
            heap[0].num = i;
            heap[0].count = freq[i];
            qsort(heap, heapSize, sizeof(Element), compare);
        }
    }
    int *result = (int *)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        result[i] = heap[i].num;
    }
    free(heap);
    *returnSize = k;
    return result;
}

学习反思

有点难度。

总结

加油！！！