晋城市建设局网站,山西大同专业网站建设制作价格,中国设计师网站,网站开发培训学校网站各位朋友们#xff0c;又是新的一天#xff0c;不知道大家过得怎样#xff1f;今天是我leedcode刷题系列的第二篇#xff0c;那么废话不多说#xff0c;直接进入我们今天的主题。 文章目录有效的括号题目要求用例输入做题思路代码实现环形链表题目要求用例输入做题思路代码…各位朋友们又是新的一天不知道大家过得怎样今天是我leedcode刷题系列的第二篇那么废话不多说直接进入我们今天的主题。 文章目录有效的括号题目要求用例输入做题思路代码实现环形链表题目要求用例输入做题思路代码实现环形链表 II题目要求用例输入做题思路代码实现有效的括号
leedcode之有效的括号
题目要求
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
用例输入
示例 1 输入s “()” 输出true
示例 2 输入s “()[]{}” 输出true
示例 3 输入s “(]” 输出false
做题思路
这道题的要求是需要我们判断给的括号是否合法意思就是当我们遇到有括号的时候我们需要判断左边最近的左括号是否跟这个右括号匹配。我们可以使用一种数据结构栈来解决这个问题因为栈是一端进一端出这一端被称为栈顶先进后出后进先出。所以我们把左括号都放在栈中当遇到右括号时我们就从栈顶取出左括号看是否跟这个右括号匹配匹配就继续下一个字符不匹配就返回true。当这个字符串遍历完后如果栈中不为空说明有左括号未匹配返回false否则返回true。
代码实现
bool isValid(char * s){int len strlen(s);//当字符串中没有或者只有一个字符时就直接返回falseif(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; ilen; 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;
}环形链表
leedcode之环形链表
题目要求
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
用例输入
示例 1
输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。
示例 2
输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。
示例 3
输入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;}环形链表 II
leedcode之环形链表 ||
题目要求
给定一个链表的头节点 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 解释链表中没有环。
做题思路
我们这个题还得需要上面的判断是否是环形链表的知识有一个结论当快慢指针相遇的时候让指针分别在链表的头结点跟相遇的结点开始走每次走一个结点他们最终会在环形链表的入口处相遇。
代码实现
/*** 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;
}
