目录
一、环形链表
方法(快慢指针):
二、环形链表 II
三、有效的括号
一、环形链表
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
方法(快慢指针):
我们定义两个指针,一快一慢。慢指针每次只移动一步,而快指针每次移动两步。初始时,慢指针和快指针都在位置 head出发。这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
return true;
}
}
return false;
}
时间复杂度:O(N)O(N)O(N),其中 NNN 是链表中的节点数。
当链表中不存在环时,快指针将先于慢指针到达链表尾部,链表中每个节点至多被访问两次。
当链表中存在环时,每一轮移动后,快慢指针的距离将减小一。而初始距离为环的长度,因此至多移动 NNN 轮。
空间复杂度:O(1)O(1)O(1)。我们只使用了两个指针的额外空间。
二、环形链表 II
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
快慢指针:
此题解题思路同上一题
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
//推到的一个结论:一个指针从相遇点开始走,一个指针从head走,他们会在入口点相遇
if(slow == fast)
{
struct ListNode* meet = slow;
while(head != meet)
{
head = head->next;
meet = meat->next;
}
return meet;
}
}
return NULL;
}
三、有效的括号
此题C语言不方便解释,只讲解思路
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
3、每个右括号都有一个对应的相同类型的左括号。
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps)
{
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//满了 -> 增容
if (ps->top == ps->capacity)
{
STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(int));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else {
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps ->top++;
}
//出栈
void StackPop(ST* ps)
{
assert(ps);
//ps->a[ps->top - 1] = 0;
//此处有两种情况:
//一、ps->a[ps->top - 1]本身就是0
//二、ps->a[ps->top - 1]的数据类型不是int,是其他数据类型
assert(ps->top > 0);
//栈空了,调用Pop,直接中止程序报错
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
//栈空了,调用Top,直接中止程序报错
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
函数内部使用了一个名为ST
的栈数据结构,并通过调用StackInit
函数进行初始化。栈用于存储左括号({
、[
、(
),以便后续与右括号进行匹配。
代码的主要逻辑是一个while
循环,遍历输入字符串s
中的每个字符,直到遇到字符串的结束符\0
。在循环中,根据当前字符的不同情况进行处理:
-
如果当前字符是左括号(
{
、[
、(
),则将其推入栈中,并移动指针s
指向下一个字符。 -
如果当前字符是右括号(
}
、]
、)
),则进行以下操作:-
首先检查栈是否为空,如果为空,则说明没有匹配的左括号,直接返回
false
表示字符串无效。 -
如果栈不为空,则取出栈顶元素(即最近推入的左括号),并与当前右括号进行匹配。
-
如果匹配成功(即左括号和右括号匹配),则将栈顶元素弹出,并移动指针
s
指向下一个字符。 -
如果匹配失败,则直接返回
false
表示字符串无效。
-
-
如果当前字符不是括号,则直接跳过该字符。
循环结束后,检查栈是否为空。如果栈为空,则说明所有左括号都与右括号成功匹配,返回true
表示字符串有效;否则返回false
表示字符串无效。
最后,在返回结果之前,调用StackDestroy
函数销毁栈,释放相关资源。
bool isValid(char* s) {
ST st;
StackInit(&st);
while (*s != '\0')
{
switch (*s)
{
case'{':
case'[':
case'(':
{
StackPush(&st, *s);
++s;
break;
}
case'}':
case']':
case')':
{
if (StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
char top = StackTop(&st);
StackPop(&st);
//不匹配
if ((*s == '}' && top != '{')
|| (*s == ']' && top != '[')
|| (*s == ')' && top != '('))
{
return false;
}
else //匹配
{
++s;
}
break;
}
default:
break;
}
}
bool ret = StackEmpty(&st);
StackDestroy(&st);
return ret;
}
今天就先到这了!!!
看到这里了还不给博主扣个:
⛳️ 点赞☀️收藏 ⭐️ 关注!文章来源:https://www.toymoban.com/news/detail-772318.html
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。文章来源地址https://www.toymoban.com/news/detail-772318.html
到了这里,关于环形链表、环形链表 II、有效的括号【LeetCode刷题日志】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!