环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】

本文涉及的产品
日志服务 SLS,月写入数据量 50GB 1个月
简介: 环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】



一、环形链表

给你一个链表的头节点 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。在循环中,根据当前字符的不同情况进行处理:

  1. 如果当前字符是左括号({[(),则将其推入栈中,并移动指针s指向下一个字符。
  2. 如果当前字符是右括号(}])),则进行以下操作:
  • 首先检查栈是否为空,如果为空,则说明没有匹配的左括号,直接返回false表示字符串无效。
  • 如果栈不为空,则取出栈顶元素(即最近推入的左括号),并与当前右括号进行匹配。
  • 如果匹配成功(即左括号和右括号匹配),则将栈顶元素弹出,并移动指针s指向下一个字符。
  • 如果匹配失败,则直接返回false表示字符串无效。
  1. 如果当前字符不是括号,则直接跳过该字符。

循环结束后,检查栈是否为空。如果栈为空,则说明所有左括号都与右括号成功匹配,返回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;
}

今天就先到这了!!!

看到这里了还不给博主扣个:

⛳️ 点赞☀️收藏 ⭐️ 关注!

你们的点赞就是博主更新最大的动力!

有问题可以评论或者私信呢秒回哦。

相关实践学习
日志服务之使用Nginx模式采集日志
本文介绍如何通过日志服务控制台创建Nginx模式的Logtail配置快速采集Nginx日志并进行多维度分析。
相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
36 1
|
2月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
51 0
Leetcode第21题(合并两个有序链表)
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
39 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
2月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
22 0
LeetCode第二十四题(两两交换链表中的节点)
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
44 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
2月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
90 0
|
2月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
22 0
|
2月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
17 0