找规律 // 题目链接-来源：力扣（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& ...

用哈希表建立索引 // 题目链接-来源：力扣（LeetCode） 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 思路：原链表的每个 random 指针指向了一个随机节点的引用，对于我们新建的复制链表而言，这个引用的意义不大，关键是要找出这个节点对应的「序号」，我们才能在复制的链表当中按图索骥，建立一个相同的链接。给链表节点「标号」可以用哈希表完成，我们遍历原链表，对每个节点维护一个 <Node, Integer> 的映射，这个 Integer 就是节点的编号。同时遍历得到的节点值，我们拿来复制新的链表节点，记得用一个能快速索引的数据结构（可以用另一个哈希表，或者直接用一个节点数组ArrayList）帮助我们存储这些复制的节点，方便 ...

回溯，树的遍历 // 题目链接-来源：力扣（LeetCode） 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例:给定如下二叉树，以及目标和 target = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5]] 思路：回溯算法的经典应用。我们需要从根节点开始遍历整棵树，统计当前路径上的和，同时用一个列表记录当前经历过的节点，并与target作比较，如果相等，就在结果列表中记录这个列表。每个节点都有左右两个子树，利用DFS，我们可以先递归遍历左子树，但是当该子树的递归返回的时候，我们要剪除其相关信息，因为这对我们遍历右子树没有帮助，之后，我们再递归地遍历右子树。这就是「回溯」。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121 ...