问题输入整数数组 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]示例 2：输入：arr = [0,1,2,1], k = 1 输出：[0]限制：0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000解答一般看到求最小或者最大的k个数这种题目，会想到使用堆。题目要找出最小的k个数，那么我们可以维护一个最大堆。遍历一遍数组，如果堆中数字个数还不满k个，直接将当前数字入堆。否者，将当前数字和堆顶数字比较，如果当前数字<堆顶数字，将堆顶数字移出堆，当前数字入堆。因为python标准库只有最小堆，要特殊处理下。class Solution: def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: if k == 0: return [] heap = [] for num in arr: if len(heap) < k: heapq.heappush(heap, -num) else: if -num > heap[0]: heapq.heappop(heap) heapq.heappush(heap, -num) return [-num for num in heap]
题目给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。示例 2：输入: "cbbd" 输出: "bb"解答很容易想到使用暴力法来解决，检查字符串s所有的子串，从所有的回文子串中，找出最长的回文子串。方法很简单，代码就不写了，构造所有的子串时间复杂度是O(n^2)，检查一个子串是否是回文串的时间复杂度是O(n)，暴力法整个算法时间复杂度是O(n^3)。空间复杂度是O(1)但使用中心扩散法可以优化时间复杂度。具体思路是：我们遍历字符串中的每一个字符，将当前字符或者当前字符和下个字符的中心位置作为子串的中心位置，然后检查当前子串是否是回文字符串。如果是，那就继续向左和向右扩展，直到左边的字符不等于右边的字符，那么之前的子串就是，以当前字符串为中心的最长回文串。class Solution: def longestPalindrome(self, s: str) -> str: if len(s) < 2: return s max_len = 0 begin = 0 for i in range(0, len(s) - 1): # 求以当前字符为中心的最长回文子串 odd_begin, odd_len = self.expand_around_center(s, i, i) # 求以当前字符和下一个字符中间位置为中心的最长回文子串 even_begin, even_len = self.expand_around_center(s, i, i+1) cur_max = max(odd_len, even_len) if cur_max > max_len: begin = odd_begin if odd_len >= even_len else even_begin max_len = cur_max return s[begin : begin + max_len] def expand_around_center(self, s:str, i:int, j:int) -> (int, int): # 返回最长回文串的起始索引和长度 s_len = len(s) while i >= 0 and j < s_len: if s[i] == s[j]: i -= 1 j += 1 else: break return i + 1, j - i - 1 时间复杂度是O(n^2)，空间复杂度是O(1)。
题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶解答不难发现，爬上n级，可以由n-1再爬1级，或者由n-2再爬2级。所以爬上n级阶梯的方法数 = 爬上n-1级阶梯的方法数 + 爬上n-2级阶梯的方法数我们可以使用递归的方法来解答，但我们可以使用动态规划来优化递归问题。我们已经将原问题分解成子问题，我们可以从解子问题来得出原问题的解。class Solution: def climbStairs(self, n: int) -> int: if n <= 2: return n first, second = 1, 2 for i in range(3, n+1): third = first + second first, second = second, third return third 时间复杂度O(n)，空间复杂度O(1)。
[每天一道LeetCode] 26. 删除排序数组中的重复项
题目给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1:给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。示例 2:给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。说明:为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。你可以想象内部操作如下:// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }解答使用双指针class Solution: def removeDuplicates(self, nums: List[int]) -> int: if len(nums) <= 1: return len(nums) i, j = 0, 1 while j < len(nums): if nums[i] == nums[j]: j += 1 else: i += 1 nums[i] = nums[j] j += 1 return i + 1
题目给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。解答动态规划0 < i < len(nums)，假设f(i)是以nums[i]结尾的连续子数组的最大值那么问题就可以转换为求，max(f(0), f(1), f(2), ... f(len(nums) - 1))举个例子，[-2, 1, 3]对于第1个元素-2，以-2结尾的连续子数组是[-2]，具有最大和的连续子数组是[-2]，最大和-2，f(0) = -2对于第2个元素1，以1结尾的连续子数组是[1], [-2,1], 具有最大和的连续子数组是[1]，最大和是1，f(1) = 1对于第3个元素3，以3结尾的连续子数组是[3], [1,3], [-2,1,3]，具有最大和的连续子数组是[1,3]，最大和是4，f(2) = 4那么整个数组具有最大和的连续子数组是[1,3]，最大和是4同时，对于f(i)，f(i) = max(f(i-1) + nums[i], nums[i])，例如对于以第3个元素3结尾的连续子数组，其具有最大和的连续子数组，是以上一个元素1结尾的最大连续子数组[1]加上当前元素3，[1,3]，所以我们可以从f(0)开始，计算得到f(1)，然后再从f(1)得到f(2)，以此类推，求得所有的0 < i < len(nums)的f(i)最后得到最大和 max(f(0), f(1), f(2), ... f(len(nums) - 1))class Solution: def maxSubArray(self, nums: List[int]) -> int: if len(nums) == 0: return pre = nums[0] ans = nums[0] for i in range(1, len(nums)): cur = max(pre + nums[i], nums[i]) ans = max(ans, cur) pre = cur return ans
题目给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]解法吴彦祖的解法非常清晰明了 ::aru:thumb:: class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: if len(nums) < 3: return [] nums.sort() # 排序 ans = [] for i in range(len(nums) - 2): low, high = i + 1, len(nums) - 1 if nums[i] > 0: return ans # 相同的元素 if i > 0 and nums[i] == nums[i - 1]: continue while low < high: complement = nums[low] + nums[high] if complement == -nums[i]: ans.append([nums[i], nums[low], nums[high]]) # 跳过重复的元素 while low < high and nums[low] == nums[low + 1]: low += 1 # 跳过重复的元素 while low < high and nums[high] == nums[high - 1]: high -= 1 low += 1 high -= 1 elif complement > -nums[i]: high -= 1 else: low += 1 return ans
题目给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6解法动态编程思路：遍历每一列i，每一列可以接的水，取决于该列左右两边最大值的较小的那一个。我们使用两个数组left-max - 每一列左边的最大值 right-max - 每一列右边的最大值先从左到右遍历，得到每一列左边的最大值再从右到左遍历，得到每一列右边的最大值最后在从左到右遍历，将当前列的高度和该列左边最大值，该列右边最大值做比较，只有在当前列的高度同时小于该列左边最大值和该列右边最大值，当前列才能接水。接的水数量 = min(该列左边最大值, 该列右边最大值) - 当前列的高度class Solution: def trap(self, height: List[int]) -> int: l = len(height) left_max, right_max = [0] * l, [0] * l # 先从左到右遍历，得到每一列左边的最大值 for i in range(1, l): left_max[i] = max(height[i - 1], left_max[i - 1]) # 再从右到左遍历，得到每一列右边的最大值 for i in range(l - 2, -1, -1): right_max[i] = max(height[i + 1], right_max[i + 1]) ants = 0 for i in range(l): if height[i] < left_max[i] and height[i] < right_max[i]: ants += min(left_max[i], right_max[i]) - height[i] return ants时间复杂度O(n)，空间复杂度O(n)双指针上面的方法扫描了三次数组，而且我们发现left_max和right_max里的每个元素，我们只使用了一次。使用双指针法，同时从两个方向来遍历数组，可以在只遍历一次数组，和使用常数级的空间来完成算法。left_max - 左边的最大值 right_max - 右边的最大值 left - 从左往右处理的当前列 right - 从右往左处理的当前列上面的方法，我们已经知道每一列能接的水，由当前列的左边最大值和右边最大值中的较小值决定。当我们从左到右遍历到i列时，left_max就是left列左边的最大值，这是确定的（因为我们已经遍历了left前的列，在这个过程中，我们可以更新left_max）。但是right_max是不是left列右边的最大值？这是不确定的。当我们从右到左遍历到right，同理，right_max就是right列右边的最大值，这是确定的。但是left_max就不一定是right列的最大值。对于位置left而言，它左边最大值一定是left_max，右边最大值大于等于 right_max，这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。 所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。class Solution: def trap(self, height: List[int]) -> int: i, j = 0, len(height) - 1 left_max, right_max = 0, 0 ants = 0 while left <= right: if left_max < right_max: if height[left] < left_max: ants += left_max - height[left] else: left_max = height[left] left += 1 else: if height[right] < right_max: ants += right_max - height[right] else: right_max = height[right] right -= 1 return ants
题目给定一个二叉树，返回它的中序 遍历。示例:输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]进阶: 递归算法很简单，你可以通过迭代算法完成吗？解法思路：使用栈来解决，优点是运行速度快，缺点是比较难记忆，我在纸上画图，才捋清楚逻辑。从根节点开始，一直遍历左子树，遍历过程中，将遍历到的节点入栈，直到左子树为空，这时候就可以将栈顶的节点出栈，append到结果。 然后开始遍历栈顶节点的右子树，从右子树的根节点开始，一直遍历它的左子树，和第一步类似。 LeetCode题解里有示例图，可以结合示例图来理解。# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: result = [] s, cur = [], root while cur or len(s): while cur: s.append(cur) cur = cur.left cur = s.pop() result.append(cur.val) cur = cur.right return result递归，递归的解法比较简单。# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] elif root.left and root.right: return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) elif root.left: return self.inorderTraversal(root.left) + [root.val] elif root.right: return [root.val] + self.inorderTraversal(root.right) else: return [root.val]
题目给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1:输入: "()" 输出: true示例 2:输入: "()[]{}" 输出: true示例 3:输入: "(]" 输出: false示例 4:输入: "([)]" 输出: false示例 5:输入: "{[]}" 输出: true解题思路：利用栈，然后遍历字符串，字符如果是：')', '}', 或者']' 检查栈目前大小，如果是空，直接判断出不是有效字符串。 如果不为空，将字符串和栈顶的字符串对比，如果是对应的左字符串，将栈顶字符出栈。'(', '{', 或者'[ 将字符入栈最后检查栈的大小，如果是空，则这个字符串是有效字符串。时间复杂度O(n)，空间复杂度O(n)class Solution: def isValid(self, s: str) -> bool: d = {')': '(', '}': '{', ']': '['} l = [] # 使用列表来模拟栈 for c in s: if c in d: if len(l) == 0: # 字符是右括号，且栈为空，s不是有效字符串 return False if l[-1] == d[c]: # 检查栈顶字符，如果栈顶字符是对应的左括号，出栈 l.pop() else: return False else: l.append(c) return len(l) == 0
题目使用队列实现栈的下列操作：push(x) -- 元素 x 入栈pop() -- 移除栈顶元素top() -- 获取栈顶元素empty() -- 返回栈是否为空注意:你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。解法利用python的listclass MyStack: def __init__(self): """ Initialize your data structure here. """ self._l = [] def push(self, x: int) -> None: """ Push element x onto stack. """ self._l.append(x) def pop(self) -> int: """ Removes the element on top of the stack and returns that element. """ if not self.empty(): e = self._l.pop() return e def top(self) -> int: """ Get the top element. """ if not self.empty(): return self._l[-1] def empty(self) -> bool: """ Returns whether the stack is empty. """ return self.size() == 0 def size(self) -> int: """ Return stack size """ return len(self._l)