有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

提示：

• 1 <= s.length <= 104

• s 仅由括号 '()[]{}' 组成

解题思路

使用栈来跟踪未匹配的开括号，利用后进先出（LIFO）特性来确保括号的正确嵌套顺序。

初始化：

HashMap<Character, Character> map = new HashMap();
map.put('(', ')');
map.put('{', '}');
map.put('[', ']');

• 创建映射关系：开括号 → 闭括号

• 这样可以通过开括号快速找到对应的闭括号

遍历字符串：

for (int i = 0; i < arr.length; i++) {

处理开括号：

if (map.containsKey(arr[i])) {
    stack.push(arr[i]);
}

• 如果是开括号（'(', '{', '['），压入栈中

处理闭括号：

else {
    if (stack.isEmpty() || map.get(stack.pop()) != arr[i]) {
        return false;
    }
}

• 如果是闭括号，检查：

  • 栈是否为空（没有对应的开括号）→ 无效

  • 栈顶的开括号对应的闭括号是否与当前字符匹配 → 不匹配则无效

• 如果匹配，弹出栈顶元素（完成一对匹配）

最终检查：

if(!stack.isEmpty()){
    return false;
}
return true;

• 遍历完成后，如果栈不为空，说明有未匹配的开括号 → 无效

• 栈为空则所有括号都正确匹配 → 有效

class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');

        Stack stack = new Stack();

        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                stack.push(arr[i]);
            } else {
                if (stack.isEmpty() || map.get(stack.pop()) != arr[i]) {
                    return false;
                }
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }

        return true;
    }
}

环形链表 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 <= 105

• pos 的值为 -1 或者链表中的一个有效索引

解题思路（滑动窗口）

1. 数据结构选择：使用 HashSet<ListNode> 来存储已经访问过的节点

2. 遍历链表：

   • 从头节点开始遍历

   • 对于每个节点，检查是否已经在 HashSet 中存在

   • 如果不存在，将其加入 HashSet 并继续遍历下一个节点

   • 如果存在，说明找到了环的起始节点，返回该节点

3. 终止条件：

   • 如果遍历到 null（链表末尾），说明没有环，返回 null

public class Solution {
    public ListNode detectCycle(ListNode head) {
        		HashSet<ListNode> objects = new HashSet<>();
		while (head != null && !objects.contains(head)) {
			objects.add(head);
			head = head.next;
		}
		return head;
    }
}