用单调队列解决滑动窗口最大值 // 题目链接-来源：力扣（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)
...

计算树的深度 // 题目链接-来源：力扣（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 ...