计算树的深度 // 题目链接-来源：力扣（LeetCode） 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。 例如： 给定二叉树 [3,9,20,null,null,15,7]， 3 / 9 20 / 15 7返回它的最大深度 3 。 思路：寻找深度，即可利用「深度优先搜索」DFS，递归地返回 「两子树深度最大值」+ 1 的结果即可。递归跳出条件是 节点为 null 时返回 0。对于树而言，DFS 即 先序遍历、中序遍历、后序遍历中的任意一种。时间复杂度：O(n)空间复杂度：O(n) 实现：12345678class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Integer.max(maxDepth(root. ...

二分法实现数组特定元素查找 // 题目链接-来源：力扣（LeetCode）一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 示例 1: 输入: [0,1,3]输出: 2 思路：我们可以很容易地将数组分为两部分，一部分是「缺失元素之前的部分」，该部分的特点是数组下标值即等于元素值；另一部分是「缺失元素之后的部分」，该部分的特点是数组下标值小于元素值。我们只要找到「缺失元素之后的第一个元素」，将其减去 1 即可得到所需结果。借鉴前一题 helper() 函数的二分思路，二分缩小左边界的条件应该是 nums[m] = m，这样我们就能找到满足 nums[m] != m 的第一个元素。时间复杂度：O(logn)空间复杂度：O(1) 实现：1234567891011121314class Solution { public int missingNumber(int[] nums) { int left = 0, r ...

用中序遍历访问BST // 题目链接-来源：力扣（LeetCode）给定一棵二叉搜索树，请找出其中第k大的节点。 示例 1: 输入: root = [3,1,4,null,2], k = 1 3 / 1 4   2输出: 4 思路：由于我们无法提前知道二叉树的节点总数，因此只能通过遍历的方式计数访问其第 k 个节点。BST 的中序序列能按从小到大的顺序输出节点值，因此我们在中序遍历的基础上，增加一个计数变量 k 作为跳出条件即可。这里展示非递归实现的思路。时间复杂度：O(n)空间复杂度：O(n) 实现：123456789101112131415161718class Solution { public int kthLargest(TreeNode root, int k) { TreeNode cur = root; Stack<TreeNode> s = new Stack<>(); while (k != 0) { ...

双指针法遍历顺序数组 // 题目链接-来源：力扣（LeetCode） 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8输出: 2 思路：我们可以很容易地想到遍历整个数组，计数 target 出现的次数，只需 O(n) 的复杂度。但是注意到数组有序，有序必定想到二分法，降低复杂度至 O(logn)。在数组中二分地找到任意一个与 target 相等的值是容易的，但我们需要统计次数，如果在找到某个 target 以后，最坏情况下整个数组相等且等于 target，我们又回到了 O(n) 复杂度。也就是说，在找到 target 确定其存在以后，我们还需要二分地找到其两侧边界。这里我们可以做一个巧妙的处理，用一个辅助函数 helper() 执行二分，我们将二分缩小左边界的条件从 target > nums[m] 改为 target >= nums[m]（nums[m] 为当前二分区间中点值），这样我们二分停止处的点就是「大于 target 的第一个值」。这样一来，target ...

双指针法快速查找链表的公共节点 // 题目链接-来源：力扣（LeetCode） 输入两个链表，找出它们的第一个公共节点。 示例 1： 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Reference of the node with value = 8输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 思路：考虑 A 链表长度为 a， B 链表长度为 b，两表公共部分长度为 c，（0 <= c <= a, b）。在不知道 a 和 b 的情况下，我们可以确定 a + (b - c) = b + (a - c)。也就是说，我们用一个指针遍历一遍 a 链表，再从 ...

// 题目链接-来源：力扣（LeetCode） 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4]输出: 5 思路：有一个基础知识：排序算法的本质就是不停寻找数组中的逆序对，然后一个个交换消灭之。那么我们只要用一个复杂度较低 O(nlong) 且每一步排序交换一组逆序对的排序算法为载体，每次交换时计数一次逆序对，最终返回值即是我们需要的逆序对的总数。这里自然想到用「归并排序」为载体（注意，O(nlogn)复杂度的排序方法很多，堆排序每次维护最小堆时的交换步骤也可用来计数；快速排序由于其无序性，每次划分可能会一次性消灭很多对逆序对，不方便统计）。现在我们仔细思考，每次「交换」操作，跟逆序对的具体数量关系如何。首先，某一轮归并排序的输入是两个有序的数组，记为 A[]，B[]。指针 pA 指向 A[] 开头， pB 指向 B[] 开头。当我们进行若干次归并以后，pA = i，pB = j。假设 A[i] <= B[j] ，则我们要添加 A ...

用哈希表辅助查找 // 题目链接-来源：力扣（LeetCode） 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。 示例: s = “abaccdeff”返回 “b” s = “”返回 “ “ 思路：遍历字符串，将出现过的字符存入哈希表中，并配以一个 boolean 状态值记录其是否只出现过一次。再次出现以后就将这个值改为 false。完成以后我们再次遍历字符串，找到键值为 true 的字符返回即可。否则返回 ‘ ‘。进一步优化：若语言支持有序哈希表，则第二步只需遍历哈希表。时间复杂度：O(n)空间复杂度：O(1) 实现：123456789101112131415161718192021class Solution { public char firstUniqChar(String s) { int n = s.length(); Map<Character, Boolean> map = new HashMap<>(); ...

用最小堆或动态规划解决数据的滚动添加维护 // 题目链接-来源：力扣（LeetCode） 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 示例: 输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明:   1 是丑数。n 不超过1690。 思路：基本思路是，丑数 能且仅能通过已有的丑数继续乘上 2、3、5 质因子生成。于是我们只要在获得一个新的丑数时，将其分别乘上 2、3、5 质因子然后加入后续的集合当中，就能保证不漏过任何一个丑数。添加丑数时，从该集合当中取出 最小值即可。容易想到，用 最小堆实现这个集合可以获得平均每次操作的时间复杂度 O(logn)。这个方法的瑕疵在于，我们每取出 1 个丑数时，就要新添加 3 个丑数，等于每次额外添加了 2 个数，所以当进行 n 次操作后，我们会浪费 2n 的存储空间。我们考虑用动态规划来实现。首先明确这样一个前提：每个出现过的丑数，可以拿来乘以 2、3、5 生成 3 个新的丑数，也就是说， ...

字符串的非重复子串 // 题目链接-来源：力扣（LeetCode） 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 思路：子串类问题可以用双指针法降低一层复杂度。一个前指针 start 指向子串的开始，一个后指针 i 指向子串末端。用一个 max 更新子串最大长度，用一个哈希表记录 i 收集到的字符、下标 + 1键值对。当发生冲突时，若 start 的位置靠前，就移动到到冲突字符的键值处，否则不动，同时更新键值。注意，为什么 front 靠后时要保持不动？因为我们每次移动 start 的时候，并没有删除旧的键值对，也就是说，欲跳转前往的键值可能并不在当前子串中，因此我们要锁定当前 start 的位置让其只能前进不能后退，以免跳转到一个不在当前子串中的位置。待 end 遍历整个字符串，输出 max 即可获得长度。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314class Solution  ...

二维动态规划 // 题目链接-来源：力扣（LeetCode） 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 示例 1: 输入:[  [1,3,1],  [1,5,1],  [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 思路：由于题目限定了前进方向，我们的工作量大大简化。建立一个二维数组 dp[i][j] 存储当前第 i 行第 j 列的格子可能取得的最高价值礼物，那么递推式很容易给出：dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]细节上，单独处理 dp[0][j] 和 dp[i][0] 防止越界即可。时间复杂度：O(n²)空间复杂度：O(n²) 如果直接修改原数组的话，则可以达到O(1)复杂度 实现：123456789101112131415161718192021clas ...