宁波论坛建站模板,wordpress发布公告,河北省建设中心网站,磁力搜索器kitty目录 一、环形链表
方法#xff08;快慢指针#xff09;#xff1a;
二、环形链表 II
三、有效的括号 一、环形链表
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链…目录 一、环形链表
方法快慢指针
二、环形链表 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;
}
今天就先到这了 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
