二维动态规划。 // 题目链接-来源：力扣（LeetCode） 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1: 输入: 1输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667] 思路：暴力解法会导致 O(6^n) 的复杂度。因此必须另寻他解。考虑利用动态规划降低复杂度。对于某一个骰子，其结果很简单，单次点数 1 ~ 6 都是 1/6 概率。我们需要掷 n 次骰子，对于第 n 次投掷，总点数为 k 的概率记为 f(n, k)，则有 f(n, k) = f(1, 6) * f(n - 1, k - 6) + f(1, 5) * f(n - 1, k - 5) + … + f(1, 1) * f(n - 1, k - 1)，其中 p(1, x) 即为单词投掷出 x 点的概率，恒等于 1/6。于是有f(n, k) = 1&# ...

用单调队列实现队列最大值的快速查找 // 题目链接-来源：力扣（LeetCode） 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 若队列为空，pop_front 和 max_value 需要返回 -1 示例 1： 输入:[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”][[],[1],[2],[],[],[]]输出: [null,null,null,2,1,2] 思路：受前一题启发，前一题的数据工作集是一个「滑动窗口」，而本题的工作集是一个「队列」，较新的元素在一侧，而较旧的元素在另一侧，结构上而言是相似的，因此可以直接套用前一题的思路。max_value 其实就相当于前一题的「滑动窗口」中的最大值，而其余功能都是队列基本的功能。于是我们只需定义一个主队列存储元素，再定义一个「单调队列」辅助查找最大值即可。时间复杂度：O(n)空间复杂度：O(n) 实现：123456 ...

用单调队列解决滑动窗口最大值 // 题目链接-来源：力扣（LeetCode） 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7]解释: 滑动窗口的位置 最大值 [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 思路：考虑一个窗口内某个数是当前的最大值，我们用某种办法记录它。这个最大值的「有效时间」截止以下两个条件满足任意一个： 1有更大的数字加入窗口，则该数称为新的「最大值」 2这个数字被移出窗口这个特性非常类似「双端队列」，但是我们 ...

简单字符串拼接 // 题目链接-来源：力扣（LeetCode） 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。 示例 1： 输入: s = “abcdefg”, k = 2输出: “cdefgab” 思路：设字符串长度为 n，只要拼接其两段子串 substring(0, k) 与 substring(k, n)即可 时间复杂度：O(n)空间复杂度：O(n) 实现：12345class Solution { public String reverseLeftWords(String s, int n) { return s.substring(n, s.length()) + s.substring(0, n); }}

// 题目链接-来源：力扣（LeetCode） 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。 示例 1： 输入: “the sky is blue”输出: “blue is sky the” 思路：用一前一后两个指针 left 和 right 遍历字符串。同时用 StringBuilder 将收集到的单词（即 left 与 right 形成的子串）插入头部，并用空格隔开即可。对于 left，我们要为其安排一个合适的停止位置（某个单词的起始位置），之后 right 从 left 出发，达到一个合适的停止位置（该单词的结束位置）。可以通过如下规则安排指针的行动， left 和 right 初始化为 0。 当前为空格，left 和 right 同时前进。 当前为字符，left 停止，right 前进直到碰见空格。复制 left 和 right 间的子串进入 StringBuilder 的开头处。细节处理，原字符串第一个单词前（生成的 ...

双指针提升有序数组查找效率 // 题目链接-来源：力扣（LeetCode） 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 示例 1： 输入：target = 9输出：[[2,3,4],[4,5]] 思路：依然使用双指针法。不同的是，本题中我们并没有一个确切的数组大小，我们需要将其考虑为一个「滑动窗口」。由于我们的目标是连续正整数序列，即便我们的数组是虚拟的，我们只需根据前后指针的大小，用等差数列和公式 sum = (a1 + an) * n / 2 （对于本题，即为 sum = (left + right) * (right - left + 1) / 2）即可求出和。 若 sum < target，则我们需扩大窗口，right 右移即可。 若 sum > target，则缩小窗口，left 右移即可 若 sum = target，窗口整体需要右移，由于 left < right，右移结果 ...

双指针提升有序数组查找效率 // 题目链接-来源：力扣（LeetCode） 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。 示例 1： 输入：nums = [2,7,11,15], target = 9输出：[2,7] 或者 [7,2] 思路：使用两个指针，一个从数组头部向后遍历，一个从数组尾部向前遍历。二者指向的元素之和，可以与 target 作比较。由于数组本身有序，当和较大时，尾指针左移可使和变小，反之头指针右移可使和变大。就这样慢慢逼近 target。 时间复杂度：O(n)空间复杂度：O(1) 实现：12345678910111213141516class Solution { public int[] twoSum(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { ...

用位运算筛选数组中出现次数不一样的数字 // 题目链接-来源：力扣（LeetCode） 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 示例 1： 输入：nums = [3,4,3,3]输出：4 思路：首先，与前一题类似，我们很直观地可以用哈希表记录数字遍历的次数。第二轮遍历的时候判断哈希表对应的键值是否为1即可找到该数字。如果要将存储空间降到 O(1)，可以采用与位运算类似的思路，不过由于无关数字出现了奇数次，无法使用异或运算抵消的思路，我们需要考虑更一般的解法。我们仍然将每一个数字视为一个 32 位的二进制数。则对于任意一个出现了 3 次的数字，其每一个位上的数字都出现了 3 次，’0’ 出现 3 次总和还是 ‘0’，而 ‘1’ 出现 3 次后总和为 ‘3’，对 ‘3’ 求余结果均为 0。并且这种结果对所有数字累加后的结果也是成立的，我们只要遍历数组，将每个数字都按二进制位统计该位上 ‘1’ 的个数，最后分别对 ‘3’ 求余，最后拼接成的结果即为「只出现1次的数」的二进制表达。 时间复杂度：O(n)空间复杂度：O ...

分组异或，用异或运算筛选元素 // 题目链接-来源：力扣（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)
...