leetcode口试经典算法题——2

链接：https://leetcode.cn/studyplan/top-interview-150/
20. 有用的括号

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

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

示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
Python代码

1. class Solution:
2.     def isValid(self, s: str) -> bool:
3.         stack = []
4.         # 利用栈先进后出的特点，遇见左符号就进栈，遇见右符号则判断栈顶的符号是否与之匹配。
5.         len_s = len(s)
6.         if len_s < 2:
7.             return False
8.         for item in s:
9.             stack_len = len(stack)
10.             if item == "(" or item == "[" or item == "{":
11.                 stack.append(item)
12.             if item == ")":
13.                 if stack_len != 0 and stack[-1] == "(":
14.                     stack.pop()
15.                 else:
16.                     return False
17.             elif item == "]":
18.                 if stack_len != 0 and stack[-1] == "[":
19.                     stack.pop()
20.                 else:
21.                     return False
22.             elif item == "}":
23.                 if stack_len != 0 and stack[-1] == "{":
24.                     stack.pop()
25.                 else:
26.                     return False
27.             
28.             i += 1
29.         # 操作之后，栈空则全部符合，否则无效
30.         if len(stack) == 0:
31.             return True
32.         else:
33.             return False
34.             
35.                
36.         
37. if __name__ == '__main__':
38.     s = Solution()
39.     a = "){}"
40.     print(s.isValid(a))

复制代码

C++代码

1. #include <iostream>
2. #include <stack>
3. using namespace std;
5. class Solution {
6. public:
7.     bool isValid(string s) {
8.     // 创建字符栈
9.         stack<char> myStack;
10.         int len_s = s.size();
11.         if (len_s < 2) return false;
12.         int i;
13.         for (i = 0; i < len_s; i++){
14.             int stack_len = myStack.size(); // 获得栈大小
15.             if (s[i] == '(' || s[i] == '[' || s[i] == '{')
16.                     myStack.push(s[i]);
17.             else if (s[i] == ')') {
18.                 if (stack_len != 0 && myStack.top() == '(') myStack.pop();
19.                 else return false;
20.             }
21.             else if (s[i] == ']') {
22.                 if (stack_len != 0 && myStack.top() == '[') myStack.pop();
23.                 else return false;
24.             }
25.             else if (s[i] == '}') {
26.                 if (stack_len != 0 && myStack.top() == '{') myStack.pop();
27.                 else return false;
28.             }
29.         }
30.         return myStack.empty(); // 检查栈是否为空
31.     }
32. };
34. int main() {
35.     Solution s;
36.     string a = "())";
37.     cout << s.isValid(a) << endl;
38.     return 0;
39. }

复制代码

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代码

1. # Definition for singly-linked list.
2. class ListNode:
3.     def __init__(self, x):
4.         self.val = x
5.         self.next = None
8. class Solution:
9.     def hasCycle(self, head: ListNode) -> bool:
10.         # 使用快慢指针，快指针每次走两个结点，慢指针每次走一个结点，当快指针遇上慢指针则存在环
11.         fast = head
12.         slow = head
13.         while fast:
14.             if fast.next:
15.                 fast = fast.next.next
16.             else:
17.                 break
18.             slow = slow.next
19.             if fast == slow:
20.                 return True
21.             
22.         return False
23. def CreateListNode(l1):
24.     head = ListNode(l1[0])
25.     node = head
26.     for i in range(1, len(l1)):
27.         new_head = ListNode(l1[i])
28.         node.next = new_head
29.         node = new_head
30.     return 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]
提示：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告