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链接 } 网页需要给自己的应用拉…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...

华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...

nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

MLP实战二:MLP 实现图像数字多分类
任务 实战(二):MLP 实现图像多分类 基于 mnist 数据集,建立 mlp 模型,实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入,可视化图形数字; 2、完成数据预处理:图像数据维度转换与…...

设计模式域——软件设计模式全集
摘要 软件设计模式是软件工程领域中经过验证的、可复用的解决方案,旨在解决常见的软件设计问题。它们是软件开发经验的总结,能够帮助开发人员在设计阶段快速找到合适的解决方案,提高代码的可维护性、可扩展性和可复用性。设计模式主要分为三…...