旅游网站系统功能,东莞松山湖华为,手机做印章网站,响应式营销型网站建设文章目录 16 分治16.1 【分治】将有序数组转换为二叉搜索树16.2 【归并排序】排序链表16.3 【分治】建立四叉树16.4 【暴力】合并 K 个升序链表 17 Kadane 算法17.1 【动态规划】最大子数组和17.2 【动态规划】环形子数组的最大和 18 二分查找18.1 【二分】搜索插入位置18.2 【… 文章目录 16 分治16.1 【分治】将有序数组转换为二叉搜索树16.2 【归并排序】排序链表16.3 【分治】建立四叉树16.4 【暴力】合并 K 个升序链表 17 Kadane 算法17.1 【动态规划】最大子数组和17.2 【动态规划】环形子数组的最大和 18 二分查找18.1 【二分】搜索插入位置18.2 【二分】搜索二维矩阵18.3 【二分】寻找峰值18.4 【二分】搜索旋转排序数组18.5 【二分】在排序数组中查找元素的第一个和最后一个位置18.6 【二分】寻找旋转排序数组中的最小值18.7 【二分】寻找两个正序数组的中位数 19 堆19.1 【二分】数组中的第K个最大元素19.2 【贪心】502. IPO19.3 【优先队列】查找和最小的 K 对数字 16 分治
16.1 【分治】将有序数组转换为二叉搜索树
题目地址https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]:def divide(nums,left,right):if left right:return Noneelse:m (leftright)//2root TreeNode(nums[m])root.left divide(nums,left,m-1)root.right divide(nums,m1,right)return rootreturn divide(nums,0,len(nums)-1)16.2 【归并排序】排序链表
题目地址https://leetcode.cn/problems/sort-list/description/?envTypestudy-plan-v2envIdtop-interview-150 首先找到链表的中间位置然后使用归并排序以此递归遍历链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def sortList(self, head: Optional[ListNode]) - Optional[ListNode]:if not head or not head.next:return headslow,fast head,head.nextwhile fast and fast.next:slow,fast slow.next,fast.next.nextmid slow.nextslow.next Noneleft,right self.sortList(head),self.sortList(mid)h ans ListNode()while left and right:if left.val right.val:h.next leftleft left.nextelse:h.next rightright right.nexth h.nexth.next left if left else rightreturn ans.next16.3 【分治】建立四叉树
题目地址https://leetcode.cn/problems/construct-quad-tree/description/?envTypestudy-plan-v2envIdtop-interview-150 首先需要判断每个方块中的数字是否是相同的其次要找到递归的条件这里的条件就是每个方块的四个组成部分然后以此向内遍历直到出现叶子结点就算结束。 # Definition for a QuadTree node.
class Node:def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):self.val valself.isLeaf isLeafself.topLeft topLeftself.topRight topRightself.bottomLeft bottomLeftself.bottomRight bottomRight
class Solution:def construct(self, grid: List[List[int]]) - Node:# if current grid is leaf or notdef is_grid(grid):l len(grid)ssum 0for i in range(l):ssum sum(grid[i])if ssum l*l:return Trueelif ssum 0:return Falseelse:return Nonegrid_flag is_grid(grid)l len(grid)if grid_flag True:node Node(True,True,None,None,None,None)elif grid_flag False:node Node(False,True,None,None,None,None)else:m l // 2topleft_grid [[grid[i][j] for j in range(m)] for i in range(m)]topright_grid [[grid[i][j] for j in range(m,l)] for i in range(m)]bottomleft_grid [[grid[i][j] for j in range(m)] for i in range(m,l)]bottomright_grid [[grid[i][j] for j in range(m,l)] for i in range(m,l)]node Node(False,False,self.construct(topleft_grid),self.construct(topright_grid),self.construct(bottomleft_grid),self.construct(bottomright_grid))return node16.4 【暴力】合并 K 个升序链表
题目地址https://leetcode.cn/problems/merge-k-sorted-lists/description/?envTypestudy-plan-v2envIdtop-interview-150 将链表两两合并。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]:def merge(l1,l2):cur tmp ListNode()while l1 and l2:if l1.val l2.val:tmp.next l1l1 l1.nextelse:tmp.next l2l2 l2.nexttmp tmp.nextif l1:tmp.next l1if l2:tmp.next l2return cur.nextans Nonefor i in lists:ans merge(ans,i)return ans17 Kadane 算法
17.1 【动态规划】最大子数组和
题目地址https://leetcode.cn/problems/maximum-subarray/description/?envTypestudy-plan-v2envIdtop-interview-150 利用动态规划首先定义数组 d p [ i ] dp[i] dp[i]表示终点下标为i的序列的最大子数组和主要考虑以下两种情况
如果 d p [ i − 1 ] dp[i-1] dp[i−1]大于 0 0 0则继续向前增加下标为i的数值作为 d p [ i ] dp[i] dp[i]的子数组和如果 d p [ i − 1 ] dp[i-1] dp[i−1]小于 0 0 0则从这里开始停止重新计算子数组和赋值为 0 0 0后再加入下标为i的数值作为 d p [ i ] dp[i] dp[i]的子数组和。 最后的结果就是数组中最大的那个值。
class Solution:def maxSubArray(self, nums: List[int]) - int:ans,dp nums[0],nums[0]for i in range(1,len(nums)):dp max(dp,0) nums[i]if dp ans:ans dpreturn ans17.2 【动态规划】环形子数组的最大和
题目地址https://leetcode.cn/problems/maximum-sum-circular-subarray/description/?envTypestudy-plan-v2envIdtop-interview-150 分为两种情况如果答案在数组中间则是最大子数组和如果答案在数组两边则是数字的和减去最小子数组和。
class Solution:def maxSubarraySumCircular(self, nums: List[int]) - int:ans_max,dp_max nums[0],nums[0]ans_min,dp_min nums[0],nums[0]total sum(nums)for i in range(1,len(nums)):dp_max max(dp_max,0) nums[i]if dp_max ans_max:ans_max dp_maxdp_min min(dp_min,0) nums[i]if dp_min ans_min:ans_min dp_minif total - ans_min 0:return ans_maxelse:return max(ans_max,total-ans_min)18 二分查找
18.1 【二分】搜索插入位置
题目地址https://leetcode.cn/problems/search-insert-position/description/?envTypestudy-plan-v2envIdtop-interview-150 二分查找注意左右边界的取值。
class Solution:def searchInsert(self, nums: List[int], target: int) - int:left,right 0,len(nums)-1while left right:m (leftright)//2if target nums[m]:right m-1elif target nums[m]:left m1else:return mreturn right118.2 【二分】搜索二维矩阵
题目地址https://leetcode.cn/problems/search-a-2d-matrix/?envTypestudy-plan-v2envIdtop-interview-150 双二分查找。
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) - bool:row,col len(matrix),len(matrix[0])row_l,row_r 0,row-1while row_l row_r:m (row_lrow_r)//2if target matrix[m][0]:row_r m-1elif target matrix[m][0]:row_l m1elif target matrix[m][0]:return Trueif row_r 0 and matrix[row_r][0] target:return Falsecol_l,col_r 0,col-1while col_l col_r:m (col_lcol_r)//2if target matrix[row_r][m]:col_r m-1elif target matrix[row_r][m]:col_l m1elif target matrix[row_r][m]:return Truereturn False18.3 【二分】寻找峰值
题目地址https://leetcode.cn/problems/find-peak-element/description/?envTypestudy-plan-v2envIdtop-interview-150 如果中间位置的值比左边大那么在该索引的右边一定存在峰值同理如果中间位置的值比右边大那么在该索引的左边一定存在峰值最后注意中间索引的取值避免出现循环。
class Solution:def findPeakElement(self, nums: List[int]) - int:l,r 0,len(nums)-1while l r:m (lr1)//2if nums[m] nums[m-1]:l melse:r m-1return l18.4 【二分】搜索旋转排序数组
题目地址https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envTypestudy-plan-v2envIdtop-interview-150 不管怎么进行旋转数组都会被分为有序的两部分每次进行二分前比较一下中间索引与左右边界的值如果 n u m s [ m ] n u m s [ l e f t ] nums[m]nums[left] nums[m]nums[left]则索引左边有序否则右边有序。
class Solution:def search(self, nums: List[int], target: int) - int:left,right 0,len(nums)-1while left right:m (leftright1)//2if nums[m] target:return mif nums[m] nums[left]:if nums[left] target nums[m]:right m-1else:left m1else:if nums[m] target nums[right]:left m1else:right m-1return -118.5 【二分】在排序数组中查找元素的第一个和最后一个位置
题目地址https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envTypestudy-plan-v2envIdtop-interview-150 两次二分第一次找出第一个位置第二次找到 t a r g e t 1 target1 target1的第一个位置该位置左边就是 t a r g e t target target最后一个位置。
class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:def bin_sort(left,right,tgt):while left right:m (leftright1)//2if nums[m] tgt:left m1else:right m-1return leftfirst bin_sort(0,len(nums)-1,target)if first len(nums) or nums[first]!target:return [-1,-1]else:last bin_sort(0,len(nums)-1,target1) - 1return [first,last]18.6 【二分】寻找旋转排序数组中的最小值
题目地址https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
class Solution:def findMin(self, nums: List[int]) - int:left,right 0,len(nums)-1while left right:m (leftright1)//2if nums[m] nums[0]:right m-1else:left m1if left len(nums):return nums[0]else:return nums[left]18.7 【二分】寻找两个正序数组的中位数
题目地址https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envTypestudy-plan-v2envIdtop-interview-150 如果数组的总长度是奇数那么中位数就是第 m n 1 2 \frac{mn1}{2} 2mn1小的元素如果数组的总长度是偶数那么中位数就是第 m n 1 2 \frac{mn1}{2} 2mn1和第 m n 2 2 \frac{mn2}{2} 2mn2小的元素的平均值。 函数get_k_min是一个辅助函数它用于找到两个已排序数组的第 k k k小的数。它通过比较两个数组的第 k / 2 k/2 k/2个元素来实现这个功能。如果数组 1 1 1的第 k / 2 k/2 k/2个元素小于数组 2 2 2的第 k / 2 k/2 k/2个元素那么数组 1 1 1的前 k / 2 k/2 k/2个元素一定不会是第 k k k小的数所以可以将它们排除在外。反之亦然。这个过程会一直持续到 k k k等于 1 1 1或者其中一个数组为空。
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:def k_min(start1,end1,start2,end2,k):cur_nums1 end1-start11cur_nums2 end2-start21if cur_nums1 0:return nums2[start2k-1]if cur_nums2 0:return nums1[start1k-1]if k 1:return min(nums1[start1],nums2[start2])m1 start1 min(cur_nums1,k//2) - 1m2 start2 min(cur_nums2,k//2) - 1if nums1[m1] nums2[m2]:return k_min(m11,end1,start2,end2,k-(m1-start11))else:return k_min(start1,end1,m21,end2,k-(m2-start21))m,n len(nums1),len(nums2)a,b (mn1)//2,(mn2)//2x k_min(0,m-1,0,n-1,a)y k_min(0,m-1,0,n-1,b)return (xy)/219 堆
19.1 【二分】数组中的第K个最大元素
题目地址https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
#方法一
class Solution:def findKthLargest(self, nums: List[int], k: int) - int:def quick_sort(num,k):big,equal,small [],[],[]for n in num:if n num[0]:big.append(n)elif n num[0]:small.append(n)else:equal.append(n)if k len(big):return quick_sort(big,k)elif k len(equal) len(big):return quick_sort(small,k-len(equal)-len(big))else:return num[0]return quick_sort(nums,k)
#方法二
class Solution:def findKthLargest(self, nums: List[int], k: int) - int:nums.sort()l len(nums)return nums[l-k]19.2 【贪心】502. IPO
题目地址https://leetcode.cn/problems/ipo/description/?envTypestudy-plan-v2envIdtop-interview-150 在当前的本金小于等于当前资本的项目中每次都选择利益最大的那个但要注意特殊情况当前的本金已经不能投资任何项目时直接结束。
class Solution:def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) - int:pro_cap sorted(zip(profits,capital),key lambda x:x[1])idx,l 0,len(profits)cur []while k:while idx l and pro_cap[idx][1] w:heapq.heappush(cur,-pro_cap[idx][0])idx 1if cur:w - heapq.heappop(cur)else:breakk - 1return w19.3 【优先队列】查找和最小的 K 对数字
题目地址https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/?envTypestudy-plan-v2envIdtop-interview-150 多路归并思想每次将三元组(两数组之和,数组1下标idx1,数组2下标idx2)加入到优先队列中以两个数组中较小长度的为数组1较大长度的为数组2每次将优先队列的栈顶出列当前未被加入到答案的所有点对中的最小值然后将下一组下标加入优先队列中。
class Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) - List[List[int]]:flag Trueif len(nums1) len(nums2):nums1,nums2 nums2,nums1flag Falsen1,n2 len(nums1),len(nums2)ans,pq [],[]for i in range(min(n1,k)):heapq.heappush(pq,(nums1[i]nums2[0],i,0))while len(ans) k:_,idx1,idx2 heapq.heappop(pq)if flag:ans.append([nums1[idx1],nums2[idx2]])else:ans.append([nums2[idx2],nums1[idx1]])if idx21 n2:heapq.heappush(pq,(nums1[idx1]nums2[idx21],idx1,idx21))return ans
(nums2)ans,pq [],[]for i in range(min(n1,k)):heapq.heappush(pq,(nums1[i]nums2[0],i,0))while len(ans) k:_,idx1,idx2 heapq.heappop(pq)if flag:ans.append([nums1[idx1],nums2[idx2]])else:ans.append([nums2[idx2],nums1[idx1]])if idx21 n2:heapq.heappush(pq,(nums1[idx1]nums2[idx21],idx1,idx21))return ans
