Python|Leetcode刷题日寄Part02

Python|Leetcode刷题日寄Part01 01：探索插入位置02：整数反转03：在排序数组中查找元素的第一个和最后一个位置04：合并两个有序链表05：寻找两个正序数组的中位数06：最大子数组和07：最长公共前缀08：罗马数字转整数09：移动零10：爬楼梯 01：探索插入位置 题目描述： 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例： 输入: nums = [1,3,5,6], target = 5 输出: 2 题解： # 二分查找 class Solution: def searchInsert(self, nums: List[int], target: int) - int: n = len(nums) if nums[-1] target: return n left = 0 right = n - 1 while left right: mid = int((left + right) / 2) if nums[mid] target: left = mid + 1 else: right = mid return left 02：整数反转 题目描述： 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [?2^31, 2^31 ? 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）。 示例： 输入：x = 123 输出：321 题解： # 按位运算 class Solution: def reverse(self, x: int) - int: y, res = abs(x), 0 boundry = (131)-1 if x0 else 131 while y != 0: res = res * 10 + y % 10 if res boundry: return 0 y //= 10 return res if x0 else -res 03：在排序数组中查找元素的第一个和最后一个位置 题目描述： 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例： 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 题解： # 二分查找 class Solution: def searchRange(self, nums: List[int], target: int) - List[int]: def binarySearch(nums: List[int], target: int) - int: left, right = 0, len(nums) - 1 while left = right: mid = (left + right) // 2 if nums[mid] = target: right = mid - 1 else: left = mid + 1 return left leftBorder = binarySearch(nums, target) rightBorder = binarySearch(nums, target + 1) - 1 if leftBorder == len(nums) or nums[leftBorder] != target: return [-1, -1] return [leftBorder, rightBorder] 04：合并两个有序链表 题目描述： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 题解： # 递归 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]: if not list1: return list2 if not list2: return list1 if list1.val = list2.val: list1.next = self.mergeTwoLists(list1.next, list2) return list1 else: list2.next = self.mergeTwoLists(list1, list2.next) return list2 05：寻找两个正序数组的中位数 题目描述： 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。 示例： 输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组为 [1,2,3] ，中位数 2 题解： # 二分查找 class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float: # 确保 nums1 比 nums2 长 if len(nums1) len(nums2): nums1, nums2 = nums2, nums1 n1, n2 = len(nums1), len(nums2) # 假设理想中位数为 x # 对于第 1 个序列，mid1 左边都小于 x，右边都大于 x # 对于第 2 个序列，mid2 左边都小于 x，右边都大于 x left, right, mid = 0, n1, (n1 + n2 + 1) // 2 mid1 = (left + right) // 2 mid2 = mid - mid1 # 更新二分查找条件 while left right: if mid1 n1 and nums2[mid2 - 1] nums1[mid1]: left = mid1 + 1 else: right = mid1 mid1 = (left + right) // 2 mid2 = mid - mid1 # 返回情况 if mid1 == 0: max_left = nums2[mid2 - 1] elif mid2 == 0: max_left = nums1[mid1 - 1] else: max_left = max(nums1[mid1 - 1], nums2[mid2 - 1]) # 总长度为偶数 if (n1 + n2) % 2 == 1: return max_left if mid1 == n1: min_right = nums2[mid2] elif mid2 == n2: min_right = nums1[mid1] else: min_right = min(nums1[mid1], nums2[mid2]) return (max_left + min_right) / 2 06：最大子数组和 题目描述： 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。 示例： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 题解： # 动态规划 class Solution: def maxSubArray(self, nums: List[int]) - int: n = len(nums) if n == 0: return 0 dp = [0 for _ in range(n)] dp[0] = nums[0] for i in range(1, n): dp[i] = max(dp[i - 1] + nums[i], nums[i]) return max(dp) 07：最长公共前缀 题目描述： 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例： 输入：strs = ["flower","flow","flight"] 输出："fl" 题解： # min() max() 根据ASCII码逐位对比 class Solution: def longestCommonPrefix(self, strs: List[str]) - str: if not strs: return '' str0 = min(strs) str1 = max(strs) for i in range(len(str0)): if str0[i] != str1[i]: return str0[:i] return str0 08：罗马数字转整数 题目描述： 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符数值I1V5X10L50C100D500M1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。 示例： 输入: s = "III" 输出: 3 题解： # 哈希表 class Solution: def romanToInt(self, s: str) - int: dic = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} n = len(s) num = 0 for i in range(n - 1): if dic[s[i]] dic[s[i + 1]]: num -= dic[s[i]] else: num += dic[s[i]] return num + dic[s[-1]] 09：移动零 题目描述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。 示例： 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 题解： # 双指针 class Solution: def moveZeroes(self, nums: List[int]) - None: """ Do not return anything, modify nums in-place instead. """ if not nums: return 0 count = 0 for i in range(len(nums)): if nums[i]: nums[count] = nums[i] count += 1 for i in range(count, len(nums)): nums[i] = 0 10：爬楼梯 题目描述： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例： 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1 + 12 题解： # 动态规划，空间优化 class Solution: def climbStairs(self, n: int) - int: a = b = 1 for i in range(2, n+1): c = a + b a = b b = c return b