广州化妆品网站制作,如何引用404做网站,做网站需要什么权限,江苏建设厅网站更新1环形链表 II
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测…1环形链表 II
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。 示例 1 输入head [3,2,0,-4], pos 1
输出返回索引为 1 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出返回 null
解释链表中没有环。提示
链表中节点的数目范围在范围 [0, 104] 内-105 Node.val 105pos 的值为 -1 或者链表中的一个有效索引
思路 初始化指针 使用两个指针 fast 和 slow初始时都指向链表的头节点 head。 检测环 在一个 while 循环中不断移动 fast 和 slow 指针直到 fast 或 fast-next 变为 NULL 或者 fast 和 slow 指针相遇。fast 指针每次移动两步fast fast-next-next。slow 指针每次移动一步slow slow-next。当 fast 和 slow 指针相遇时说明链表中存在环。 检查是否有环 如果 fast 或 fast-next 变为 NULL说明链表没有环此时返回 NULL。 找到环的入口 当快慢指针相遇后将 fast 指针重新指向链表的头节点 head。然后让 fast 和 slow 指针同时每次移动一步直到它们再次相遇。二者相遇的节点就是环的入口节点。 返回环的入口节点 返回 fast 或 slow 指针它们此时指向环的入口节点。
代码
struct ListNode *detectCycle(struct ListNode *head) {// 使用快慢指针检测是否有环struct ListNode* fast head;struct ListNode* slow head;while (true) {// 如果快指针或快指针的下一个节点为 nullptr直接返回 nullptrif (fast nullptr || fast-next nullptr) {return nullptr; }fast fast-next-next; // 快指针移动两步slow slow-next; // 慢指针移动一步// 检查快慢指针是否相遇if (fast slow) {break; // 找到环}}// 找到环的入口fast head; // 将快指针重置到头节点while (fast ! slow) {fast fast-next; // 快指针和慢指针同时移动一步slow slow-next;}// 返回环的入口节点return fast;
}
2有效的括号
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例 1
输入s ()
输出true
示例 2
输入s ()[]{}
输出true
示例 3
输入s (]
输出false
示例 4
输入s ([])
输出true 提示
1 s.length 104s 仅由括号 ()[]{} 组成
思路
先来分析一下 这里有三种不匹配的情况 第一种情况字符串里左方向的括号多余了 所以不匹配。第一种情况已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号来匹配所以return false 第二种情况括号没有多余但是 括号的类型没有匹配上。第二种情况遍历字符串匹配的过程中发现栈里没有要匹配的字符。所以return false 第三种情况字符串里右方向的括号多余了所以不匹配。遍历字符串匹配的过程中栈已经为空了没有匹配的字符了说明右括号没有找到对应的左括号return false 我们的代码只要包含这三种不匹配的情况就不会出问题 字符串遍历完之后栈是空的就说明全都匹配了。
代码
bool isValid(char * s) {int len strlen(s);// 为栈分配内存栈最多能存储 len 个元素char* stack malloc(sizeof(char) * len); int count 0; // 栈的当前大小// 遍历字符串中的每个字符for (int i 0; i len; i) {// 如果是左括号压入栈中if (s[i] ( || s[i] { || s[i] [) {stack[count] s[i]; // 将左括号压入栈中} // 如果是右括号进行匹配检查else {// 检查当前栈是否为空或栈顶的左括号是否与当前右括号匹配if (count 0) {// 情况 3遍历字符串匹配的过程中栈已经为空了没有匹配的字符了说明右括号没有找到对应的左括号return false; }char top stack[count - 1]; // 获取栈顶元素// 检查匹配if ((s[i] ) top () || (s[i] } top {) || (s[i] ] top [)) {count--; // 匹配成功弹出栈顶元素} else {// 情况 2遍历字符串匹配的过程中发现栈里没有要匹配的字符return false; }}}// 情况 1已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号来匹配return count 0; // 返回 true表示有效否则返回 false无效
}
