leetcode刷题（2）

小灰灰 2023-09-25 22:40 132阅读 0赞

各位朋友们，又是新的一天，不知道大家过得怎样？今天是我leedcode刷题系列的第二篇，那么废话不多说，直接进入我们今天的主题。

#### 文章目录 ####

*  有效的括号
 *   *  题目要求
     *  用例输入
     *  做题思路
     *  代码实现
 *  环形链表
 *   *  题目要求
     *  用例输入
     *  做题思路
     *  代码实现
 *  环形链表 II
 *   *  题目要求
     *  用例输入
     *  做题思路
     *  代码实现

## 有效的括号 ##

[leetcode之有效的括号][leetcode]

### 题目要求 ###

给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
每个右括号都有一个对应的相同类型的左括号。

### 用例输入 ###

示例 1：  
输入：s = “()”  
输出：true

示例 2：  
输入：s = “()\[\]\{\}”  
输出：true

示例 3：  
输入：s = “(\]”  
输出：false

### 做题思路 ###

这道题的要求是需要我们判断给的括号是否合法，意思就是当我们遇到有括号的时候，我们需要判断左边最近的左括号是否跟这个右括号匹配。我们可以使用一种数据结构：栈来解决这个问题，因为栈是一端进，一端出，这一端被称为栈顶，先进后出，后进先出。所以我们把左括号都放在栈中，当遇到右括号时，我们就从栈顶取出左括号，看是否跟这个右括号匹配，匹配就继续下一个字符，不匹配就返回true。当这个字符串遍历完后，如果栈中不为空，说明有左括号未匹配，返回false，否则返回true。

### 代码实现 ###

bool isValid(char * s){
        
        int len = strlen(s);
        //当字符串中没有或者只有一个字符时就直接返回false
        if(len <= 1)
        return false;
        //字符个数为奇数就说明一定有一个未匹配所以就直接返回
        if(len%2 == 1)
        return false;
        //tail记录栈顶的位置
        int tail = 0;
        char* arr = (char*)malloc(len*sizeof(char));
        int i = 0;
        for(int i = 0; i<len; i++)
        {
        
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
        
            	arr[tail++] = s[i];
            }
            else
            {
        
                if(tail == 0)
                return false;
                if(s[i] == ')')
                {
        
                    if(arr[tail-1] != '(')
                    return false;
                }
                else if(s[i] == ']')
                {
        
                    if(arr[tail-1] != '[')
                    {
        
                        return false;
                    }
                }
                else
                {
        
                    if(arr[tail-1] != '{')
                    {
        
                        return false;
                    }
                }
                tail--;
            }
        }
        if(tail == 0)
        return true;
        return false;
    }

![在这里插入图片描述][b1416937552a4229a6a944960774264b.png]

## 环形链表 ##

[leetcode之环形链表][leetcode 1]

### 题目要求 ###

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

### 用例输入 ###

示例 1：  
![在这里插入图片描述][4e82675d6b324281946cdd3dd3f9b910.png]

输入：head = \[3,2,0,-4\], pos = 1  
输出：true  
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：  
![在这里插入图片描述][1c0f8084f1934994a8e265cc588f0df0.png]

输入：head = \[1,2\], pos = 0  
输出：true  
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：  
![在这里插入图片描述][d8b661a40d7a46e2bf3077b9e734c5d8.png]

输入：head = \[1\], pos = -1  
输出：false  
解释：链表中没有环。

### 做题思路 ###

如果该链表是有环的，那么我们使用两个指针：快指针跟慢指针，慢指针一次走一个结点，快指针走两个结点，他们最终一定会相遇。

### 代码实现 ###

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    bool hasCycle(struct ListNode *head) {
        
        struct ListNode* low = head;
        struct ListNode* fast = head;
        while(fast && fast->next)
        {
        
            low = low->next;
            fast = fast->next->next;
    
            if(low == fast)
            return true;
        }
    
        return false;
        
    }

![在这里插入图片描述][5a3c6a26746c430499f555546cc2c455.png]

## 环形链表 II ##

[leetcode之环形链表 ||][leetcode_]

### 题目要求 ###

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

### 用例输入 ###

示例 1：

![在这里插入图片描述][5223e763f40e40f39ea66b2cc5ac6104.png]

输入：head = \[3,2,0,-4\], pos = 1  
输出：返回索引为 1 的链表节点  
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：  
![在这里插入图片描述][b7ca0e2809984d5286c7ada2c3bc02df.png]

输入：head = \[1,2\], pos = 0  
输出：返回索引为 0 的链表节点  
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：  
![在这里插入图片描述][a657a80c67f14e03a8a52de2b7704ff7.png]

输入：head = \[1\], pos = -1  
输出：返回 null  
解释：链表中没有环。

### 做题思路 ###

我们这个题还得需要上面的判断是否是环形链表的知识，有一个结论：当快慢指针相遇的时候，让指针分别在链表的头结点跟相遇的结点开始走，每次走一个结点，他们最终会在环形链表的入口处相遇。

### 代码实现 ###

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    struct ListNode *detectCycle(struct ListNode *head) {
        
        struct ListNode* slow = head;
        struct ListNode* fast = head;
    
        while(fast && fast->next)
        {
        
            slow = slow->next;
            fast = fast->next->next;
    
            if(slow == fast)
            {
        
                struct ListNode* meet = slow;
    
                while(head != meet)
                {
        
                    meet = meet->next;
                    head = head->next;
                }
                return meet;
            }
        }
        return NULL;
    }

![在这里插入图片描述][83636851bbba4e7bb20c41a4c6232bab.png]

[leetcode]: https://leetcode.cn/problems/valid-parentheses/description/
[b1416937552a4229a6a944960774264b.png]: https://img-blog.csdnimg.cn/b1416937552a4229a6a944960774264b.png
[leetcode 1]: https://leetcode.cn/problems/linked-list-cycle/
[4e82675d6b324281946cdd3dd3f9b910.png]: https://img-blog.csdnimg.cn/4e82675d6b324281946cdd3dd3f9b910.png
[1c0f8084f1934994a8e265cc588f0df0.png]: https://img-blog.csdnimg.cn/1c0f8084f1934994a8e265cc588f0df0.png
[d8b661a40d7a46e2bf3077b9e734c5d8.png]: https://img-blog.csdnimg.cn/d8b661a40d7a46e2bf3077b9e734c5d8.png
[5a3c6a26746c430499f555546cc2c455.png]: https://img-blog.csdnimg.cn/5a3c6a26746c430499f555546cc2c455.png
[leetcode_]: https://leetcode.cn/problems/linked-list-cycle-ii/
[5223e763f40e40f39ea66b2cc5ac6104.png]: https://img-blog.csdnimg.cn/5223e763f40e40f39ea66b2cc5ac6104.png
[b7ca0e2809984d5286c7ada2c3bc02df.png]: https://img-blog.csdnimg.cn/b7ca0e2809984d5286c7ada2c3bc02df.png
[a657a80c67f14e03a8a52de2b7704ff7.png]: https://img-blog.csdnimg.cn/a657a80c67f14e03a8a52de2b7704ff7.png
[83636851bbba4e7bb20c41a4c6232bab.png]: https://img-blog.csdnimg.cn/83636851bbba4e7bb20c41a4c6232bab.png