小白学习打卡02

这是在力扣的刷题过程的笔记记录；代码部分来自于力扣官方解答

1.有序矩阵

题目描述：

求取某多维数组中第k个元素；此元素为第k个最小元素

解答：

方法一： 直接排序 把多维数组另存为一维数组进行排序

class Solution: #python3 def kthsmaller(self, matrix:list[list[]], k:int)->int: r=sorted(sum(matrix,[])) return r[k-1] #空间复杂度O(n^2)；时间复杂度O(n^2logn) class Solution{ public int kthsmaller(int[][] matrix,int k){ int rows=matrix.length,columns=matrix[0].length;//rows为数组的宽度 columns为数组的列数 int[] sorted= new int[rows * columns]; //重新排序 int index=0; for(int[] row:matrix){ for(int num:row){ sorted[index++]=num;//对每一行的数组元素进行排序 } } Arrays.sort(sorted);//重新排序成一维数组 return sorted[k-1];//返回一维数组中的排序 } }//空间复杂度O(n^2)；时间复杂度O(n^2logn)

方法二： 二分查找 （ps：看了官方题解有点难，不过相对来说，python3还是认为能理解一些）

class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int: n = len(matrix) #定义数组长度 def check(mid): #定义函数check 目的检查mid i, j = n - 1, 0 num = 0 while i >= 0 and j < n: #当最后一个值的index大于0且第一个值的index小于数组长度时进行循环 if matrix[i][j] <= mid: num += i + 1 // j += 1 #相当于left+1 else: i -= 1 #i=i-1 相当于right-1 return num >= k #返回num大于k left, right = matrix[0][0], matrix[-1][-1] while left < right: mid = (left + right) // 2 if check(mid): right = mid else: left = mid + 1 return left

2.数组转为二叉树

题目描述：

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

解答：

class Solution: def sortArraytoBST(self,nums:list[int])->TreeNode: def exo(left,right): if left>right: return None mid=(left+right)//2 #左 or mid=(left+right+1)//2 #右 or mid(left+right+randint(0,1))//2 #随机 root=TreeNode(nums[mid]) root.left=exo(left,mid-1) root.right=exo(mid+1,right) return root return exo(0,len(nums)-1)

3.跳水板

题目描述：

输入： shorter = 1 longer = 2 k = 3 输出： {3,4,5,6}

解答：

Class Solution: def dividBroad(self, shorter:int,longer:int, k:int)->List[int]: if k==0: return [] if shorter==longer: return (shorter*k) result=[] #一定注意这里是result=[] for i in range(k+1): ##??? result.append(shorter*(k-i)+longer*i) return result