τα στοιχεία επικοινωνίας μου
Ταχυδρομείο[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Σύνδεσμος ΕΕ:225. Χρησιμοποιήστε ουρές για την υλοποίηση στοίβων - LeetCode
Εντάξει, ας ρίξουμε μια ματιά στον τίτλο Ο τίτλος λέει αυτό
Ιδέες : Χρησιμοποιήστε δύο ουρές και κρατήστε πάντα μια ουρά κενή. Όταν πρέπει να ωθήσουμε τα δεδομένα στη στοίβα, βάλτε τα δεδομένα σε μια ουρά που δεν είναι άδεια (αν και τα δύο είναι κενά, σπρώξτε τα σε οποιαδήποτε ουρά). Όταν απαιτείται μια λειτουργία pop, τα δεδομένα στη μη κενή ουρά εισάγονται στην κενή ουρά, αφήνοντας μόνο ένα δεδομένο αυτήν τη στιγμή, αυτά τα δεδομένα μπορούν να επιστραφούν και να διαγραφούν.Προσδιορίστε εάν η στοίβα είναι άδεια, δηλαδή εάν οι δύο ουρές είναι ταυτόχρονα κενές
Για παράδειγμα, θα το κάνουμε 1,2,3,4
Η ώθηση στη στοίβα σημαίνει στην πραγματικότητα είσοδο σε μία από τις ουρέςq1
Μέσης
Αν θέλουμε να βγούμε από τη στοίβα, πρέπει να ακολουθήσουμε 4,3,2,1
με τη σειρά, θα το κάνουμε1,2,3
push
στη δεύτερη ουράq2
μέσα, μετά μέσαq1
Μέσηςpop
4
Ολοκληρώστε τη λειτουργία ενός βήματος για να ανοίξετε τη στοίβα
Τότε μπορούμε push
q2
Μέσης1,2
φθάνωq1
, ώστε να μπορείτε να αφήσετε ένα3
υπάρχειq2
Επειταpop
q2
Αυτό είναι3
Η ποπ επιχείρηση
Αυτός ο βρόχος μπορεί να ολοκληρώσει όλες τις λειτουργίες απόσπασης της στοίβας.
Εδώ είναι η υλοποίηση του κώδικα:
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->size = 0;
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->size = 0;
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failn");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
bool QueueEmpty(Queue* pq)
{
return pq->tail == NULL && pq->head == NULL;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!(QueueEmpty(pq)));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!(QueueEmpty(pq)));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!(QueueEmpty(pq)));
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if (!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj) {
Queue* empty = &obj->q1;
Queue* noEmpty = &obj->q2;
if (!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noEmpty = &obj->q1;
}
while (QueueSize(noEmpty) > 1)
{
QueuePush(empty, QueueFront(noEmpty));
QueuePop(noEmpty);
}
int top = QueueFront(noEmpty);
QueuePop(noEmpty);
return top;
}
int myStackTop(MyStack* obj) {
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
Σύνδεσμος ΕΕ:232. Χρησιμοποιήστε τη στοίβα για την υλοποίηση της ουράς - LeetCode
Εντάξει, ας ρίξουμε μια ματιά στον τίτλο Ο τίτλος λέει αυτό
Ιδέες : Χρησιμοποιήστε δύο στοίβες, η πρώτη στοίβα χρησιμοποιείται μόνο για εισαγωγή δεδομένων και η δεύτερη στοίβα χρησιμοποιείται μόνο για έξοδο δεδομένων.Όταν πρέπει να εξάγονται δεδομένα αλλά η δεύτερη στοίβα είναι άδεια, πρώτα εισάγετε τα δεδομένα της πρώτης στοίβας στη δεύτερη στοίβα ένα προς ένα και, στη συνέχεια, εξάγετε τα δεδομένα από τη δεύτερη στοίβα.
Για παράδειγμα, θέλω να ακολουθήσω 1,2,3,4
στην ουρά με τη σειρά του1,2,3,4
Για να βάλουμε ουρά στη σειρά, μπορούμε πρώτα να το βάλουμε σε μια στοίβα και, στη συνέχεια, να εισάγουμε τα δεδομένα της πρώτης στοίβας στη δεύτερη στοίβα ένα προς ένα και απλώς να εισάγουμε
Εδώ είναι η υλοποίηση του κώδικα:
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0;
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
if (NULL == tmp)
{
perror("malloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newCapacity;
}
ps->_a[ps->_top] = data;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps);
ps->_top--;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
typedef struct {
Stack pushST;
Stack popST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->pushST);
StackInit(&obj->popST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->pushST, x);
}
void PushSTToPopST(MyQueue* obj)
{
if (StackEmpty(&obj->popST))
{
while (!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
}
int myQueuePop(MyQueue* obj) {
PushSTToPopST(obj);
int front = StackTop(&obj->popST);
StackPop(&obj->popST);
return front;
}
int myQueuePeek(MyQueue* obj) {
PushSTToPopST(obj);
int front = StackTop(&obj->popST);
return front;
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->popST) && StackEmpty(&obj->pushST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
}
Σύνδεσμος ΕΕ:20. Έγκυρες παρενθέσεις - LeetCode
Εντάξει, ας ρίξουμε μια ματιά στον τίτλο Ο τίτλος λέει αυτό
Ιδέες: Αυτή η ερώτηση είναι μια τυπική εφαρμογή της στοίβας, που ικανοποιεί τον κανόνα last-in-first-out (Η αρχική παρένθεση που πιέζεται τελευταία στη στοίβα θα ταιριάζει πρώτα με την τελική παρένθεση που εμφανίζεται πρώτη. ). Διασχίστε τη χορδή και σπρώξτε την απευθείας στη στοίβα όταν συναντήσετε την ανοιγόμενη παρένθεση. Όταν συναντήσετε ένα πίσω στήριγμα, προσδιορίστε εάν το πίσω στήριγμα ταιριάζει με το μπροστινό στήριγμα στο επάνω μέρος της στοίβας (εάν η στοίβα είναι άδεια αυτή τη στιγμή, η συμβολοσειρά δεν είναι έγκυρη), εάν δεν ταιριάζει, η συμβολοσειρά δεν είναι έγκυρη ταιριάζει, διαγράψτε το στοιχείο στο επάνω μέρος της στοίβας και συνεχίστε τη διέλευση χαρακτήρων μέχρι να ολοκληρωθεί η διέλευση συμβολοσειράς.Όταν η συμβολοσειρά διασχίζεται, ελέγξτε εάν η στοίβα είναι κενή, η συμβολοσειρά είναι έγκυρη εάν δεν είναι κενή, σημαίνει ότι η μπροστινή αγκύρωση δεν είναι έγκυρη.
typedef char STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0;
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
if (NULL == tmp)
{
perror("malloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newCapacity;
}
ps->_a[ps->_top] = data;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps);
ps->_top--;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
bool isValid(char * s){
Stack st;
StackInit(&st);
while(*s)
{
if(*s == '(' || *s == '[' || *s == '{')
{
StackPush(&st, *s);
}
else
{
if(StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
else
{
if((*s == ')' && StackTop(&st) != '(')
|| (*s == ']' && StackTop(&st) != '[')
|| (*s == '}' && StackTop(&st) != '{'))
{
StackDestroy(&st);
return false;
}
StackPop(&st);
}
}
++s;
}
if(!StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
return true;
}
Σύνδεσμος ΕΕ:622. Σχεδιασμός κυκλικής ουράς - LeetCode
Εντάξει, ας ρίξουμε μια ματιά στον τίτλο Ο τίτλος λέει αυτό
Ιδέες : Σε μια κυκλική ουρά, όταν η ουρά είναι άδεια, το κεφάλι και η ουρά της ουράς δείχνουν στην ίδια θέση. Όταν η ουρά δεν είναι κενή, η κεφαλή της ουράς δείχνει στα πρώτα δεδομένα που εισήχθησαν και η ουρά της ουράς δείχνει στη θέση δίπλα στα τελευταία δεδομένα. Όταν το tail+1 είναι ίσο με το μπροστινό μέρος, σημαίνει ότι η ουρά δακτυλίου είναι γεμάτη.
Ειδοποίηση : Η ουρά της κυκλικής ουράς δεν μπορεί να δείχνει προς τα τελευταία δεδομένα, όπως η ουρά της κανονικής ουράς, δεν θα μπορούμε να διακρίνουμε αν η κατάσταση της κυκλικής ουράς είναι κενή ή γεμάτη, επειδή αυτή τη στιγμή. τόσο το κεφάλι όσο και η ουρά της ουράς δείχνουν στην ίδια θέση. Αυτό σημαίνει ότι πρέπει να αφήσουμε ένα κενό που δεν μπορεί να αποθηκεύσει δεδομένα, ώστε να μπορούμε να διακρίνουμε καλά αν η κατάσταση της ουράς κουδουνίσματος είναι κενή ή πλήρης.
Ο κώδικας υλοποίησης είναι ο εξής:
typedef struct {
int* a;
int head;
int tail;
int size;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail + 1) % obj->size == obj->head;
}
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int) * (k+1));
obj->head = obj->tail = 0;
obj->size = k + 1;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
obj->tail++;
obj->tail %= obj->size;
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
obj->head++;
obj->head %= obj->size;
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->head];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[(obj->tail - 1 + obj->size) % obj->size];
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}