LeetCode 20. 有效的括号
20. 有效的括号题目给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例 1：
12输入：s = "()"输出：true
示例 2：
12输入：s = "()[]{}"输出：true
示例 3：
12输入：s = "(]"输出：false
示例 4：
12输入：s = "([)]"输出：false
示例 5：
12输入：s = "{[]}"输出：true
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
思路使用栈实现，进来一个元素和栈顶元素对比，如果能够匹配上则弹出栈顶元素，否则把这个元素压入栈
实现
LeetCode 200. 岛屿数量
200. 岛屿数量题目给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
1234567输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]输出：1
示例 2：
1234567输入：grid = [ ["1","1",& ...
LeetCode 208. 实现 Trie (前缀树)
208. 实现 Trie (前缀树)题目Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”][[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]输出[null, null, tr ...
LeetCode 209. 长度最小的子数组
209. 长度最小的子数组题目给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]输出：2解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
输入：target = 4, nums = [1,4,4]输出：1示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]输出：0
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
思路第一个是滑动窗口，先从第一个值开始逐个遍历找到大于target的end，然后增大end，递减star ...
LeetCode 21. 合并两个有序链表
21. 合并两个有序链表题目将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
12输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]
示例 2：
12输入：l1 = [], l2 = []输出：[]
示例 3：
12输入：l1 = [], l2 = [0]输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]-100 <= Node.val <= 100l1 和 l2 均按 非递减顺序 排列
思路创建一个空的节点记录结果，然后比较两个链表中节点的值比较小的，放在head.next，然后依次进行，最后必定有一个链表为空，然后head.next = 另一个链表。
实现123456789101112131415161718public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode preHead = new ListNode(-1); ListNode ...
LeetCode 215. 数组中的第K个最大元素
215. 数组中的第K个最大元素题目给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
12输入: [3,2,1,5,6,4] 和 k = 2输出: 5
示例 2:
12输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4
1234提示：1 <= k <= nums.length <= 104-104 <= nums[i] <= 104
思路
对数组全部排序玩后，拿到第k个最大的数
使用快排的变形，如果基准值右边的数大于k了，我们就把左边的数抛弃，如果基准值就是k，我们已经不用排序了
实现整体排序123456private static class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - ...
LeetCode 23. 合并K个升序链表
23. 合并K个升序链表题目给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
12345678910输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6
示例 2：
12输入：lists = []输出：[]
示例 3：
12输入：lists = [[]]输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
思路分治的思想，我们每次两个两个合并，然后在两个两个合并
实现12345678 ...
LeetCode 236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先题目给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出：5解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
12输入：root = [1,2], p = 1, q = 2输出：1
提示：
12345树中节点数目在范围 [2, 105] 内。-109 <= Node.val <= 109所有 Node.val 互不相同 。p != qp 和 q 均存在于给定的二叉树 ...
LeetCode 142. 环形链表 II
142. 环形链表 II题目给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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 或者链表中的一个有效索引
思路也是快门指针，相 ...
LeetCode 143. 重排链表
143. 重排链表题目给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]输出：[1,4,2,3]示例 2：
输入：head = [1,2,3,4,5]输出：[1,5,2,4,3]
提示：
链表的长度范围为 [1, 5 * 104]1 <= node.val <= 1000
思路
找到中间节点
翻转右边的链表
原左边的链表和右边的链表合并
这个题的主要难点：
拿到中间节点的时候，我们要考虑引用的链表在什么情况下会改变原来的值，当我们直接置空的时候不会改变原来饿值，但是我们next=null的时候会改变原来的值，所以我们可以直接返回中间节点的上一个节点
然后通过 mid.next = null;改变原来节点的值，划分出leftNode 和 rightNode
然后翻转链表，两个链表合并
...
LeetCode 144. 二叉树的前序遍历
144. 二叉树的前序遍历题目给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]输出：[1,2,3]示例 2：
输入：root = []输出：[]示例 3：
输入：root = [1]输出：[1]示例 4：
输入：root = [1,2]输出：[1,2]示例 5：
输入：root = [1,null,2]输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
思路就是二叉树的层序遍历
实现1234567891011121314151617181920212223class Solution { public List<Integer> preorderTraversal(TreeNode root) { if (root == null){ return new ArrayList<>( ...
LeetCode 148. 排序链表
148. 排序链表题目给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]输出：[1,2,3,4]示例 2：
输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5]示例 3：
输入：head = []输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内-105 <= Node.val <= 105
思路先对链表进行拆分，然后链表逐个合并（合并两个有序链表），类似第23题合并k个升序链表
实现1
LeetCode 15. 三数之和
15. 三数之和题目给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
12输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]
示例 2：
12输入：nums = []输出：[]
示例 3：
12输入：nums = [0]输出：[]
123提示：0 <= nums.length <= 3000-105 <= nums[i] <= 105
思路本题的难点在于去除重复的元素，这个题类似于全排列II、子集II都是需要排序后去重
第一种：三种for循环暴力求解
第二种：for循环的时间复杂度太高，在O(n^3^)，优化后使用两次for循环，在第三次的时候我们使用两个指针来代替（因为我们已经使用了排序，所以才能使用指针）
先对数组进行排序
第一层为for循环，第二层为while循环（left < right）
要排除重复元素，如果这个值和前 ...
LeetCode 151. 翻转字符串里的单词
151. 翻转字符串里的单词题目给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。翻转后单词间应当仅用一个空格分隔。翻转后的字符串中不应包含额外的空格。
示例 1：
输入：s = “the sky is blue”输出：”blue is sky the”示例 2：
输入：s = “ hello world “输出：”world hello”解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。示例 3：
输入：s = “a good example”输出：”example good a”解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。示例 4：
输入：s = “ Bob Loves Alice “输出：”Alice Loves Bob”示例 5：
输入：s = “Alice does not even li ...
LeetCode 153. 寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值题目已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
123输入：nums = [3,4,5,1,2]输出：1解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
123输入：nums = [4,5,6,7,0,1,2]输出：0解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
123输入：nums = [11,13,15,17 ...
