分组异或，用异或运算筛选元素 // 题目链接-来源：力扣（LeetCode） 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例 1： 输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1] 思路：我们可以遍历数组，将所有数字都放到哈希表当中，而出现冲突时则删除。目标数字只出现一次，而其他数字重复出现后即删除。余下的数字即是我们需要的数字。但是这样的话空间复杂度为 O(n)，不符合题目要求。信号处理中，位运算常常用来帮助我们进行信号的筛选。我们考虑进行位运算中的「异或」（xor）运算，「异或」具有一个优良性质：进行「异或」运算的元素中，如果有相同的元素成对出现，它们会互相抵消，对其余元素没有任何影响。而本题中，无关元素恰好都是出现2次，成对出现。于是我们只要考虑将数组中所有元素依次进行「异或」操作，就能过滤掉它们，留下我们需要的两个数字的异或结果，记为 xor，这两个数字我们记为 a 和 b。接下来我们考虑如何分离这对数字。由于 xor 存储了 a ^ ...

通过深度判断二叉树是否平衡 // 题目链接-来源：力扣（LeetCode） 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / 9 20 / 15 7返回 true 。 思路：借鉴上一题的方法，我们利用 DFS 就能递归地获取到二叉树的每个子树深度。但是对于某个节点来说，除了子树深度的信息，我们还需要知道子树中是否已经发生了「不平衡」。这里我们可以巧妙地在返回值中增加这个信息，若没有不平衡，正常返回子树最大深度 + 1；否则，返回一个负值告诉上层节点已经出现了不平衡。这样我们就用一个变量同时传递了子树深度和是否存在不平衡的两条信息。 时间复杂度：O(n)空间复杂度：O(n) 实现：12345678910111213141516171819class Solution { public boolean isBalanced(TreeNode root)
...

计算树的深度 // 题目链接-来源：力扣（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 个新的丑数，也就是说， ...