剑指 Offer 06. 从尾到头打印链表
剑指 Offer 06. 从尾到头打印链表1234567891011121314输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 1：输入：head = [1,3,2]输出：[2,3,1] 限制：0 <= 链表长度 <= 10000
原理：
链表只有一个头结点，想要到尾结点只能从头开始遍历
辅助空间声明一个辅助空间，先遍历一遍确定辅助空间的大小，然后对辅助空间倒序打印
1234567891011121314151617181920212223242526/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public int[] reversePrint(ListNode head) { ListNo ...
700. 二叉搜索树中的搜索
700. 二叉搜索树中的搜索题目12345678910111213141516171819给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。例如，给定二叉搜索树: 4 / \ 2 7 / \ 1 3和值: 2你应该返回如下子树: 2 / \ 1 3在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
思路什么是二叉搜索树二叉搜索树二叉搜索树是一棵二叉树，每个节点都有以下特性：
大于左子树上任意一个节点的值，
小于右子树上任意一个节点的值。
也就是比根节点小的值放左边，比根节点大的值放右边
一个二叉搜索树的例子：
二叉搜索树中复杂度为对数时间的操作：
查找。
插入。
删除。
实现递归123456789101112131415private static class Solution { public TreeNode sear ...
LeetCode 704. 二分查找
704. 二分查找题目给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
123输入: nums = [-1,0,3,5,9,12], target = 9输出: 4解释: 9 出现在 nums 中并且下标为 4
示例 2:
123输入: nums = [-1,0,3,5,9,12], target = 2输出: -1解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
思路二分，先找到中间的值，如果目标值比中间的值小，做找左边，否则找右边
实现
LeetCode 72. 编辑距离
72. 编辑距离题目给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符删除一个字符替换一个字符
示例 1：
输入：word1 = “horse”, word2 = “ros”输出：3解释：horse -> rorse (将 ‘h’ 替换为 ‘r’)rorse -> rose (删除 ‘r’)rose -> ros (删除 ‘e’)示例 2：
输入：word1 = “intention”, word2 = “execution”输出：5解释：intention -> inention (删除 ‘t’)inention -> enention (将 ‘i’ 替换为 ‘e’)enention -> exention (将 ‘n’ 替换为 ‘x’)exention -> exection (将 ‘n’ 替换为 ‘c’)exection -> execution (插入 ‘u’)
提示：
0 <= word1.length, word ...
LeetCode 76. 最小覆盖子串
76. 最小覆盖子串题目给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”输出：”BANC”示例 2：
输入：s = “a”, t = “a”输出：”a”示例 3:
输入: s = “a”, t = “aa”输出: “”解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 105s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
思路滑动窗口实现，两个指针：left和right，最开始right向右移动直到目标字符串被全部包括，然后right想右移动在遇到目标字符串重复字符的时候，left判断是否可以右移，记录当 ...
LeetCode 77. 组合
77. 组合题目给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
12345678910输入：n = 4, k = 2输出：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
示例 2：
12输入：n = 1, k = 1输出：[[1]]
提示：
1 <= n <= 201 <= k <= n
思路还是一个回溯的思路
实现
LeetCode 78. 子集
78. 子集题目给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
12输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
12输入：nums = [0]输出：[[],[0]]
提示：
1231 <= nums.length <= 10-10 <= nums[i] <= 10nums 中的所有元素 互不相同
思路实现
LeetCode 82. 删除排序链表中的重复元素 II
82. 删除排序链表中的重复元素 II题目存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,2,3,3,4,4,5]输出：[1,2,5]示例 2：
输入：head = [1,1,1,2,3]输出：[2,3]
提示：
链表中节点数目在范围 [0, 300] 内-100 <= Node.val <= 100题目数据保证链表已经按升序排列
思路因为要删除所有重复的元素，我们可以直接判断node.next和node.next.next是否重复，如果重复，在进行一个while循环循环去重
实现12345678910111213141516171819202122private static class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null) { ...
LeetCode 8. 字符串转换整数 (atoi)
8. 字符串转换整数 (atoi)题目请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。返回整数作为最终结果。注意：
本题中的空白字符只包括空格字符 ‘ ‘ 。除前导空格或数字后的其余字 ...
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 463. 岛屿的周长
463. 岛屿的周长题目给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 1：
123输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]输出：16解释：它的周长是上面图片中的 16 个黄色的边
示例 2：
12输入：grid = [[1]]输出：4
示例 3：
12输入：grid = [[1,0]]输出：4
提示：
1234row == grid.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j] 为 0 或 1
思路实现
LeetCode 47. 全排列 II
47. 全排列 II题目给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
12345输入：nums = [1,1,2]输出：[[1,1,2], [1,2,1], [2,1,1]]
示例 2：
12输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
123提示：1 <= nums.length <= 8-10 <= nums[i] <= 10
思路也是一个全拍列组合，但是我们如果使用46题的全排列组合会产生重复的数据，所以需要先对数组进行排序，这个是一贯思路，只要排除重复大部分情况下的组合都是通过前排序，然后和前一个数对比实现去重
实现12345678910111213141516171819202122232425262728293031private static class Solution { boolean[] used; Deque<Integer> col = new Lin ...
5. 最长回文子串
5. 最长回文子串题目1234567891011121314151617181920212223242526给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。示例 2：输入：s = "cbbd"输出："bb"示例 3：输入：s = "a"输出："a"示例 4：输入：s = "ac"输出："a" 提示：1 <= s.length <= 1000s 仅由数字和英文字母（大写和/或小写）组成
思路动态规划：我们主要是找状态转移方程
对于任意的一个回文字符串，减去两头的两个字符，剩下的字符也一定是回文字符串，所以我们就找到了最小子问题，这一点很容易想到，但是这个状态转移方程，如果是第一次做这种字符串的动归，真的不容易想到。这类字符串的动归的关键思路是把一个字符串拆分为数个子字符串
我们用 P(i,j)表示字符串 ...
LeetCode 53. 最大子数组和
53. 最大子数组和题目给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
123输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
12输入：nums = [1]输出：1
示例 3：
12输入：nums = [5,4,-1,7,8]输出：23
1234提示：1 <= nums.length <= 105-104 <= nums[i] <= 104
思路第一种方法就是，双重for循环暴力求解
第二种方法就是，动态规划，在原来的数组上，每位置替换为之前数组累加的最大值
实现1
LeetCode 51. N 皇后
51. N 皇后题目n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：
123输入：n = 4输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
12输入：n = 1输出：[["Q"]]
提示：
1 <= n <= 9
思路实现
