leetcode面试经典算法题——2

链接：https://leetcode.cn/studyplan/top-interview-150/

20. 有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

Python代码

class Solution:def isValid(self, s: str) -> bool:stack = []# 利用栈先进后出的特点，遇见左符号就进栈，遇见右符号则判断栈顶的符号是否与之匹配。len_s = len(s)if len_s < 2:return Falsefor item in s:stack_len = len(stack)if item == "(" or item == "[" or item == "{":stack.append(item)if item == ")":if stack_len != 0 and stack[-1] == "(":stack.pop()else:return Falseelif item == "]":if stack_len != 0 and stack[-1] == "[":stack.pop()else:return Falseelif item == "}":if stack_len != 0 and stack[-1] == "{":stack.pop()else:return Falsei += 1# 操作之后，栈空则全部符合，否则无效if len(stack) == 0:return Trueelse:return Falseif __name__ == '__main__':s = Solution()a = "){}"print(s.isValid(a))

C++代码

#include <iostream>
#include <stack>
using namespace std;class Solution {
public:bool isValid(string s) {// 创建字符栈stack<char> myStack; int len_s = s.size();if (len_s < 2) return false;int i;for (i = 0; i < len_s; i++){int stack_len = myStack.size(); // 获得栈大小if (s[i] == '(' || s[i] == '[' || s[i] == '{')myStack.push(s[i]);else if (s[i] == ')') {if (stack_len != 0 && myStack.top() == '(') myStack.pop();else return false;}else if (s[i] == ']') {if (stack_len != 0 && myStack.top() == '[') myStack.pop();else return false;}else if (s[i] == '}') {if (stack_len != 0 && myStack.top() == '{') myStack.pop();else return false;}}return myStack.empty(); // 检查栈是否为空}
};int main() {Solution s;string a = "())";cout << s.isValid(a) << endl;return 0;
}

141. 环形链表

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

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

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

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

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

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

提示：

• 链表中节点的数目范围是 [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos 为 -1 或者链表中的一个 有效索引 。

Python代码

# Definition for singly-linked list.
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def hasCycle(self, head: ListNode) -> bool:# 使用快慢指针，快指针每次走两个结点，慢指针每次走一个结点，当快指针遇上慢指针则存在环fast = headslow = headwhile fast:if fast.next:fast = fast.next.nextelse:breakslow = slow.nextif fast == slow:return Truereturn False
def CreateListNode(l1):head = ListNode(l1[0])node = headfor i in range(1, len(l1)):new_head = ListNode(l1[i])node.next = new_headnode = new_headreturn head

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：