刷题《面试经典150题》(第九天)

2024-05-02 19:04

本文主要是介绍刷题《面试经典150题》(第九天),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

加油!

  • 学习目标:
  • 学习内容:
  • 学习时间:
  • 知识点
  • 学习内容:
    • 跳跃游戏 II - 力扣(LeetCode)
    • H 指数 - 力扣(LeetCode)
    • 盛最多水的容器 - 力扣(LeetCode)
    • 矩阵置零 - 力扣(LeetCode)
    • 最小栈 - 力扣(LeetCode)
  • 最后成果
  • 结论

学习目标:

  • 刷完面试经典150题
  • 链接: 面试经典150题

学习内容:

  • 跳跃游戏 II - 力扣(LeetCode)
  • H 指数 - 力扣(LeetCode)
  • 盛最多水的容器 - 力扣(LeetCode)
  • 矩阵置零 - 力扣(LeetCode)
  • 最小栈 - 力扣(LeetCode)

学习时间:

4.30

知识点

学习内容:

跳跃游戏 II - 力扣(LeetCode)

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i] i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达
nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4] 输出: 2

这道题可真恶心,想法是用bfs,可是一直超时超时超时!!!

道心破碎,时间怎么来都是超时
抄答案吧呜呜呜

class Solution:def jump(self, nums: List[int]) -> int:n = len(nums)maxPos, end, step = 0, 0, 0for i in range(n - 1):if maxPos >= i:maxPos = max(maxPos, i + nums[i])if i == end:end = maxPosstep += 1return step

H 指数 - 力扣(LeetCode)

给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h
指数。

根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且 至少 有 h
篇论文被引用次数大于等于 h 。如果 h 有多种可能的值,h 指数 是其中最大的那个。

示例 1:

输入:citations = [3,0,6,1,5] 输出:3 解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 3,
0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3。
示例 2:

输入:citations = [1,3,1] 输出:1

直接暴力出答案

class Solution(object):def hIndex(self, citations):""":type citations: List[int]:rtype: int"""h=1if len(citations)==1:if citations[0]==0:return 0else:return hfor i in range(len(citations)):   #一共有n篇论文,h指数介于1和n之间,所以遍历n次sum=0           #用来记录引用次数大于h指数的数量for j in citations:         #j是每篇论文引用的次数,如果j>h,则sum+1if j>=h:sum+=1if sum>=h:break           #已经满足当前h指数的要求了if sum<h:break               #本次的h指数不满足,停止循环h+=1return h-1
if __name__ == "__main__":a=Solution()citations = [11,15]print(a.hIndex(citations))

盛最多水的容器 - 力扣(LeetCode)

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:

在这里插入图片描述

输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组
[1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:

输入:height = [1,1] 输出:1

终于碰到一道正常题了,这个应该不难吧,如果不懂的话,可以留言,评论。我将秒回复~~~

class Solution(object):def maxArea(self, height):""":type height: List[int]:rtype: int"""left=0right = len(height)-1max_water = -1while left<right:max_water=max(max_water,min(height[left],height[right])*(right-left))if height[left]<height[right]:left+=1else:right-=1return max_waterif __name__ == "__main__":a=Solution()height=[1,2,1]print(a.maxArea(height))

矩阵置零 - 力扣(LeetCode)

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1:

在这里插入图片描述

输入:matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[1,0,1],[0,0,0],[1,0,1]]

示例 2:

在这里插入图片描述

输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

比上一题还简单

class Solution(object):def setZeroes(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""r=len(matrix)       #行c=len(matrix[0])    #列qr=[]   #存行qc=[]   #存列for i in range(r):for j in range(c):if matrix[i][j] == 0:if i not in qr:qr.append(i)if j not in qc:qc.append(j)for i in qr:    #第i行for k in range(c):matrix[i][k]=0for j in qc:for k in range(r):matrix[k][j]=0return matrixif __name__ == "__main__":a=Solution()matrix = [[1,1,1],[1,0,1],[1,1,1]]print(a.setZeroes(matrix))

最小栈 - 力扣(LeetCode)

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop()
删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

示例 1:

输入: [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出: [null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

class MinStack(object):def __init__(self):self.stack = []self.mins = 1<<32def push(self, val):""":type val: int:rtype: None"""self.stack.append(val)self.mins = min(self.stack)def pop(self):""":rtype: None"""self.stack.pop()if len(self.stack)!=0:self.mins = min(self.stack)else:self.mins = 1<<32def top(self):""":rtype: int"""return self.stack[-1]def getMin(self):""":rtype: int"""return self.mins# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
if __name__ == "__main__":obj = MinStack()obj.push(-2)obj.push(0)obj.push(-3)obj.getMin()obj.pop()obj.pop()obj.top()obj.getMin()

最后成果

  • 跳跃游戏 II - 力扣(LeetCode)
  • H 指数 - 力扣(LeetCode)
  • 盛最多水的容器 - 力扣(LeetCode)
  • 矩阵置零 - 力扣(LeetCode)
  • 最小栈 - 力扣(LeetCode)

结论

道友,加油!!

这篇关于刷题《面试经典150题》(第九天)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

java面试常见问题之Hibernate总结

1  Hibernate的检索方式 Ø  导航对象图检索(根据已经加载的对象,导航到其他对象。) Ø  OID检索(按照对象的OID来检索对象。) Ø  HQL检索(使用面向对象的HQL查询语言。) Ø  QBC检索(使用QBC(Qurey By Criteria)API来检索对象。 QBC/QBE离线/在线) Ø  本地SQL检索(使用本地数据库的SQL查询语句。) 包括Hibern

HotSpot虚拟机的经典垃圾收集器

读《深入理解Java虚拟机》第三版笔记。 关系 Serial、ParNew、Parallel Scavenge、Parallel Old、Serial Old(MSC)、Concurrent Mark Sweep (CMS)、Garbage First(G1)收集器。 如图: 1、Serial 和 Serial Old 收集器 2、ParNew 收集器 3、Parallel Sc

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验

Java基础回顾系列-第九天-数据库编程

Java基础回顾系列-第九天-数据库编程 数据库简介工具包java.sql API 内容与数据库建立连接执行SQL语句数据库检索和更新查询结果SQL类型对应Java类型映射元数据异常 API方法DriverManagerConnectionStatementPreparedStatementCallableStatementResultSetjava.sql.Date批处理、存储过程、事务

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

贝壳面试:什么是回表?什么是索引下推?

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50+)中,最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格,遇到很多很重要的面试题: 1.谈谈你对MySQL 索引下推 的认识? 2.在MySQL中,索引下推 是如何实现的?请简述其工作原理。 3、说说什么是 回表,什么是 索引下推 ? 最近有小伙伴在面试 贝壳、soul,又遇到了相关的

毕业前第二次面试的感慨

距面试已经过去了有几天了,我现在想起来都有说多的恨感慨。 我一直都是想找刚刚起步的企业,因为这能让我学到更多的东西,然而正好有一家企业是刚起步的,而且他还有自己的产品专利,可以说这是一家,即是创业又是刚起步的公司,这家公司回复了我投给他的简历,这家企业想进一步了解我的情况,因为简历上我符合这家企业的基本要求,所以要进一步了解。 虽然面试的过程中,他给我的面试题,我做得并不是很理想,

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis