Home

题目链接 有了解决jz057I的经验，我们也考虑用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。如果从small到big的序列的和大于s，则可以增大big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加small直到$\frac{1 + s}{2}$为止。这个算法的时间复杂度是O（N），空间复杂度是O（1）。当然，这题还有其他更快的用方程求解的方法，鉴于不是很通用我就不在这里写了。 class Solution: def findContinuousSequence(self, target: int) -> List[List[int]]: res = [] ...

题目链接 这个题是一个比较显然的双指针法，不赘述了。因为每个数都只会被扫描一次，所以这个算法的时间复杂度是O（N），空间复杂度是O（1）。 class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s < target: left += 1 elif s > ...

题目链接 如果我们把题目改成数组中的数字除某一个外只出现一次，其他数字出现了两次，那么我们就能用异或很方便地解决。但是在现在这种情况下，由于三个相同的数字的异或结果还是该数字，这种方法不能直接使用。尽管如此，我们还是可以沿用位运算的思路。如果一个数字出现三次，那么他的二进制位表示的每一位（0或1）也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被3整除。因此我们可以把数组中所有数字的二进制表示的每一位都加起来，如果某一位的和能被3整除，那么那个只出现一次的数字二进制表示中对应的那一位是0，否则是1。该算法的实现如下所示。输出前要先判断结果是正数还是负数，如果为正数那么第32位是0，如果是负数那么第32位是1。要注意的是，由于在python中负数...

题目链接 做jz056I的时候想起来的这个题，这题是其基础。利用异或的性质：1.任何数和0做异或运算，结果仍然是原来的数；2.任何数和其自身做异或运算，结果是0；3.异或运算满足交换律和结合律。算法实现如下。这个算法的时间复杂度是O（N），空间复杂度是O（1）。 class Solution: def singleNumber(self, nums: List[int]) -> int: return reduce(lambda x, y: x ^ y, nums)

题目链接 这个题和jz055II相似。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isBalanced(self, root: TreeNode) -> bool: def dfs(node): ...

题目链接 这个和之前做过的只出现一次的数字很像，区别在于只出现一次的数字有一个或者有两个。那我们是否可以利用解决只出现一个出现一次的数字中的方法呢，如果想要去利用，那么难点在于如何将数组分成两个子数组并且每个子数组分别包含了一个特殊的只出现一次的数字。我们还是从头到尾依此异或数组中的每个数字。由于有两个不一样的数字，得到的结果肯定不为0，也就是说这个结果数字的二进制表示中至少有一位为1。我们在结果中找到第一个为1的位置，记为第n位。现在我们以第n位是不是1为标准将原数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都为1，而第二个子数组中的每个数字的第n位都为0。由于我们分组的标准是数字中的某一位是1还是0，那么出现了两次的数字肯定会被分配到同一个子数组。因为两个相同的数字的...

题目链接 有了求二叉树的深度的经验之后来做这个问题，我们很容易想到一种思路，就是在遍历树的每个节点的时候，调用函数treeDepth得到它的左右子树的深度。如果每个节点的左右字数的深度相差都不超过1，那么按照定义它就是一颗平衡二叉树，这种思路对应的代码如1所示。这个算法的时间复杂度是O（NlogN）：在最差情况下（为“满二叉树”时），isBalanced遍历树所有节点，判断每个节点的深度需要遍历各子树的所有节点。满二叉树高度为O（logN），将满二叉树按层分为log（N+1）层，通过调用treeDepth来判断二叉树各层的节点对应子树的深度，需遍历节点数量为N x 1，$\frac{N-1}{2}$ x 2，$\frac{N-3}{4}$ x 4，$\frac{N-7}{8}$ x ...

题目链接 只要中序遍历一下二叉搜索树就容易找到，如算法1所示，当然也可以用k计数，一点点减1，直到0为止返回正确的数即可。这个算法的时间复杂度是O（N），空间复杂度是O（N），当树退化为链表时。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def kthLargest1(self, root: TreeNode, k: int) -> int: ...

题目链接 这个问题有一个直观的解决方案，我们可以先用公式n（n-1）/2求出数字0～n-1的所有数字之和，记为s1。接着求出数组中所有数字的和，记为s2。那个不在数组中的数字就是s1-s2的差。这种解法需要O（N）的时间求数组中所有数字的和。显然，该解法没有有效利用数组是递增排序的这一特点。 因为0～n-1这些数字在数组中是排序的，因此数组中开始的一些数字与它们的下标相同。也就是说，0在下标为0的位置，1在下标为1的位置，以此类推。如果不再数组中的数字记为m，那么所有比m小的数字的下标都与它们的值相同。由于m不在数组中，那么m+1处在下标为m的位置，m+2处在下标为m+1的位置，以此类推。我们发现m正好是数组中第一个数值和下标不相等的下标，因此这个问题转化成在排序数组中找出第一个值...

题目链接 既然输入的数组是排序的，那么我们就能很自然地想到用二分查找算法。在题目给的例子中，我们可以先用二分查找找到一个3，由于3可能出现多次，因此我们找到的3的左右两边可能都有3，于是在找到的3的左右两边顺序扫描，分别找出第一个3和最后一个3。因为要查找的数字在长度为n的数组中有可能出现O（N）次，所以顺序扫描的时间复杂度是O（N），这种算法的效率与直接从头到尾顺序扫描整个数组统计3出现的次数方法是一样的，显然我们可以有更加高效的算法。 我们思考如何更好地利用二分法查找算法，假设我们要统计数字k在排序数组中出现的次数。在前面的算法中，时间主要消耗在如何确定重复出现的数字的第一个k和最后一个k的位置上，有没有可能用二分查找直接找到第一个和最后一个k呢。 我们先复习如何用二分查找在...