用中序遍历访问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 ...

动态规划解决字符串组合问题 // 题目链接-来源：力扣（LeetCode） 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 示例 1: 输入: 12258输出: 5解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi” 思路：显然，对于一位数字，确定地对应’0’~’9’中的某一个，所以只有 1 种翻译。我们再将它之前的数字组合考虑，如果组合而成的数字大于 ‘25’，显然是无法翻译的，也就是 0 种；反之，我们又能多出 1 种翻译。于是我们可以动态规划，以 dp[i]存储截至当前第 i 位数字，共有几种翻译，根据乘法原理，我们只翻译 1 位数字的话，那就有 dp[i - 1] * 1 种翻译；若翻译 2 位数字，就有 dp[i - 2] * 0 （超过25） 或者 dp[i - 2] * 1 （不超过25）种翻译，于是 dp[i] 的翻译种 ...

巧妙定义排序规则，以处理复杂的字符判定 // 题目链接-来源：力扣（LeetCode） 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2]输出: “102” 示例 2: 输入: [3,30,34,5,9]输出: “3033459” 思路：如果此题用类似 DFS 的方法暴力展开，会达到 O(n!) 的复杂度。我们思考，如示例 2，’30’ 排在 ‘3’ 的前面，而 ‘3’ 又排在 ‘34’ 前面。那么说明存在一种规则，使得在这个规则下， ‘30’「小于」’3’「小于」’34’。我们只要能定义出这种规则，便可以利用任意一种 O(nlogn) 的排序方法解决此题。题目要求构造出最小的数，显然，这样的数，我们应该让「较小」元素放到头部，而「较大」元素放到尾部。那么比较两个数之间的大小，最直观的方法就是，我们比较其组合后的数字大小，比如 数字 X 和数字 Y，若 XY < YX，我们称 X 「小于」 Y。于是只要定义一个比较器 Comparator 实现此规则，即可以此排序，之后连接所有数字即可。 时间复杂 ...