描述 题目描述 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。 示例 输入： [10,10,9,9,8,7,5,6,4,3,4,2],12,3 返回值：9 说明： 去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9  知识点：堆, 分治，排序，二分 难度：⭐⭐⭐  题解 图解：  方法一：快排 解题思路： 通过快排思想，将数组通过基准数分为两组，借助二分，判断基准数是否刚好是第k大的元素 算法流程：  逆序快排 以某个元素作为基准数，维...

描述 题目描述 已知int一个有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，且矩阵的行和列都是从小到大有序的。设计查找算法返回所查找元素的二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。 要求：空间复杂度 O(1)，时间复杂度 O(n+m) 示例 输入： [[1,2,3],[4,5,6]],2,3,6 返回值： [1,2]  知识点：二分查找、分治算法 难度：⭐⭐⭐  题解 图解  方法一：分治法（右上角） 解题思路： 从题目给出的要求时间复杂度至少为 O(n+m) 也可以猜出，最坏的情况会遍历一行加一列的长度 算法流程：  分治, 右上角开始查找 从右上角开始比...

描述 题目描述 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 要求：空间复杂度 O(1)，时间复杂度 O(n) 提示：输出时按非降序排列。 示例 输入： [1,4,1,6] 返回值：[4,6] 说明： 返回的结果中较小的数排在前面  知识点：位运算, 哈希 难度：⭐⭐⭐  题解   与运算, 算出异或结果的二进制位的最右的1, 作为分组的标记位 mark 最后mark与每个元素进行与运算, 根据运算结果是否为 0 分两组, 同时分别两两进行与运算, 两个组的运算结果为整数中只出现一次的两个数字  方法一：运算+分组 解题思路： 对于这种题目...

描述 题目描述 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。 要求：空间复杂度：O(1)，时间复杂度 O(n) 输入描述： 保证数组输入非空，且保证有解 示例 输入： [1,2,3,2,2,2,5,4,2] 返回值：2  知识点：数组 难度：⭐⭐  题解 图解  方法一：抵消计数 解题思路： 思路其实是简单的抵消 + 计数，对于当前元素与前一个元素数值不同，则进行抵消和计数，最后剩下的数一定是超过一半的那个数字，因为那个数...

描述 思路：  递归 动态规划  知识点：递归，动态规划 难度：⭐⭐  题解 图解：  图中圈出来的表示出现的重叠子问题，需要优化 方法一：递推 解题思路： 本题可以用自顶向下的递归方法，从一级台阶开始向上跳，那么想要跳到第n级台阶，由于题目要求一次能跳一级或二级台阶，因此要跳到n级台阶只能从n-1和n-2分别跳一级和二级台阶到达，可以得出结论：每一级台阶的跳法数量是下面的两级台阶的方法数之和。只需要注意定义递归函数功能和递归终止条件即可。 假设当前要跳上第 n 级台阶的跳法，必定是在第 n-1 和跳上 n-2 级台阶跳法数之和。 设跳上 i 级台阶有 f(n) 种跳法，则跳上 n 级台阶有 ...

描述 题目描述 我们有由底至上为从大到小放置的 n 个圆盘，和三个柱子（分别为左/中/右即left/mid/right），开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，要求一次只能移动一个圆盘，而且大的圆盘不可以放到小的上面。 请实现一个函数打印最优移动轨迹。 给定一个 int n ，表示有 n 个圆盘。请返回一个 string 数组，其中的元素依次为每次移动的描述。描述格式为： move from [left/mid/right] to [left/mid/right]。 要求：时间复杂度 O(3^n)， 空间复杂度 O(3^n) 示例 输入：2...

描述 题目描述 给定一个字符串的数组strs，请找到一种拼接顺序，使得所有的字符串拼接起来组成的字符串是所有可能性中字典序最小的，并返回这个字符串。 示例 输入：["abc","de"] 返回值："abcde"知识点：字符串，数组难度：⭐⭐⭐  题解 方法一：重载比较函数 解题思路：  算法流程：  Java通过重写优先级队列PriorityQueue的比较器方法 保证 s1 + s2 > s2 + s1 时，返回值大于0，否则返回值小于0 同时保证queue中越靠近队头的元素，字典序越小 将所有字符串放入队列中排好序，然后重新...

描述 题目描述 给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。  示例 输入：{1,2,3} 返回值：3知识点：完全二叉树，递归难度：⭐⭐⭐  题解 方法一：递归 解题思路： 完全二叉树的特性：  完全二叉树的左右子树中至少有一颗是满二叉树，叶子结点只能出现在最下两层 最下层的叶子一定集中在左部连续位置，因此最深处一定在最左下角（可用来求子树深度）。如果倒数第二层出现叶子，则一定在右边且连续 对于子树有两种情况： 情况1：若是左子树高度大，则右边子树一定是满的。 情况2：若是左右深度相同，则左边子树一定满的     根...

描述 题目描述 有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。 给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于300。 示例 输入：[[1,2,3],[4,5,6],[7,8,9]],3 返回值：[[7,4,1],[8,5,2],[9,6,3]]知识点：矩阵，模拟难度：⭐⭐⭐  题解 方法一：模拟 解题思路： 要达到顺时针旋转90°的效果，可以先根据左下——右上的对角线翻转，再上下翻转  算法流程：  如上图，可以先根据左下——右上的对角线翻转，再上下翻转 斜线翻转，根据对角线交换位置 上下翻转，交换上下元素的位置  Java 版本代码如下： i...

描述 题目描述 对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。 给定字符串A以及它的长度n，请返回最长回文子串的长度。 示例 输入："abc1234321ab",12 返回值：7知识点：字符串难度：⭐⭐⭐  题解 方法一：中心扩散 解题思路：  算法流程：  每个字符都可以尝试作为中心点看，会出现两种情况：可能是类似 aba 的字符串，也可能是类似 abba 的情况 只需要分别计算出以一个和两个字符作为中心点的子串，取出较大的长度即可 从left到right开始向两边扩散、比较，如果相等则继续扩散比较 如果不相等则剪枝，不用再继续扩散比较  计算每次比较的...

描述 题目描述 给定一棵二叉树，判断其是否是自身的镜像（即：是否对称） 示例 输入：{8,6,6,5,7,7,5} 返回值：true知识点：二叉树难度：⭐⭐⭐  题解 解题思路 因为要比较左右结点是否对称，因此可以通过BFS每次对一层的结点进行遍历并比较是否对称。 对于树的问题，往往还可以通过递归解决，相对于遍历，代码量会少很多，但没有遍历容易理解。 方法一：BFS 图解  算法流程：  1、每次往队列中按顺序，从左到右放入当前结点的左右子节点，随后进行判断。 2、每次从Queue中获取前两个元素，并比较值 3、如果又一对元素比较结果不相等，则表示不对称。 4、注意放入队列的顺序，左子结点的左...

描述 题目描述 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历） 示例 输入：{1,2,3,4,#,#,5} 返回值：[[1],[2,3],[4,5]]知识点：树，层序遍历，队列，栈难度：⭐⭐  题解 解题思路 层序遍历一般都可以通过队列或栈实现 如果是队列，每次需要加入当前层所有结点到队头，之后收集完当前层所有结点的值后，再加入下一层所有结点，直到叶子结点 方法一：队列实现 图解  算法流程：  维护一个队列，队列保存每一层所有结点 list集合收集当前层的所有结点的值 遍历所有每一层，从队列中取出当前层所有结点，并收集结果到集合 左右节点按顺序加到队尾  Java ...

描述 题目描述 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替） 示例 输入：{1,#,2} 返回值：[[1],[2]]知识点：二叉树，队列，栈，BFS难度：⭐⭐⭐  题解 解题思路 一旦看到这种有关顺序的，第一个就要想到用栈或队列实现，有这个思路才能进一步实现、优化。 比如这道题，要求 “第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印”，显然，如果能直接利用栈或队列的特性，就能实现题目要求的各种顺序了。 方法一：双栈 图解  算法流程：  维护两个栈，一个存放奇数层的节点，一个存放偶数层的节点 整型变量level表示当前遍历第几层，奇...