Dayx4:剑指offer

2024-06-23 23:38

文章标签 offer dayx4

本文主要是介绍Dayx4:剑指offer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\bullet$ 举一反三之二分法

53.1 (多practice). 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

def searchRange(self, nums, target):if not nums: return -1,-1l,r=0,len(nums)-1#二分找到target的第一个位置while l<r:mid=l+(r-l)//2if nums[mid]<target:  # 说明答案在右边，不包含midl=mid+1else:r=midif nums[l]!=target: return -1,-1![在这里插入图片描述](https://img-blog.csdnimg.cn/20200718165738578.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIxMTQ5MDA=,size_16,color_FFFFFF,t_70)left=l# 二分找到target的最后一个位置l, r = 0, len(nums) - 1while l < r:mid=l+(r-l+1)//2if nums[mid]<=target:  # 说明答案在右边，包含mid，故上面加1l=midelse:r=mid-1return left,r

53.2. 缺失数字 leetcode 268
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

Time: O(logn)
#[数组有序]二分
def getMissingNumber(self, nums):nums.sort()  #!!!leetcode中无序，故先sortif not nums: return 0'''standard 二分'''l,r=0,len(nums)-1while l<r:mid=l+r>>1  #等价(l+r)//2if nums[mid]!=mid:  #满足条件的，保持不动r=midr=midelse:l=mid+1if nums[l]==l: return l+=1return l

$\bullet$ 由于异或运算（XOR）满足结合律，
并且对一个数进行两次完全相同的异或运算会得到原来的数，因此我们可以通过异或运算找到缺失的数字。

#[数组无序]
公式求和   Time: O(n)
def getMissingNumber_2(self, nums):n=len(nums)res= (0+n-1)*n/2 - sum(nums)return res异或法
def missingNumber(self, nums: List[int]) -> int:miss = len(nums)  # 假设缺失值为 nfor i, num in enumerate(nums):miss ^= i ^ numreturn miss

$\bullet$ 知识点：
&、 |位运算符; and、or逻辑运算符
`Python 中（&，|）和（and，or）之间的区别

`python集合中&、|、-、^、与and、or

53.3. 数组中数值与下标相等的元素
实现一个函数找出单调递增的数组中任意一个数值等于其下标的元素。
e.g，在数组[-3, -1, 1, 3, 5]中，数字3和它的下标相等

def getNumberSameAsIndex(self, nums):l,r=0,len(nums)-1while l<r:mid=l+r>>1if nums[mid]<mid:l=mid+1else:r=mid  #！满足条件，就不动if nums[l]!=l: return -1       return l

$\bullet$ 二叉树系列—树遍历algs application

二叉搜索树的第k小的节点
一棵二叉搜索树，请找出其中的第k小的结点。
假设树和k都存在，并且1≤k≤树的总结点数。

中序遍历
二叉搜索树：all左节点值<根节点值 all右节点值>根节点值

中序遍历的同时，没遍历一次，k–，当k = 0时，ans

class Solution(object):def kthNode(self, pRoot, k):'''中序遍历''' #[自顶向下]剖开；[自下向上]寻找def dfs(pRoot):  #!!!noneed selfif not pRoot: returndfs(pRoot.left)self.k -=1if self.k==0: self.res=pRootif self.k>0: dfs(pRoot.right)  #剪枝；只self.k-=1self.k=k #!!! k要为全局变量self.res=Nonedfs(pRoot)return self.res

55.1. 二叉树的深度简单
给定一个二叉树，找出其最大深度。

递归
class Solution:def maxDepth(self, root: TreeNode) -> int:if not root: return 0left  = self.maxDepth(root.left)right = self.maxDepth(root.right)return max(left,right)+1

55.2. 平衡二叉树 leetcode 110
判断它是否是高度平衡的二叉树?

definition: 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

class Solution:def isBalanced(self, root: TreeNode) -> bool:def dfs(root):if not root: return 0left =dfs(root.left)  #!!!调用[嵌套在上一个self def函数下；同T54；区别T55.1]!!!right=dfs(root.right)if abs(left-right)>1: self.ans =Falsereturn max(left, right)+1self.ans=Truedfs(root)return self.ans