LeetCode 69. Sqrt(x)
69. Sqrt(x)题目给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4输出：2示例 2：
输入：x = 8输出：2解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
思路
使用二分法尝试法，对x进行二分，mid的平方小于x则，left=mid，否则right=mid
牛顿迭代法
实现二分法牛顿迭代法
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 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 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 。返回整数作为最终结果。注意：
本题中的空白字符只包括空格字符 ‘ ‘ 。除前导空格或数字后的其余字 ...
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 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 ...
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 56. 合并区间
56. 合并区间题目以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
123输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
123输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1231 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
思路先对数组进行排序，保证数组中的子数组是按照intervals[][0]进行排序的，排序后的数组是否能够合并分为下面两个结果
不能够合并，前一个合并后的right&l ...
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
思路实现
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 567. 字符串的排列
567. 字符串的排列题目给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
123输入：s1 = "ab" s2 = "eidbaooo"输出：true解释：s2 包含 s1 的排列之一 ("ba").
示例 2：
12输入：s1= "ab" s2 = "eidboaoo"输出：false
提示：
121 <= s1.length, s2.length <= 104s1 和 s2 仅包含小写字母
思路使用滑动窗口
实现
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
思路实现
62. 不同路径
62. 不同路径题目
123456789101112131415161718192021222324252627282930313233一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？示例 1：输入：m = 3, n = 7输出：28示例 2：输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下示例 3：输入：m = 7, n = 3输出：28示例 4：输入：m = 3, n = 3输出：6 提示：1 <= m, n <= 100题目数据保证答案小于等于 2 * 109
思路首先想到的就是动态规划，寻找最小子问题，找最优子结构，找状态转移方程
还是二维数组，找路径
状态转移方程：
1memo[i][j] = memo[i - 1] ...
