动态规划解决字符串组合问题 // 题目链接-来源：力扣（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 实现此规则，即可以此排序，之后连接所有数字即可。 时间复杂 ...

找规律 // 题目链接-来源：力扣（LeetCode） 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。 请写一个函数，求任意第n位对应的数字。 示例 1： 输入：n = 3输出：3 思路：此题与上题一样，需要找到数字的规律，方能在O(logn)的时间复杂度内解决，避免暴力解。我们正向思考这个问题，如果给你某个具体的数字，让你计算出这个序列中，这个数字落在第几位，应该如何计算？比如，数字 ‘10’，落在序列 “012345678910”的第 11 位（最开头数字记为第 0 位）。我们可以有以下思路，’10’ 是个「两位数」，因此其之前「一位数」的总数是确定的，（由于 ‘0’ 是第 0 个，不参与计数）有 10 - 1 = 9 个，再加上 ‘10’ 在「两位数」中排第 1 个，于是其末位就位于 2 * 1（2位数，第1个） = 2 的偏移位置，最终计算出 ‘10’ 的末位于第 11 位。现在我们回到题解，如果我们能通过 「末位位于第 11 ...

找规律 // 题目链接-来源：力扣（LeetCode） 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 示例 1： 输入：n = 12输出：5 思路：将数字转换为字符串暴力计数会超出时间限制，所以只能期待通过数学规律计算出某个数字包含的 ‘1’ 的个数。计数 ‘1’ 的难点，或者说计数任何一个数码的难点在于，数码在不同数字范围内出现的「密度」不同，例如，对于11 ~ 19，每个数字都至少出现一个 ‘1’ ，而21 ~ 29，则只出现了1次1，使得我们很难按序去计数。我们换个角度思考，如果数字大小已经确定了，我们是否可以确定地，统计其每一个十进制位的 ‘1’ 的个数，然后累加呢？答案是肯定的。例如，我们考察十位，任取一个数，XX3Y，那么这个数字个位出现 ‘1’ 的数字，从 0010 ~ XX19，主要取决于 XX 的大小。而最终有多少次，还取决于这位数字本身和Y的大小，由于是 ‘3’ ，我们知道肯定会经过 ‘1’，所以需要多计数一次。最终，我们可以确定如下规则 ...

动态规划解决子列和问题 // 题目链接-来源：力扣（LeetCode） 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 思路：我们希望在O(n)的复杂度内完成最大值的计算，那么就需要在每一次考察新元素的时候充分利用已有元素信息，自然想到动态规划。记dp[i]表示「截至第i个元素，数组中出现的子数组和的最大值」，这样我们每次同步更新一个 dp[i] 的最大值，直到数组末尾，代表的意义就是题目所要求的结果。递推规则：考察dp[i - 1]是否大于0。若 dp[i - 1] <= 0，证明前驱的子数组对我们增大子数组和没有帮助，我们就舍弃之，只留下 nums[i] 的值供后续子数组参考；否则，我们留下 dp[i - 1] 的值，加上 nums[i] 的值，构成当前位置的 dp[i]。每次更新 dp，维护一个最大值，最后返回即可。时间复杂度：O(n ...

用堆高效返回中位数 // 题目链接-来源：力扣（LeetCode） 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。示例 1： 输入：[“MedianFinder”,”addNum”,”addNum”,”findMedian”,”addNum”,”findMedian”][[],[1],[2],[],[3],[]]输出：[null,null,null,1.50000,null,2.00000] 思路：如果要快速返回数据的最大值或者最小值，显然应该用 最大堆 或者 最小堆。本题需要中位数，我们思考能否在堆的中间「剖开」一个接口，让我们能够像 ...

用快速排序解决「不要求有序」的最小 k 个树 // 题目链接-来源：力扣（LeetCode） 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： 输入：arr = [3,2,1], k = 2输出：[1,2] 或者 [2,1] 思路：找 最小/最大 的 k 个数，习惯性地可以想到 最大堆 / 最小堆 来解决。复杂度为 O(nlogk)。当然，注意到本题的条件，不要求按顺序输出结果，那么我们可以用一种更聪明的办法，那就是借助「快速排序」。快速排序的每一轮排序当中，我们会确定一个 pivot ，在这个 pivot 左侧的元素都比它要小，右侧的元素都比它要大。那么我们只要在某轮排序中，发现 pivot 的左侧元素刚好为 k 个，那么这 k 个元素就是我们所要寻找的结果。我们快速排序的目标不再是真的「排序」，而是想办法让 pivot 左侧恰好有 k 个元素。细节：快排的划分策略，我们采用双指针法，分别从数组开头和结尾查看元素，当前指针元素大于 pivo ...

用摩尔投票法寻找数组中数量超过一半的成员 // 题目链接-来源：力扣（LeetCode）数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 思路：题目给出数组中存在一个出现次数超过一半的成员，那么我们可以用「摩尔投票法」找出他。「摩尔投票法」核心思路就是，遍历数组中的成员，出现相同的成员会累计，而不同的成员会抵消。那么只要确保有数量超过一半的某种成员，便可「活到最后」，拥有不为0的计数，这便是我们要找的那个成员。具体实现当中，我们需要一个变量 prev 存储当前数量占优的那个元素，初始为 nums[0]，还需要用 votes 记录当前占优元素的「票数」，或者说「存活个数」。当 votes 变化到0时，我们认为当前的「优势元素」prev 可能发生了变化，于是取当前访问到的数组成员为新的 「优势元素」。遇到与「优势元素」相同的元素则票数增加，反之减少。这样经过完整遍历后，数组中超过一半数量的那个成员一定能活到最后。时间复杂度：O(n ...

字符的全排列 // 题目链接-来源：力扣（LeetCode）输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例: 输入：s = “abc”输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”] 思路：求全排列，容易联想到 DFS 以及回溯算法。输入的字符构成一个集合，从集合中依次取出元素作为开始，进行DFS，剪枝：忽略遍历过的字符。对于输入字符的集合，我们可以用一个 StringBuilder 变量 res 来保存，这样我们可以按照索引指针每次「取」一个字符，同时也可以从 res 中删除该字符，完成回溯后再加回它，相当方便。取字符可以用一个 for 循环依次获取。为了防止结果出现重复，我们在 for 循环的同时维护一个 visited 集合，如果有相同字符，则会出现冲突，我们跳过该字符即可。在每一层的 DFS 当中，我们还需要一个 StringBuilder 变量 construct 来收集当前生成的字符串。相对应地，完成回溯后，要把当前收集的这个字符删除掉。DFS 跳出的条件就是 ...

二叉搜索树的中序遍历 // 题目链接-来源：力扣（LeetCode） 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 思路：要将BST的节点从小到大以循环双向链表串起来。注意BST的节点从小到大访问生成的序列即是中序遍历，所以我们可以以中序遍历为模板解决此题。我们需要用两个变量分别记录 中序遍历的当前节点 和 前驱节点。对于递归做法，用全局变量会比较方便，对于非递归做法，则用普通变量即可。我采用的是非递归做法，事实上，递归做法的代码会更加简洁明了。在遍历的同时调整 当前节点 和 前驱节点 的指针。注意，由于是循环链表，遍历完成后还要记得链接头节点和末尾节点。 时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617181920212223242526272829303132333435class Solution { public Node treeToDoublyList(Node root) { Stack<Node& ...