当前位置: 首页 > news >正文

【Leetcode 剑指Offer】第 5 天 查找算法(中等)

查找算法

    • 剑指 Offer 04. 二维数组中的查找
    • 剑指 Offer 11. 旋转数组的最小数字
    • 剑指 Offer 50. 第一个只出现一次的字符
      • Python字典基础
      • 哈希表(python中是dict())
      • 有序哈希表

第一个中等,后两个简单题。

剑指 Offer 04. 二维数组中的查找

题:在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
现有矩阵 matrix 如下:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。
给定 target = 20,返回 false。


这题看到有**暴力解法【时间复杂度O(MN)】**,

二分法【矩阵 matrix\textit{matrix}matrix 中每一行的元素都是升序排列的,因此我们可以对每一行都使用一次二分查找,判断 target\textit{target}target 是否在该行中,从而判断 target\textit{target}target 是否出现】,

最巧妙好懂的是下面这种,以左下角数字作为标志,最多查找M+N次。**

class Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:i,j=len(matrix) - 1,0while i>=0 and j<len(matrix[0]):if matrix[i][j]>target:i-=1elif matrix[i][j]<target:j+=1else: return Truereturn False

复杂度分析: 时间复杂度 O(M+N) :其中,N和 M分别为矩阵行数和列数,此算法最多循环 M+N 次。 空间复杂度
O(1)O(1)O(1) : i, j 指针使用常数大小额外空间。

在这里插入图片描述

作者:Krahets
链接:https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solutions/95306/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-zuo/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的最小值为 1。

注意,数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

思路: 从后往前遍历,找到第一个前一个数比自己大的,这个数就是最小的。

class Solution:def minArray(self, numbers: List[int]) -> int:i=len(numbers)-1while(i>0):if numbers[i]>=numbers[i-1]:i-=1else:return numbers[i]return numbers[0]   

剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

在这里插入图片描述

复杂度分析:
时间复杂度 O(N) : N 为字符串 s 的长度;需遍历 s 两轮,使用 O(N);HashMap 查找操作的复杂度为 O(1) ;
空间复杂度 O(1): 由于题目指出 s 只包含小写字母,因此最多有 26 个不同字符,HashMap 存储需占用 O(26)=O(1) 的额外空间。

作者:Krahets
链接:https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solutions/159489/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Python字典基础

字典的每个键值 key:value 对用冒号 : 分割,每个键值对之间用逗号 , 分割,整个字典包括在花括号 {} 中;
键一般是唯一且不可变【不能是数组】的,如果重复最后的一个键值对会替换前面的,值不需要唯一。
访问某健的值:dict['key'] 添加更新相同方法;
删除操作:

del tinydict['Name']  # 删除键是'Name'的条目
tinydict.clear()      # 清空字典所有条目
del tinydict          # 删除字典

哈希表(python中是dict())

! Python 代码中的 not c in dic 整体为一个布尔值c in dic 为判断字典中是否含有键 c

class Solution:def firstUniqChar(self, s: str) -> str:dic = {}for c in s:dic[c] = not c in dicfor c in s:if dic[c]: return creturn ' '

有序哈希表

在哈希表的基础上,有序哈希表中的键值对是 按照插入顺序排序 的。基于此,可通过遍历有序哈希表,实现搜索首个 “数量为 1的字符”。

哈希表是 去重 的,即哈希表中键值对数量 ≤\leq≤ 字符串 s 的长度。因此,相比于方法一,方法二减少了第二轮遍历的循环次数。当字符串很长(重复字符很多)时,方法二则效率更高(第二次搜索dic次)。

class Solution:def firstUniqChar(self, s: str) -> str:dic = collections.OrderedDict()for c in s:dic[c] = not c in dicfor k, v in dic.items():if v: return kreturn ' '

作者:Krahets
链接:https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solutions/159489/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关文章:

【Leetcode 剑指Offer】第 5 天 查找算法(中等)

查找算法剑指 Offer 04. 二维数组中的查找剑指 Offer 11. 旋转数组的最小数字剑指 Offer 50. 第一个只出现一次的字符Python字典基础哈希表&#xff08;python中是dict()&#xff09;有序哈希表第一个中等&#xff0c;后两个简单题。剑指 Offer 04. 二维数组中的查找 题&#…...

薯条投放适合哪些笔记?小红书薯条投放的3种模式

随着小红书平台的种草推广模式兴盛&#xff0c;薯条投放这个词也渐渐进入大众的视野&#xff0c;今天就来给大家讲讲什么是薯条投放&#xff0c;以及薯条投放适合哪些笔记。一、什么是薯条投放?薯条是一款为小红书用户打造的笔记推广工具&#xff0c;用户可选择推广目标&#…...

记录第一个Python练习的过程

题目如下 编写一个名为collatz()的函数&#xff0c;它有一个名为number的参数。如果参数是偶数&#xff0c;那么collatz()就打印出number // 2&#xff0c;并返回该值。如果number是奇数&#xff0c;collatz()就打印并返回3 * number 1。 然后编写一个程序&#xff0c;让用户…...

【Python】3.3实现多线程

程序Program进程Process线程Thread为完成特定任务而用计算机语言编写的一组计算机能识别和执行的指令的集合。程序是指令、数据及其组织形式的描述&#xff0c;一段静态代码&#xff0c;静态对象。计算机中的程序关于某数据集合上的一次执行过程。进程是程序的实体&#xff0c;…...

在linux中使用lftp和sftp下载文件(夹)

一、首先确保你的系统中已经下载了lftp和sftp。 1.安装lftp sudo apt install lftp sudo apt install screen 2.安装sftp 在Linux系统中&#xff0c;一般RedHat系统默认已经安装了openssh-client和openssh-server&#xff0c;即默认已经集成了sftp服务&#xff0c;不需要重…...

Docker简介与用法

文章目录1、Docker简介1.1、Docker能解决什么问题1.2、什么是虚拟机技术1.2.1、虚拟机的缺点1.3、什么是容器1.3.1、容器与虚拟机比较1.4、分析 Docker 容器架构1.4.1、Docker客户端和服务器1.4.2、Docker 镜像(Image)1.4.3、Docker 容器(Container)1.4.4、Docker 仓库(reposit…...

基于海鸥算法改进的DELM分类-附代码

海鸥算法改进的深度极限学习机DELM的分类 文章目录海鸥算法改进的深度极限学习机DELM的分类1.ELM原理2.深度极限学习机&#xff08;DELM&#xff09;原理3.海鸥算法4.海鸥算法改进DELM5.实验结果6.参考文献7.Matlab代码1.ELM原理 ELM基础原理请参考&#xff1a;https://blog.c…...

linux基本功系列之mount命令实战

文章目录前言一. mount命令的介绍二. 语法格式及常用选项三. 参考案例3.1 将iso镜像挂载到/mnt上3.2 把某个分区挂载到/sdb1上3.3 用只读的形式把/dev/sdb2挂载到/sdb2上3.4 设置自动挂载总结前言 大家好&#xff0c;又见面了&#xff0c;我是沐风晓月&#xff0c;本文是专栏【…...

力扣Top100题之两数相加(Java解法)

0 题目描述 给你两个 非空 的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的&#xff0c;并且每个节点只能存储 一位 数字。 请你将两个数相加&#xff0c;并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外&#xff0c;这两个数…...

【测试】Python手机自动化测试库uiautomator2和weditor的详细使用

1.说明 我们之前在电脑操作手机进行自动化测试&#xff0c;基本上都是通过Appium的&#xff0c;这个工具确实强大&#xff0c;搭配谷歌官方的UiAutomator基本上可以完成各种测试&#xff0c;但缺点也很明显&#xff0c;配置环境太麻烦了&#xff0c;需要jdk、sdk等&#xff0c…...

《NFL橄榄球》:旧金山49人·橄榄1号位

旧金山四九人&#xff08;San Francisco 49ers&#xff0c;又译旧金山淘金者) 是美国全国橄榄球联盟球队。成立于1946年&#xff0c;最初作为全美橄榄球联合会(AAFC)的一员参加比赛&#xff0c;后于1950年与克利夫兰布朗一同加入由美国橄榄球联合会合并而成的NFL。现任主教练为…...

spark为什么比hadoop快

网上一堆人根本对计算框架一知半解就出来糊弄人&#xff0c;常见解答有&#xff1a; spark是基于内存计算&#xff0c;所以快。这跟废话似的&#xff0c;mr计算的时候不也是基于内存&#xff1f; mr shuffle落盘。这也是胡扯&#xff0c; spark shuffle不落盘&#xff1f; 实际…...

跨境人都在用的指纹浏览器到底有什么魔力?三分钟带你了解透彻

什么是指纹浏览器&#xff1f;这是东哥近期收到最多的粉丝私信咨询&#xff0c;指纹两个字大家都很熟悉&#xff0c;指纹浏览器就变得陌生起来。之前东哥也跟大家分享过很多次指纹浏览器的用法&#xff0c;鉴于还是很多人不认识这个好用的工具&#xff0c;东哥今天就来详细给大…...

机器学习概述

机器学习是人工智能的核心研究领域之一&#xff0c;其研究动机是为了让计算机系统具有人的学习能力以便实现人工智能。目前被广泛采用的机器学习的定义是“利用经验来改善计算机系统自身的性能”。由于“经验在计算机系统中主要是以数据的形式存在的&#xff0c;因此机器学习需…...

企业网站自动生成系统的设计和实现

技术&#xff1a;Java、JSP等摘要&#xff1a;随着Internet技术的发展&#xff0c;人们的日常生活已经离不开网络。未来社会人们的生活和工作将越来越依赖于数字技术的发展&#xff0c;越来越数字化、网络化、电子化、虚拟化。Internet的发展历程以及目前的应用状况和发展趋势&…...

sikuli+eclipse对于安卓app自动化测试的应用

Sikuli是什么&#xff1f; 下面是来自于官网的介绍&#xff1a;Sikuli is a visual technology to automate and test graphical user interfaces (GUI) using images (screenshots). Sikuli includes Sikuli Script, a visual scripting API for Jython, and Sikuli IDE, an …...

react源码分析:babel如何解析jsx

同作为MVVM框架&#xff0c;React相比于Vue来讲&#xff0c;上手更需要JavaScript功底深厚一些&#xff0c;本系列将阅读React相关源码&#xff0c;从jsx -> VDom -> RDOM等一些列的过程&#xff0c;将会在本系列中一一讲解 工欲善其事&#xff0c;必先利其器 经过多年的…...

搜广推 WideDeep 与 DeepCrossNetwork (DCN) - 记忆+泛化共存

😄 这节来讲讲Wide&Deep与Deep&CrossNetwork (DCN)。从下图可看出WD非常重要,后面衍生出了一堆WD的变体。本节要讲的WD和DCN结构都非常简单,但其设计思想值得学习。 🚀 wide&deep:2016年,谷歌提出。 🚀 Deep&CrossNetwork (DCN):2017年,谷歌和斯坦…...

项目管理工具dhtmlxGantt甘特图入门教程(十四):导出/导入 Excel到 iCal

这篇文章给大家讲解利用dhtmlxgantt导入/导出Excel到iCal的操作方法。 dhtmlxGantt是用于跨浏览器和跨平台应用程序的功能齐全的Gantt图表&#xff0c;可满足应用程序的所有需求&#xff0c;是完善的甘特图图表库 DhtmlxGantt正版试用下载&#xff08;qun&#xff1b;765665…...

k-means聚类总结

1.概述 聚类算法又叫做‘无监督学习’&#xff0c;其目的是将数据划分成有意义或有用的组&#xff08;或簇&#xff09;。 2.KMeans 关键概念&#xff1a;簇与质心 KMeans算法将一组N个样本的特征矩阵X划分为K个无交集的簇&#xff0c;直观上来看是簇是一组一组聚集在一起的…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...