LeetCode 300. 最长递增子序列
300. 最长递增子序列题目给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
123输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
12输入：nums = [0,1,0,3,2,3]输出：4
示例 3：
12输入：nums = [7,7,7,7,7,7,7]输出：1
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
进阶：
你可以设计时间复杂度为 O(n2) 的解决方案吗？你能将算法的时间复杂度降低到 O(n log(n)) 吗?
思路O(n2) 这个一看就是动态规划，对动态太规划算法的进一步优化就是贪心
实现动态规划后面这个结果依赖于前面结果的最大值，寻找j的结果的时候，我们从0开始遍历，挨个对比如果是递增的就加一， ...
LeetCode 31. 下一个排列
31. 下一个排列题目实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]输出：[1,3,2]示例 2：
输入：nums = [3,2,1]输出：[1,2,3]示例 3：
输入：nums = [1,1,5]输出：[1,5,1]示例 4：
输入：nums = [1]输出：[1]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
思路以排列 [4,5,2,6,3,1] 为例：
假如我们要找到它的最小排列的最小思路是什么：
大数在前面，后面的大数替换前面的一个小数
我们要替换的小数要尽可能的靠近末尾的位置
所以我们要把这个数变为453621，但是我们发现这个数也不是临近的的数，我们需要把3只有的数变为一个最小值，也就是453126
所以整体思路也就出来了，我们使用两次循环
第一次循环从后向前找 ...
322.零钱兑换
322. 零钱兑换题目1234567891011121314151617181920212223242526272829303132333435给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。示例 1：输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1示例 2：输入：coins = [2], amount = 3输出：-1示例 3：输入：coins = [1], amount = 0输出：0示例 4：输入：coins = [1], amount = 1输出：1示例 5：输入：coins = [1], amount = 2输出：2 提示：1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
思路首先就是使用递归，但是递归也是分情况的
...
387.字符串中的第一个唯一字符
387. 字符串中的第一个唯一字符题目12345678910111213给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。示例：s = "leetcode"返回 0s = "loveleetcode"返回 2 提示：你可以假定该字符串只包含小写字母。
思路实现123456789101112131415private static class Solution { public int firstUniqChar(String s) { int[] bucket = new int[26]; for (int i = 0; i < s.length(); i++) { bucket[s.charAt(i) - 'a']++; } for (int i = 0; i < s.length(); i++) { if (bucket ...
LeetCode 415. 字符串相加
415. 字符串相加题目给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
12输入：num1 = "11", num2 = "123"输出："134"
示例 2：
12输入：num1 = "456", num2 = "77"输出："533"
示例 3：
12输入：num1 = "0", num2 = "0"输出："0"
1234提示：1 <= num1.length, num2.length <= 104num1 和num2 都只包含数字 0-9num1 和num2 都不包含任何前导零
思路就是模拟加法，如果大于10进行取模，结果都保存到字符串中，最后反转字符串
实现123456789101112131415161718 ...
LeetCode 4. 寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数题目给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]输出：2.00000解释：合并数组 = [1,2,3] ，中位数 2示例 2：
输入：nums1 = [1,2], nums2 = [3,4]输出：2.50000解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5示例 3：
输入：nums1 = [0,0], nums2 = [0,0]输出：0.00000示例 4：
输入：nums1 = [], nums2 = [1]输出：1.00000示例 5：
输入：nums1 = [2], nums2 = []输出：2.00000
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000 ...
LeetCode 42. 接雨水
42. 接雨水题目给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
123输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
12输入：height = [4,2,0,3,2,5]输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
思路动态规划，定义数组，先从左边找到这个数组中的最大值，然后从右边找到数组中的最大值
双指针：为们动态规划的时候发现我们的雨水的值依赖于从左边和右边的最大值，减去原来的数组，所以我们可以使用双指针代理这个两个数组，从而动态的拿到雨水的值
实现动态规划：
12345678910111213141516171819202122232425262728private static class Solut ...
LeetCode 33. 搜索旋转排序数组
33. 搜索旋转排序数组题目整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
12输入：nums = [4,5,6,7,0,1,2], target = 0输出：4
示例 2：
12输入：nums = [4,5,6,7,0,1,2], target = 3输出：-1
示例 3：
12输入：nums = [1], target = 0输出：-1
提示：
123451 <= nums.length <= 50 ...
46. 全排列
46. 全排列题目123456789101112131415161718192021给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。示例 1：输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：输入：nums = [0,1]输出：[[0,1],[1,0]]示例 3：输入：nums = [1]输出：[[1]] 提示：1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不相同
思路全排列，典型的深度遍历加上回溯
深度优先遍历：常用的是对于二维数组，就是一次for循环加上一个递归
回溯：需要定义一个数组，记录节点是否访问过。因为本题中是要从nums中找不重复的数字，所以我们需要定义一个一维数组，记录nums中哪一个数还没有被拿过。
实现实现一通过栈来记录每次取的数据
1234567891011121314151617181920212223242526272829 ...
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 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 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 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 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 25. K 个一组翻转链表
25. K 个一组翻转链表题目给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
12输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5]
示例 2：
12输入：head = [1,2,3,4,5], k = 3输出：[3,2,1,4,5]
示例 3：
12输入：head = [1,2,3,4,5], k = 1输出：[1,2,3,4,5]
示例 4：
12输入：head = [1], k = 1输出：[1]
123456提示：列表中节点的数量在范围 sz 内1 <= sz <= 50000 <= Node.val <= 10001 <= k <= sz
思路每k个节点进行一次划分，这个内部是一个翻转链表，我们需要记录链表的start和e ...
