Python|Leetcode刷题日寄Part03

交易中获取的最大利润。如果你不能获取任何利润，返回0。 在这道题目中，我们需要找到一个最佳的买入时机和一个最佳的卖出时机，使得卖出时的价格比买入时的价格高，并且获取的利润最大。 我们可以使用一个变量 minPrice 来记录当前找到的最小的价格，同时使用另一个变量 maxProfit 来记录当前找到的最大利润。遍历整个价格列表，在遍历过程中，如果遇到了更小的价格，就更新 minPrice，如果当前价格减去最小价格比之前找到的最大利润更大，那么就更新 maxProfit。 下面是 Python 中的具体实现代码： ```python def maxProfit(prices): if not prices: return 0 minPrice = prices[0] maxProfit = 0 for price in prices: if price < minPrice: minPrice = price elif price - minPrice > maxProfit: maxProfit = price - minPrice return maxProfit ``` 02：合并两个有序数组 题目描述： 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。 这道题目可以使用双指针的方法进行求解。我们从 nums1 和 nums2 的末尾开始比较两个数组的元素大小，然后将较大的元素插入到 nums1 的末尾。最后如果 nums2 中还有剩余的元素，那么就将它们拷贝到 nums1 的前面。 下面是 Python 中的具体实现代码： ```python def merge(nums1, m, nums2, n): i = m - 1 j = n - 1 k = m + n - 1 while i >= 0 and j >= 0: if nums1[i] > nums2[j]: nums1[k] = nums1[i] i -= 1 else: nums1[k] = nums2[j] j -= 1 k -= 1 if j >= 0: nums1[:j+1] = nums2[:j+1] ``` 03：三数之和 题目描述： 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 。请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 这道题目也可以使用双指针的方法进行求解。我们首先对 nums 进行排序，然后固定一个数 i，使用两个指针 left 和 right 来扫描剩余的数。如果三个数的和等于 0，我们就记录这个三元组，然后继续移动 left 和 right 来寻找下一个三元组。如果三个数的和小于 0，说明需要增加一个较大的数，所以将 left 向右移动。如果三个数的和大于 0，说明需要减少一个较大的数，所以将 right 向左移动。 下面是 Python 中的具体实现代码： ```python def threeSum(nums): nums.sort() res = [] for i in range(len(nums)-2): if i > 0 and nums[i] == nums[i-1]: continue left = i + 1 right = len(nums) - 1 while left < right: s = nums[i] + nums[left] + nums[right] if s < 0: left += 1 elif s > 0: right -= 1 else: res.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left+1]: left += 1 while left < right and nums[right] == nums[right-1]: right -= 1 left += 1 right -= 1 return res ``` 04：找出字符串中第一个匹配项的下标 题目描述： 实现 strStr() 函数。 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。 这道题目可以使用字符串匹配算法进行求解。最简单的方法是暴力枚举，对于 haystack 中的每个位置，都判断能否匹配 needle，时间复杂度为 O(m*n)。另外还有一些高级的字符串匹配算法，例如 KMP、Boyer-Moore 等，时间复杂度可以做到 O(m+n)。 下面是 Python 中暴力枚举的具体实现代码： ```python def strStr(haystack, needle): n = len(haystack) m = len(needle) for i in range(n-m+1): if haystack[i:i+m] == needle: return i return -1 ``` 05：全排列 题目描述： 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 这道题目可以使用递归的方法进行求解。我们可以维护一个已经选择好的前缀，然后递归地选择剩余的元素。具体来说，我们可以依次枚举每个元素作为前缀，然后递归地选择剩余的元素，直到所有元素都被选择完毕，这时就可以将这个排列加入到结果中。 下面是 Python 中的具体实现代码： ```python def permute(nums): res = [] def dfs(path, used): if len(path) == len(nums): res.append(path[:]) return for num in nums: if not used[num]: path.append(num) used[num] = True dfs(path, used) path.pop() used[num] = False dfs([], [False]*len(nums)) return res ``` 06：用队列实现栈 题目描述： 使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 注意: 你只能使用队列的基本操作-- 也就是push to back，peek/pop from front，size 和is empty这些操作是合法的。 你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 ，只要是标准的队列操作即可。 这道题目可以使用两个队列来实现栈的操作。具体来说，我们在入栈时，将元素添加到一个空队列中，然后将原先的队列中的元素依次放到这个新队列中，这样最后得到的队列顺序就和栈的顺序相同了。出栈、获取栈顶元素等操作可以直接在这个新队列上进行。 下面是 Python 中的具体实现代码： ```python from collections import deque class MyStack: def __init__(self): self.queue1 = deque() self.queue2 = deque() def push(self, x: int) -> None: self.queue2.append(x) while self.queue1: self.queue2.append(self.queue1.popleft()) self.queue1, self.queue2 = self.queue2, self.queue1 def pop(self) -> int: return self.queue1.popleft() def top(self) -> int: return self.queue1[0] def empty(self) -> bool: return not self.queue1 ``` 07：加一 题目描述： 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 这道题目可以直接模拟加法的过程。我们从末尾开始遍历数组，依次将每一位加 1，如果有进位，就继续向前处理。如果最高位还有进位，那么就需要在数组的前面插入一个 1。 下面是 Python 中的具体实现代码： ```python def plusOne(digits): for i in range(len(digits)-1, -1, -1): digits[i] += 1 if digits[i] < 10: return digits digits[i] = 0 digits.insert(0, 1) return digits ``` 08：电话号码的字母组合 题目描述： 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 这道题目可以使用回溯算法进行求解。我们可以维护一个已经选择好的前缀，然后递归地选择剩余的字母。具体来说，我们首先将数字对应的字母列表存储在一个字典中，然后对于每个数字，依次遍历字母列表，将字母加入到前缀中，然后递归地处理剩余的数字，直到所有数字都被处理完毕，这时就可以将这个排列加入到结果中。 下面是 Python 中的具体实现代码： ```python def letterCombinations(digits): if not digits: return [] letters = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' } res = [] def dfs(path, idx): if idx == len(digits): res.append(path[:]) return for letter in letters[digits[idx]]: path.append(letter) dfs(path, idx+1) path.pop() dfs([], 0) return res ``` 09：盛最多水的容器 题目描述： 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为(i, ai) 和 (i, 0)。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 这道题目可以使用双指针的方法进行求解。我们可以使用两个指针 left 和 right 分别指向数组的左右两端，然后计算当前组成容器的面积，将面积与之前的最大面积进行比较，并将较大的面积保存下来。然后我们移动两个指针中高度较小的那个指针，直到两个指针相遇为止。 下面是 Python 中的具体实现代码： ```python def maxArea(height): left = 0 right = len(height) - 1 res = 0 while left < right: area = min(height[left], height[right]) * (right-left) res = max(res, area) if height[left] < height[right]: left += 1 else: right -= 1 return res ``` 10：二叉树的最大深度 题目描述： 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 这道题目可以使用递归的方法进行求解。我们可以分别递归处理左子树和右子树，并返回左子树和右子树中的最大深度加上 1，作为当前子树的最大深度。叶子节点的深度为 1。 下面是 Python 中的具体实现代码： ```python class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def maxDepth(root): if not root: return 0 return 1 + max(maxDepth(root.left), maxDepth(root.right)) ```