2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
ओ जे लिङ्कः : १.225. स्टैक्स् कार्यान्वितुं पङ्क्तयः उपयुज्यताम् - LeetCode
ठीकम्, शीर्षकं पश्यामः
विचाराः : द्वौ पङ्क्तौ उपयुज्य एकां पङ्क्तिं सर्वदा रिक्तं कुर्वन्तु। यदा अस्माभिः दत्तांशं स्टैक् मध्ये धक्कायितुं आवश्यकं भवति तदा दत्तांशं रिक्तं न भवति इति पङ्क्तौ स्थापयन्तु (यदि उभयम् अपि रिक्तं भवति तर्हि कस्यापि पङ्क्तौ धक्कायन्तु) । यदा पॉप् ऑपरेशनस्य आवश्यकता भवति तदा अरिक्तपङ्क्तौ दत्तांशः रिक्तपङ्क्तौ आयातितः भवति, अस्मिन् समये केवलम् एकः दत्तांशः अवशिष्टः भवति, एतत् दत्तांशं प्रत्यागत्य विलोपयितुं शक्यते ।स्तम्भः रिक्तः अस्ति वा इति निर्धारयन्तु अर्थात् पङ्क्तिद्वयं एकस्मिन् समये रिक्तं वा इति
यथा - करिष्यामः 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 - कार्यान्वयनार्थं stack इत्यस्य उपयोगं कुर्वन्तु
ठीकम्, शीर्षकं पश्यामः
विचाराः : द्वौ स्टैक् उपयुज्यताम्, प्रथमः स्टैक् केवलं data input कृते उपयुज्यते, द्वितीयः stack केवलं data output कृते उपयुज्यते ।यदा दत्तांशं निर्गन्तुं आवश्यकं भवति परन्तु द्वितीयः स्टैक् रिक्तः भवति तदा प्रथमं प्रथमे स्टैक् मध्ये दत्तांशं एकैकं द्वितीयं स्टैक् आयातयन्तु, ततः द्वितीयस्टैक् तः दत्तांशं आउटपुट् कुर्वन्तु
यथा, अहं अनुसरणं कर्तुम् इच्छामि 1,2,3,4
क्रमेण पङ्क्तौ अन्तः1,2,3,4
क्रमेण dequeue कर्तुं प्रथमं वयं तत् stack मध्ये स्थापयितुं शक्नुमः, ततः प्रथमे stack मध्ये विद्यमानं data एकैकं stack मध्ये import कर्तुं शक्नुमः, तथा च केवलं input कर्तुं शक्नुमः
अत्र कोड् कार्यान्वयनम् अस्ति :
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
ठीकम्, शीर्षकं पश्यामः
विचाराः: एषः प्रश्नः स्टैकस्य विशिष्टः अनुप्रयोगः अस्ति, यः अन्तिम-प्रथम-बहिः नियमं (यः उद्घाटनकोष्ठकः अन्तिमे स्तम्भे धक्कायते सः प्रथमं प्रथमं दृश्यमानस्य पश्चात् कोष्ठकस्य सङ्गतिं करिष्यति । ). तारं पारं कृत्वा उद्घाटनकोष्ठकस्य सम्मुखीभवति सति प्रत्यक्षतया स्तम्भे धक्कायन्तु । यदा पृष्ठकोष्ठकः सम्मुखीभवति तदा पृष्ठकोष्ठकः स्तम्भस्य उपरि स्थितस्य अग्रकोष्ठकस्य मेलनं करोति वा इति निर्धारयन्तु (यदि अस्मिन् समये स्तम्भः रिक्तः अस्ति तर्हि स्ट्रिंग् अमान्यः अस्ति यदि सः न मेलति) इदं मेलनं करोति, स्तम्भस्य उपरि स्थितं तत्त्वं विलोपयन्तु तथा च यावत् स्ट्रिंग्-भ्रमणं न सम्पन्नं भवति तावत् वर्णानाम् अनुसरणं निरन्तरं कुर्वन्तु ।यदा स्ट्रिंग् पारितं भवति तदा स्टैक् रिक्तः अस्ति वा इति पश्यन्तु यदि स्ट्रिंग् रिक्तं नास्ति तर्हि अग्रे कोष्ठकं न मेलितं भवति तथा च स्ट्रिंग् अमान्यम् इति अर्थः ।
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
ठीकम्, शीर्षकं पश्यामः
विचाराः : वृत्तपङ्क्तौ यदा पङ्क्तिः रिक्तः भवति तदा पङ्क्तिस्य शिरः पुच्छं च समानस्थानं दर्शयति । यदा पङ्क्तिः रिक्तः नास्ति तदा पङ्क्तिशिरः प्रथमं सम्मिलितं दत्तांशं दर्शयति, पङ्क्तिपुच्छं च अन्तिमदत्तांशस्य पार्श्वे स्थितं स्थानं दर्शयति यदा पुच्छं+१ अग्रे समं भवति तदा रङ्गपङ्क्तिः पूर्णा इति अर्थः ।
सूचना : वृत्तपङ्क्तिस्य पुच्छं नियमितपङ्क्तिवत् अन्तिमदत्तांशं दर्शयितुं न शक्नोति यदि एतत् भवति तर्हि वृत्तपङ्क्तिस्य स्थितिः रिक्तः पूर्णा वा इति भेदं कर्तुं न शक्नुमः, यतः अस्मिन् समये पङ्क्तिस्य शिरः पुच्छं च समानस्थानं दर्शयन्ति । अस्य अर्थः अस्ति यत् अस्माभिः एकं स्थानं त्यक्तव्यं यत् दत्तांशं संग्रहीतुं न शक्नोति, येन वयं सम्यक् भेदं कर्तुं शक्नुमः यत् रिंग-पङ्क्तौ स्थितिः रिक्तः अस्ति वा पूर्णा वा इति ।
कार्यान्वयनसङ्केतः निम्नलिखितरूपेण अस्ति ।
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);
}