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

  1. 二叉搜索树的第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

这篇关于Dayx4:剑指offer的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1088607

相关文章

20190315 把整理和培养自己当作一生的事业,而不是局限在找工作拿offer。

把整理和培养自己当作一生的事业,而不是局限在找工作拿offer,做有本事的人。 来东南读研半年了,明显感觉自己掌握的不过是书本知识级别的中上水平,垃圾收集器这些的只知道背面经,靠脑子硬记,缺乏整理和系统,一头浆糊。 现在一边做实训这个烂项目,一边刷面经,一边刷剑指offer,想投些大公司的实习,又觉得还没准备好,看着各 种面经,都能说个大概,但明显感觉到自己知识的不体系和不深入,**做的项目

【简历】25届南京某一本JAVA简历:简历通过率还好,但是拿不到OFFER

注:为保证用户信息安全,姓名和学校等信息已经进行同层次变更,内容部分细节也进行了部分隐藏 简历说明 今天看一份25届南京某一本大学的Java简历。 这个简历呢,学校是一本。我们说上来先要定校招层次,这个层次就按照中厂来讲。因为现在很多的双非一本目标都是在中厂。 这个同学有个实习经历,一本有八成的同学主项目都是重复的。HR他只能看到项目重不重复,要点对不对他不知道,就从这个角度来看,这位同学

所以说读者们才是最优秀的 | 某读者喜提offer(+85%)后的分享

点击上方蓝色字体,选择“设为星标” 回复”资源“获取更多资源 这是小编的一个读者喜提offer后在群里做的分享,文中隐藏了读者的个人隐私信息,小编这里把他的面经分享出来供大家学习。  群友们看到后都纷纷表示【我酸了,现在我就是个柠檬精系列】。 小编现在也是个柠檬精????????????????????????????????。 小编现在是群里最菜的了。     关于如何学习/准备面试的总结

剑指offer——替换字符

/*** 剑指offer* 替换字符*/import java.util.Scanner;public class Solution {public String replaceSpace(StringBuffer str) {String s=str.toString();StringBuilder st=new StringBuilder(); for(int i=0;i<s.leng

剑指offer——第一次只出现一次的字符

/*** */package interview35;/*** 第一次只出现一次的字符* 在一个字符串(1<=字符串长度<=10000,全部由大写字母组成)中找到第一个只出现一次的字符,并返回它的位置*@author: Administrator*@date: 2017-1-9 下午07:34:07*/import java.util.Scanner;public class Solutio

ssh登录服务器报错“no matching host key type found. Their offer: ssh-rsa,ssh-dss”解决方法

这个错误表明你尝试使用 ssh 连接到远程服务器时,客户端和服务器之间没有匹配的 host key 类型。具体来说,远程服务器提供了 ssh-rsa 和 ssh-dss 类型的 host key,但你的 SSH 客户端配置可能不再支持这些较旧的算法。最近的 OpenSSH 版本默认禁用了不够安全的算法,如 ssh-rsa 和 ssh-dss。 解决方法 临时启用 ssh-rsa: 你可以在

Accept CS Ph.D. Offer from Stony Brook University,去SUNY石溪大学的CS Ph.D.啦

前言:在2017年3月24日,正式决定去纽约州立大学石溪分校(State University of New York, Stony Brook,简称石溪大学),CS Ph.D. 项目。本科直博,DIY申请,全额奖学金,第一年5.1万美元(免学费2.2万,2017 fall, 2018 spring 的TA 1.93万,2018 summer RA 1万,没有 Fellowship) Abs

牛客《剑指Offer》 -- 数值的整数次方

题目描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 思路 特别注意负数的情况,出现负数,将其转化为正数然后求倒数。 class Solution {public:double Power(double base, int exponent) {double total = 1;bool flag = false

牛客网《剑指Offer》 二进制中1的个数

题目描述 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 思路 负数用补码,其实就是求一个数据在计算机中是存储是怎么样子的。用位运算,就能很好实现。 class Solution {public:int NumberOf1(int n) {int count = 0;int flag = 1;while (flag != 0) {if ((n & f

牛客网《剑指Offer》 矩形覆盖

题目描述 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? class Solution {public:int rectCover(int number) {if(number==0) return 0;if(number==1) return 1;if(number==2) return 2;retu