本文主要是介绍每周刷题第三期,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
个人主页:星纭-CSDN博客
系列文章专栏:Python
踏上取经路,比抵达灵山更重要!一起努力一起进步!
目录
题目一:环形链表
题目二:删除有序数组中的重复项
题目三:有效的括号
题目四:用队列实现栈
题目五:用栈实现队列
题目一:环形链表
题目出处:. - 力扣(LeetCode)/
题目描述:这道题和上一期的环形链表很像只不过,一个是判断是否存在环,一个是求入环节点。
题解思路:采用双指针。定义两个指针fast,slow,fast一次走两步,slow一次走一步。
然后我们来分析一下这道题的数学关系。
相遇点指的是fast指针和slow指针第一次相遇的地方。
当fast和slow相遇的时候,fast行走的距离是slow的两倍,
slow:L + X
fast:2(L + X) = L + X + a * N。a指的是fast进入环后行走的圈数
L = (a - 1) * N + N - X;
N-X就是相遇点到环的距离。也就是说,如果fast从相遇出发,slow从起点出发,均每次走一步。两者第一次相遇的地方就是进入环的节点。
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fast = head,*slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(fast == slow){fast = head;while(fast != slow){fast = fast->next;slow = slow->next; }return fast;}}return NULL;
}
题目二:删除有序数组中的重复项
题目出处:. - 力扣(LeetCode)
题目描述:给你一个 非严格递增排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums
中唯一元素的个数。
这道题的要求是,原地删除,所以空间复杂度是O(1),因为这个数组是非严格递增的,重复的元素是挨在一起的,即相等的元素在数组中一定是连续的。
解题思路:使用双指针,定义两个指针src,dst.src表示下一个不同元素的下标,dst表示要填入的位置的下标。
dst开始指向0,src开始指向1.如果src和dst相同,src就加1。不相同,dst加1,然后移动元素,然后src也加1.
int removeDuplicates(int* nums, int numsSize) {int src,dst;src = 1;dst = 0;while(src < numsSize){if(nums[src] != nums[dst]){++dst;nums[dst] = nums[src];++src;}else{src++;}}int k = dst + 1;return k;
}
题目三:有效的括号
题目出处:. - 力扣(LeetCode)
题目描述 :
这个题目的示例不够全面,
对于字符串s = "{[]}",这样的字符串也成立,s = "()[{}]"也是成立的,题目所给的示例会让人误以为匹配的括号必须连续,其实不是这样的,这是题目的一个问题。
题目思路:首先需要用C语言手动实现一个栈。
然后我们开始遍历整个字符串:当遇到左括号的时候,就入栈,遇到右括号的时候,就取出栈顶元素,进行匹配,如果不匹配说明这个字符串不有效,反之继续匹配 ,直到结束,该字符串就匹配。关于栈的代码参考前面的文章。
bool isValid(char* s) {Stack st;STInit(&st);while (*s) {if (*s == '(' || *s == '[' || *s == '{') {STPush(&st, *s);} else {if (IsEmpty(&st)) {STDestory(&st);return false;} else {char ch = STTop(&st);STPop(&st);if ((ch == '(' && *s != ')') || (ch == '[' && *s != ']') ||(ch == '{' && *s != '}')) {STDestory(&st);return false;}}}++s;}bool ret = IsEmpty(&st);STDestory(&st);return ret;
}
在每次使用return语句之前都要销毁这个栈,避免内存泄漏。
最后为什么是返回ret?
如果遇到这样的字符,不难发现根本没有进入循环,直接返回了true,这明显是不正确的,所以需要进行判断,栈是否为空,如果为空,所以左括号并没匹配完成,这个字符串无效。
题目四:用队列实现栈
题目出处:. - 力扣(LeetCode)
题目描述:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和 empty
)。
实现 MyStack
类:
void push(int x)
将元素 x 压入栈顶。int pop()
移除并返回栈顶元素。int top()
返回栈顶元素。boolean empty()
如果栈是空的,返回true
;否则,返回false
。
解题思路:
如果接下来我们要进行出栈,根据先进后出的规则,那么得到的第一个数据应该是5,可是仅仅在队列一中进行出队列入队列是达不到这样的效果的。
那么如何进行操作呢?
首先我们可以将1-4入队列到队列二中,这样队列一中就只剩下一个数据5了,此时出队列就是5.起到了先进后出的效果。如果还需要放入数据,很明显是放在队列二中,因为此时的队列一已经没有了数据了。
首先需要使用C语言实现一个队列。代码参考前面的文章。
初始化:
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(pst->q1));QueueInit(&(pst->q2));return pst;
}
push:
void myStackPush(MyStack* obj, int x) {if (!QueueEmpty(&(obj->q1))) {QueuePush(&(obj->q1), x);} else {QueuePush(&(obj->q2), x);}
}
新放入的数据,需要放在已经存放有数据的队列。如果两个队列都为空,那么此时随便放在那个队列中都可以。
删除数据:
int myStackPop(MyStack* obj) {Queue* noempty = &(obj->q1);Queue* empty = &(obj->q2);if (!QueueEmpty(&(obj->q2))) {noempty = &(obj->q2);empty = &(obj->q1);}while (QueueSize(noempty) > 1) {QueuePush(empty, QueueFront(noempty));QueuePop(noempty);}int top = QueueFront(noempty);QueuePop(noempty);return top;
}
由于不确定,哪一个队列是空的,所以采用假设法进行判断,出数据的时候,需要将非空队列的数据的前n-1个全部转移到空队列中,留剩下一个出栈即可。
查看栈顶元素:
int myStackTop(MyStack* obj) {if (!QueueEmpty(&(obj->q2))) {return QueueBack(&(obj->q2));} else {return QueueBack(&(obj->q1));}
}
实现的队列中是,含有查看队尾元素的,非空的队列的队尾元素就是栈顶元素。
判空与销毁:
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}void myStackFree(MyStack* obj) {QueueDestory(&(obj->q1));QueueDestory(&(obj->q2));free(obj);
}
这里的判空,是判断两个队列都是否为空。
题目五:用栈实现队列
题目出处;. - 力扣(LeetCode)
题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
实现 MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
解题思路:
这道题与上一道题类似
只不过,需要判断空了,入栈的时候只需要把 数据固定存放在一个栈中,push栈,出栈的时候,先出pop栈中的数据,如果栈为空,把push栈的数据导过来。
初始化:
typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;
}
入数据:
void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);
}
查看数据:
int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}return STTop(&obj->popst);
}
首先需要判断popst中是否为空,如果不为空就直接返回即可,为空,就需要向pust中得到数据。
出数据:
int myQueuePop(MyQueue* obj) {int front = myQueuePeek(obj);STPop(&obj->popst);return front;
}
出数据,直接使用peek函数先查看一下栈顶有没有元素,有才出,否则peek元素会先导数据。
判空与销毁:
bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {STDestory(&obj->popst);STDestory(&obj->pushst);free(obj);
}
这篇关于每周刷题第三期的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!