高频-临时抱佛脚篇

215. 数组中的第K个最大元素 - 力扣LeetCodeclass Solution: def findKthLargest(self, nums: List[int], k: int) - int: # 用堆确实可以快速解决但是时间复杂度是在nlogn min_heap [] for i in range(len(nums)): heapq.heappush(min_heap,(nums[i],i)) if len(min_heap)k: heapq.heappop(min_heap) return min_heap[0][0]class Solution: def findKthLargest(self, nums: List[int], k: int) - int: # 快速排序可以达到n的时间复杂度 # 快速排序其实是快速选择出正确的位置然后左侧和右侧分别递归是因为递归导致了n的时间复杂度 # 但是我们这里其实可以扔了左右递归答案再那一侧就去那一侧 target len(nums) - k # 我们想要的元素的下标 def quickselect(left:int, right:int) - int: if leftright: return nums[left] pi random.randint(left,right) nums[pi],nums[right] nums[right],nums[pi] p nums[right] min_left left # 小于等于边界 # 如果只有一个指针会在重复元素上超时 for i in range(left,right): if nums[i]p: nums[i],nums[min_left] nums[min_left],nums[i] min_left 1 nums[min_left],nums[right] nums[right],nums[min_left] if min_lefttarget: return nums[min_left] elif min_lefttarget: return quickselect(left,min_left-1) else: return quickselect(min_left1,right) return quickselect(0,len(nums)-1)class Solution: def findKthLargest(self, nums: List[int], k: int) - int: # 快速排序可以达到n的时间复杂度 # 快速排序其实是快速选择出正确的位置然后左侧和右侧分别递归是因为递归导致了n的时间复杂度 # 但是我们这里其实可以扔了左右递归答案再那一侧就去那一侧 target len(nums) - k # 我们想要的元素的下标 def quickselect(left:int, right:int) - int: if leftright: return nums[left] pi random.randint(left,right) nums[pi],nums[right] nums[right],nums[pi] p nums[right] i left li left # 小于的右边界开区间 ri right # 大于的左边界开区间 while iri: if nums[i]p: nums[i],nums[li] nums[li],nums[i] i 1 li 1 elif nums[i]p: nums[i],nums[ri] nums[ri],nums[i] ri - 1 else: i 1 # 此时[left,li-1]全部小[li,ri]全部相等[ri1,right]全部大 if targetli: return quickselect(left,li-1) elif targetri: return quickselect(ri1,right) else: return nums[target] return quickselect(0,len(nums)-1)3. 无重复字符的最长子串 - 力扣LeetCodeclass Solution: def lengthOfLongestSubstring(self, s: str) - int: # 滑动窗口利用集合确定重复元素 res 0 left 0 d set() for right in range(len(s)): while s[right] in d: d.remove(s[left]) left 1 d.add(s[right]) res max(res,right-left1) return res72. 编辑距离 - 力扣LeetCodeclass Solution: def minDistance(self, word1: str, word2: str) - int: # dp[i][j] 前i长度和前j长度之间至少需要多少步编辑 m,n len(word1),len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(1,m1): dp[i][0] i for j in range(1,n1): dp[0][j] j for i in range(1,m1): for j in range(1,n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]1) return dp[-1][-1]15. 三数之和 - 力扣LeetCodeclass Solution: def threeSum(self, nums: list[int]) - list[list[int]]: res [] n len(nums) # 防止重复先排序 nums sorted(nums) for f in range(n-2): if f0 and nums[f]nums[f-1]: continue if nums[f]0: break s,t f1,n-1 while st: cur nums[f]nums[s]nums[t] if cur 0: # 得到结果后做好去重 res.append([nums[f],nums[s],nums[t]]) while st and nums[s] nums[s1]: s 1 while st and nums[t] nums[t-1]: t - 1 s 1 t - 1 elif cur0: t - 1 else: s 1 return res时间复杂度是o(n^2)200. 岛屿数量 - 力扣LeetCodeclass Solution: def dfs(self, grid, m , n, x, y): grid[x][y] 0 for i,j in [[x1,y],[x-1,y],[x,y1],[x,y-1]]: if 0im and 0jn and grid[i][j] 1: self.dfs(grid,m,n,i,j) def numIslands(self, grid: List[List[str]]) - int: # 本质就是连通分量计算 res 0 m,n len(grid),len(grid[0]) for i in range(m): for j in range(n): if grid[i][j] 1: self.dfs(grid,m,n,i,j) res 1 return res33. 搜索旋转排序数组 - 力扣LeetCodeclass Solution: def search(self, nums: List[int], target: int) - int: l,r 0,len(nums)-1 while lr: mid (lr)//2 if nums[mid] target: return mid else: if nums[mid]nums[0]: # 这个分支大于等于才是有序的 if nums[l]targetnums[mid]: r mid - 1 else: l mid 1 else: if nums[mid]targetnums[r]: l mid 1 else: r mid - 1 return -153. 最大子数组和 - 力扣LeetCodeclass Solution: def maxSubArray(self, nums: List[int]) - int: # 动态规划 # dp[i] 表示到目前为止包含这个元素的子数组最大和是多少 # 要么是一个新数组的开始要么是一个上一个子数组 n len(nums) dp [0]*n dp[0] nums[0] for i in range(1,n): dp[i] max(dp[i-1]nums[i],nums[i]) return max(dp)300. 最长递增子序列 - 力扣LeetCodeclass Solution: def lengthOfLIS(self, nums: List[int]) - int: # dp[i] 表示的是包含i的最长递增子序列的长度 # 其实这也是一个背包问题我们要找到所有的最大的组合 # 子序列就不能考虑双指针了那就只能是dp n len(nums) dp [1]*n # 对于每一个位置我们都要考虑所有比他小的元素 for j in range(1,n): for i in range(j): if nums[i]nums[j]: dp[j] max(dp[i]1,dp[j]) return max(dp)206. 反转链表 - 力扣LeetCodeclass Solution: def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: prev None while head: nex head.next head.next prev prev head head nex return prev46. 全排列 - 力扣LeetCodeclass Solution: def permute(self, nums: List[int]) - List[List[int]]: res [] path [] n len(nums) # 因为是全排列所以一定需要记录一下used used [0]*n def backtrack(): if len(path) n: res.append(path[:]) return for i in range(n): if not used[i]: used[i] 1 path.append(nums[i]) backtrack() path.pop() used[i] 0 backtrack() return res5. 最长回文子串 - 力扣LeetCodeclass Solution: def longestPalindrome(self, s: str) - str: # 看似是子串可以用双指针 # 但是这是一个经典的dp # 因为可以利用dp[i][j] dp[i1]dp[j-1] 如果ij位置相同 n len(s) if n2: return s max_left 0 max_length 1 # dp[i][j] 表示的是i-j上面的子串是一个回文串 dp [[0]*n for _ in range(n)] for i in range(n): dp[i][i] 1 # 先遍历长度然后遍历左边界 for l in range(2,n1): for i in range(n-l1): j il-1 if s[i] ! s[j]: dp[i][j] 0 else: if l2: dp[i][j]1 else: dp[i][j] dp[i1][j-1] if dp[i][j] and lmax_length: max_left i max_length l return s[max_left:max_leftmax_length]912. 排序数组 - 力扣LeetCodeimport random class Solution: def quickselect(self,nums,left,right): pi random.randint(left,right) nums[pi],nums[right] nums[right],nums[pi] p nums[right] l left i left r right while ir: if nums[i]p: nums[i],nums[l] nums[l],nums[i] l 1 i 1 elif nums[i]p: nums[i],nums[r] nums[r],nums[i] r - 1 else: i1 return l-1,r1 def quicksort(self,nums,left,right): if leftright: l,r self.quickselect(nums,left,right) self.quicksort(nums,left,l) self.quicksort(nums,r,right) def sortArray(self, nums: List[int]) - List[int]: self.quicksort(nums,0,len(nums)-1) return nums1143. 最长公共子序列 - 力扣LeetCodeclass Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: # 相对顺序一致肯定是dp # dp[i][j] 表示长度i和j的两个序列里面有多长的子序列 m,n len(text1),len(text2) dp [[0]*(n1) for _ in range(m1)] for i in range(1,m1): for j in range(1,n1): if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1]1 else: dp[i][j] max(dp[i][j-1],dp[i-1][j]) return dp[-1][-1]69. x 的平方根 - 力扣LeetCodeclass Solution: def mySqrt(self, x: int) - int: if x2: return x a x while a*ax: a (ax/a)//2 return int(a)25. K 个一组翻转链表 - 力扣LeetCodeclass Solution: def reverse(self, head, tail): prev tail.next p head while prev!tail: nex p.next p.next prev prev p p nex return tail,head def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]: # 思路不难就是找到k个然后翻转关键是要注意各种实现 jiahead prev ListNode(0,head) tail prev while prev: for _ in range(k): tail tail.next if not tail: return jiahead.next nex tail.next head,tail self.reverse(prev.next,tail) prev.next head tail.next nex prev tail return jiahead.next121. 买卖股票的最佳时机 - 力扣LeetCodeclass Solution: def maxProfit(self, prices: List[int]) - int: # 最多买卖一次 dp [-prices[0],0] for i in range(1,len(prices)): dp[0],dp[1] max(dp[0],-prices[i]),max(dp[1],dp[0]prices[i]) return max(dp)