382. 链表随机节点给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。 进阶:如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？ 示例: // 初始化一个单链表 [1,2,3].ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);Solution solution = new Solution(head); // getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等...

645. 错误的集合集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 nums 代表了集合 S 发生错误后的结果。 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。 示例 1： 输入：nums = [1,2,2,4]输出：[2,3]示例 2： 输入：nums = [1,1]输出：[1,2]解题思路利用映射的思想我们先让每个位置的数字作为索引，使其索引对应位置的数变为负数。这样一旦其对应位置本身为负数，则证明重复（找到重复的数也不可跳出，必须...

372. 超级次方你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。 示例 1： 输入：a = 2, b = [3]输出：8示例 2： 输入：a = 2, b = [1,0]输出：1024示例 3： 输入：a = 1, b = [4,3,3,8,5,2]输出：1示例 4： 输入：a = 2147483647, b = [2,0,0]输出：1198解题思路1.如何求指数为数组的幂 ****2.对乘积求余=对因子求余，再对乘积求余（防止溢出）(ab)%base=((a%base)(b%base))%base;3.如何高效求幂* ** * cla...

204. 计数质数统计所有小于非负整数 n 的质数的数量。 示例 1： 输入：n = 10输出：4解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。示例 2： 输入：n = 0输出：0示例 3： 输入：n = 1输出：0 提示： 0 <= n <= 5 * 106解题思路利用质数的倍数都不是质数来排除质数而且由于质数因子的对称性，所以可以外层循环只遍历2~sqrt（n）内层则直接计算sqrn（n）之后的，这样可以避免重叠 class Solution { public int countPrimes(int n) { boolean...

793. 阶乘函数后K个零 f(x) 是 x! 末尾是0的数量。（回想一下 x! = 1 * 2 * 3 * ... * x，且0! = 1） 例如， f(3) = 0 ，因为3! = 6的末尾没有0；而 f(11) = 2 ，因为11!= 39916800末端有2个0。给定 K，找出多少个非负整数x ，有 f(x) = K 的性质。 示例 1:输入:K = 0输出:5解释: 0!, 1!, 2!, 3!, and 4! 均符合 K = 0 的条件。 示例 2:输入:K = 5输出:0解释:没有匹配到这样的 x!，符合K = 5 的条件。注意： K是范围在 [0, 10^9] 的整数。解题思路...

172. 阶乘后的零给定一个整数 n，返回 n! 结果尾数中零的数量。 示例 1: 输入: 3输出: 0解释: 3! = 6, 尾数中没有零。示例 2: 输入: 5输出: 1解释: 5! = 120, 尾数中有 1 个零.解题思路0来自于2乘以5，每个偶数都可以分离出2，所以转换为了求有几个5.那个就是5的倍数可以提高一个5,25的倍数可以提高2个，125的倍数可以提高三个。也就是看其是5的几次幂就可以提供几个5 class Solution { public int trailingZeroes(int n) { int res=0; for(int...

231. 2的幂给定一个整数，编写一个函数来判断它是否是 2 的幂次方。 示例 1: 输入: 1输出: true解释: 20 = 1示例 2: 输入: 16输出: true解释: 24 = 16示例 3: 输入: 218输出: false 解题思路简单的位运算操作：见注释，2的幂只有一个1 class Solution { public boolean isPowerOfTwo(int n) { if(n<=0) return false; return (n&(n-1))==0;//2的幂一定是只含有一个1，所以去除末尾的1之后就该是0...

773. 滑动谜题在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示. 一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换. 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。 给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。 示例： 输入：board = [[1,2,3],[4,0,5]]输出：1解释：交换 0 和 5 ，1 步完成输入：board = [[1,2,3],[5,4,0]]输出：-1解释：没有办法完成谜板输入：board = [[4,1...

752. 打开转盘锁你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。 字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。 示例 1...

111. 二叉树的最小深度给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。示例 2： 输入：root = [2,null,3,null,4,null,5,null,6]输出：5解题思路利用BFS框架，每次同步前进一步，这样一旦遇见底，就是找到了最短路径，也就是树的最小深度 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode...

37. 解数独编写一个程序，通过填充空格来解决数独问题。 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。空白格用 '.' 表示。 一个数独。 答案被标成红色。 提示： 给定的数独序列只包含数字 1-9 和字符 '.' 。你可以假设给定的数独只有唯一解。给定数独永远是 9x9 形式的。解题思路利用回溯算法的思想：先遍历每行，行完了再遍历下一行如果到最后一列，则换下一行如果到最后一行，则说明找到了可信解，返回true如果该位置已经有值，则跳出然后遍历1-9九个选择判断当前字符是...

22. 括号生成数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例 1： 输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"]示例 2： 输入：n = 1输出：["()"] 解题思路利用回溯和DFS的思路我们每次只有选（和）两种情况，可以直接进行套DFS框架，就没必要进行回溯了注意特点：剩下的右括号一定大于左括号（因为左括号大多在左边） class Solutio...

77. 组合给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2输出:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]解题思路和子集问题一样，只不过这里有结束条件，也就是我们只要长度为k的子集还是回溯算法解答 class Solution { List<List<Integer>> res=new LinkedList<>(); public List<List<Integer>> combine(...

78. 子集给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1： 输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2： 输入：nums = [0]输出：[[],[0]]解题思路还是利用回溯算法框架结束条件是每一个路径都可以作为结果存入为了避免重复，每次记录当前索引，不往前遍历。只遍历之后的元素也就是【1,2,3】，先选1，再就只能在2,3里选。如果先选2，则只能选3，不能选1 class Solutio...