2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
OJ linkki:225. Käytä jonoja pinojen toteuttamiseen - LeetCode
Okei, katsotaanpa otsikkoa
Ideoita : Käytä kahta jonoa ja pidä yksi jono aina tyhjänä. Kun meidän on työnnettävä tiedot pinoon, laita tiedot jonoon, joka ei ole tyhjä (jos molemmat ovat tyhjiä, työnnä se mihin tahansa jonoon). Kun pop-toimintoa tarvitaan, ei-tyhjän jonon tiedot tuodaan tyhjään jonoon, jolloin jäljelle jää vain yksi data. Tällä hetkellä nämä tiedot voidaan palauttaa ja poistaa.Selvitä, onko pino tyhjä, eli ovatko kaksi jonoa tyhjiä samanaikaisesti
Esimerkiksi teemme 1，2，3，4 Pinoon työntäminen tarkoittaa itse asiassa siirtymistä johonkin jonoistaq1 keskellä
Jos haluamme ponnahtaa pinosta, pitäisikö meidän seurata 4，3，2，1 järjestyksessä, teemme1，2，3 push toiseen jonoonq2 sisään, sitten sisäänq1 keskelläpop 4 Suorita yksivaiheinen pinon poksaaminen loppuun
Sitten voimme push q2 keskellä1，2 saapuaq1 , joten voit jättää yhden3 olla olemassaq2 Sittenpop q2 Se siitä3 Pop-operaatio
Tämä silmukka voi suorittaa kaikki pinon poksauksen toiminnot.
Tässä koodin toteutus:
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);
}
OJ linkki:232. Käytä pinoa toteuttamaan jono - LeetCode
Okei, katsotaanpa otsikkoa
Ideoita : Käytä kahta pinoa, ensimmäistä pinoa käytetään vain tietojen syöttämiseen ja toista pinoa vain tietojen tulostamiseen.Kun tiedot on tulostettava, mutta toinen pino on tyhjä, tuo ensin ensimmäisen pinon tiedot yksitellen toiseen pinoon ja tulosta sitten tiedot toisesta pinosta.
Haluan esimerkiksi seurata 1，2，3，4 jonoon järjestyksessä1，2，3，4 Järjestyksen purkamiseksi voimme ensin laittaa sen pinoon ja tuoda sitten ensimmäisen pinon tiedot toiseen pinoon yksitellen ja syöttää vain
Tässä koodin toteutus:
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);
}
OJ linkki:20. Kelvolliset sulut - LeetCode
Okei, katsotaanpa otsikkoa
Ideoita: Tämä kysymys on tyypillinen pinon sovellus, joka täyttää viimeinen sisään ensimmäinen ulos -säännön (Viimeiseksi pinoon työnnetty aloitussulku vastaa ensin ensimmäisenä näkyvää loppusulkua. ). Siirrä merkkijono poikki ja työnnä se suoraan pinoon, kun kohtaat avaavan sulkumerkin. Kun havaitset takasulun, määritä, vastaako se pinon yläosassa olevaa hakasuljetta (jos pino on tällä hetkellä tyhjä, merkkijono on virheellinen, jos se ei täsmää). se vastaa, poista pinon yläosassa oleva elementti ja jatka merkkijonon läpikulkua, kunnes merkkijonon läpikulku on valmis.Kun merkkijono on ajettu läpi, tarkista onko pino tyhjä. Jos se on tyhjä, merkkijono ei täsmää ja merkkijono on virheellinen.
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;
}
OJ linkki:622. Suunnittele pyöreä jono - LeetCode
Okei, katsotaanpa otsikkoa
Ideoita : Pyöreässä jonossa, kun jono on tyhjä, jonon pää ja loppu osoittavat samaan kohtaan. Kun jono ei ole tyhjä, jonon pää osoittaa ensimmäiseen lisättyyn tietoon ja jonon loppuosa viimeisen tiedon viereiseen kohtaan. Kun häntä+1 on yhtä suuri kuin etu, se tarkoittaa, että rengasjono on täynnä.
Ilmoitus : Pyöreän jonon loppuosa ei voi osoittaa viimeiseen dataan, kuten tavallisen jonon loppu, emme pysty erottamaan, onko pyöreän jonon tila tyhjä vai täynnä, koska tällä hetkellä. sekä jonon pää että häntä osoittavat samaan kohtaan. Tämä tarkoittaa, että meidän on jätettävä tila, johon ei voi tallentaa tietoja, jotta voimme hyvin erottaa, onko soittojonon tila tyhjä vai täynnä.
Käyttöönottokoodi on seuraava:
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);
}
Hän on omistautunut teknologian tutkimukselle yli kolmenkymmenen vuoden ajan ja hallitsee useita kieliä, kuten java, linux, javascript, php, css jne., ja hän on tehnyt monia panoksia avoimen lähdekoodin alalla Kehittäjän dokumentaatioasema, jossa voit jakaa joitakin teknologian kehityksen ongelmia tulevaa käyttöä varten
