Leetcode Hot100之哈希表
1. 两数之和
- 题目描述
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现 - 思路
通过哈希表保存每个数字nums[i]对应的下标,并查找target-nums[i]是否在哈希表中,这样可以通过一次遍历就完成;
时间复杂度: O(N);空间复杂度: O(N) - 代码
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:n = len(nums)if n < 2:return []dic = {}for i in range(n):if target - nums[i] in dic:return [dic[target - nums[i]], i]dic[nums[i]] = i
2. 字母异位词分组
-
题目描述
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
-
思路
提到字母异位词要联想到两点:(1) 字母异位词的字母计数的哈希表是相同的 (2)字母异位词按照字母序排序后的字符串是相同的
本道题就是要将字母异位词进行聚类,判断方式无非上面两种,由于我们通过字典存储聚类字母异位词,而字典是不可哈希的,无法作为字典的key,因此就将排序后的字母异位词作为key;
时间复杂度:O(nklogk)其中 n是 strs 中的字符串的数量,k是 strs 中的字符串的的最大长度。
空间复杂度:O(nk) -
代码
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:n = len(strs)if n == 0:return []dic = {}for i in range(n):s = strs[i]s_sorted = "".join(sorted(s))if s_sorted not in dic:dic[s_sorted] = [s]else:dic[s_sorted].append(s)return [value for value in dic.values()]
如果想通过字母计数哈希表的方式来实现,则不能用字典来计数,需要用列表,然后再转成tuple,可以作为dict的key:
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp = collections.defaultdict(list)for st in strs:counts = [0] * 26for ch in st:counts[ord(ch) - ord("a")] += 1# 需要将 list 转换成 tuple 才能进行哈希mp[tuple(counts)].append(st)return list(mp.values())
3. 最长连续序列
-
题目描述
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:输入:nums = [100,4,200,1,3,2]输出:4解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
-
思路
由于序列是无序的,而题目要求O(n)的解法,那么想到用哈希表实现,注意哈希表题目有的用字典方便,有的用数组方便,有的用集合方便,集合(set)是一个无序的不重复元素序列。本题就是用set比较合适,因为我们只要方便查找哪些元素是否出现即可,不需要用到其他信息;- 首先将所有元素放入set中
- 遍历set中的元素num,如果num-1在set中说明num并不是一个连续序列的起点;如果num是一个连续序列的起点,那么依次判断num+1,num+2是不是在set中,即可获取以num为起点的连续序列的长度;
时间复杂度:O(N);因为每个元素只会被遍历一次,因此数组中的每个数只会进入内层循环一次
空间复杂度:O(N)
-
代码
class Solution:def longestConsecutive(self, nums: List[int]) -> int:n = len(nums)if n == 0:return 0nums_set = set(nums)res = 1for i in nums_set:if i - 1 not in nums_set:cur_l = 1cur_num = iwhile cur_num + 1 in nums_set:cur_num += 1cur_l += 1res = max(res, cur_l)return res
相关文章:
Leetcode Hot100之哈希表
1. 两数之和 题目描述 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现思路…...
Vision Transformer with Sparse Scan Prior
摘要 https://arxiv.org/pdf/2405.13335v1 In recent years, Transformers have achieved remarkable progress in computer vision tasks. However, their global modeling often comes with substantial computational overhead, in stark contrast to the human eye’s eff…...
笔记-python 中BeautifulSoup入门
在前面的例子用,我用了BeautifulSoup来从58同城抓取了手机维修的店铺信息,这个库使用起来的确是很方便的。本文是BeautifulSoup 的一个详细的介绍,算是入门把。文档地址:http://www.crummy.com/software/BeautifulSoup/bs4/doc/ …...

Tomcat Websocket应用实例研究
概述 本文介绍了如何根据Tomcat给出的websocket实例,通过对实例的学习,定制自己基于websocket的应用。 环境及版本: Ubuntu 22.04.4 LTSApache Tomcat/10.1.20openjdk 11.0.23 2024-04-16浏览器:Chrome 相关资源及链接 Class…...
leetcode-11-二叉树前中后序遍历以及层次遍历
一、递归版 前序遍历 (先根遍历) 中左右 class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result new ArrayList<Integer>();preorder(root, result);return result;}public void preorder…...
Python基础学习笔记(十一)——集合
目录 一、集合的介绍与创建二、集合的存储原理三、元素的修改1. 添加元素2. 删除元素 四、集合的运算五、集合的判定 一、集合的介绍与创建 集合(set),一种可变、无序、不重复的数据结构,由大括号{}内、用逗号分隔的一组元素组成。…...
FineReport
1.FineReport 官网 :FineReport产品简介- FineReport帮助文档 - 全面的报表使用教程和学习资料 下载地址 免费下载FineReport - FineReport报表官网 FineReport是一款用于报表制作,分析和展示的工具。 普通模板:是 FineReport 最常用…...
嵌入式就业前景好么
嵌入式就业前景在当前环境下是较为乐观的,以下是对嵌入式就业前景的详细分析: 广泛应用领域:嵌入式系统广泛应用于智能家居、医疗设备、航空航天等领域。随着物联网(IoT)的快速发展,预计到2024年ÿ…...

为啥找对象千万别找大厂男,还好我不是大厂的。。
网上看到一大厂女员工发文说:找对象千万别找大厂男,理由说了一大堆,无非就是大厂男为了逃避带娃,以加班为由宁愿在工位上玩游戏也不愿回家。当然这种观点有的人赞同有的人反对。 网友精彩评论: --------------下面是今…...
如何查看k8s中service的负载均衡策略
在Kubernetes中,Service的负载均衡策略一般由kube-proxy负责,kube-proxy使用iptables或IPVS规则进行负载均衡。默认情况下,kube-proxy使用的是轮询(Round Robin)策略,但是在使用IPVS模式时,可以…...

Linux-DNS域名解析服务01
BIND 域名服务基础 1、DNS(Domain Name System)系统的作用及类型 整个 Internet 大家庭中连接了数以亿计的服务器、个人主机,其中大部分的网站、邮件等服务器都使用了域名形式的地址,如 www.google.com、mail.163.com 等。很显然…...

[c++刷题]贪心算法.N01
题目如上: 首先通过经验分析,要用最少的减半次数,使得数组总和减少至一半以上,那么第一反应就是每次都挑数组中最大的数据去减半,这样可以是每次数组总和值减少程度最大化。 代码思路:利用大根堆去找数据中的最大值,…...

推荐常用的三款源代码防泄密软件
三款源代码防泄密软件——安秉源代码加密、Virbox Protector 和 MapoLicensor——确实各自在源代码保护的不同方面有其专长。这些软件可以满足企业对于源代码保护的三大需求:防止泄露、防止反编译和防止破解。 安秉源代码加密: 专注于源代码文件的加密&…...

Android 13 高通设备热点低功耗模式(2)
前言 之前写过一篇文章:高通热点被IOS设备识别为低数据模式,该功能仿照小米的低数据模式写的,散发的热点可以达到被IOS和小米设备识别为低数据模式。但是发现IOS设备如果后台无任何网络请求的时候,息屏的状态下过一会,会自动断开热点的连接。 分析 抓取设备的热点相关的…...
web前端任职条件:全面解析
web前端任职条件:全面解析 在当今数字化快速发展的时代,Web前端技术已经成为互联网行业不可或缺的一部分。作为一名Web前端开发者,需要具备哪些任职条件呢?本文将从四个方面、五个方面、六个方面和七个方面为您深入剖析。 四个方…...

分析医药零售数据该用哪个BI数据可视化工具?
数据是企业决策的重要依据,可以用于现代企业大数据可视化分析的BI工具有很多,各有各擅长的领域。那么哪个BI数据可视化工具分析医药零售数据又好又快? 做医药零售数据分析首推奥威BI数据可视化工具! 奥威BI数据可视化工具做医药…...
如何使用芯片手册做软件开发?
在阅读和利用芯片手册进行软件开发时,你应该关注以下几个关键点: 引脚功能:了解芯片上每个引脚的功能,包括它们可以被配置为输入还是输出,以及它们支持的特殊功能,如模拟输入、PWM输出、中断等。 寄存器映…...
基于深度学习的文本翻译
基于深度学习的文本翻译 基于深度学习的文本翻译,通常称为神经机器翻译(Neural Machine Translation, NMT),是近年来在自然语言处理(NLP)领域取得显著进展的技术。NMT通过使用深度神经网络来自动学习和翻译…...

Unity制作透明材质直接方法——6.15山大软院项目实训
之前没有在unity里面接触过材质的问题,一般都是在maya或这是其他建模软件里面直接得到编辑好材质的模型,然后将他导入Unity里面,然后现在碰到了需要自己在Unity制作透明材质的情况,所以先搜索了一下有没有现成的方法,很…...
【HarmonyOS NEXT】如何通过h5拉起应用(在华为浏览器中拉起应用)
华为浏览器支持拉起外部应用 浏览器访问网页经常会遇到deeplink的场景。当前处理方案统一为使用AMS系统能力startAbility去隐式拉起。传递的want参数为 { "actions": "ohos.want.action.viewData", "uri": deeplink链接 } 网页需要给自己的应用拉…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...