首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >golang刷leetcode 经典(6) 实现跳表

golang刷leetcode 经典(6) 实现跳表

作者头像
golangLeetcode
发布于 2022-08-02 09:32:50
发布于 2022-08-02 09:32:50
21000
代码可运行
举报
运行总次数:0
代码可运行

不使用任何内建的哈希表库设计一个哈希映射

具体地说,你的设计应该包含以下的功能

put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更新这个值。

get(key):返回给定的键所对应的值,如果映射中不包含这个键,返回-1。

remove(key):如果映射中存在这个键,删除这个数值对。

示例:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // 返回 1
hashMap.get(3);            // 返回 -1 (未找到)
hashMap.put(2, 1);         // 更新已有的值
hashMap.get(2);            // 返回 1 
hashMap.remove(2);         // 删除键为2的数据
hashMap.get(2);            // 返回 -1 (未找到) 

注意:

所有的值都在 [1, 1000000]的范围内。

操作的总数目在[1, 10000]范围内。

不要使用内建的哈希库。

解题思路

1,使用拉链法

2,和hashset区别是节点里存的内容

A,hashset 里存key

B,hashmap里存key,value

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
type MyHashMap struct {
    data []*Node
    len int
}

type Node struct{
    key int
    value int
    next  *Node
}

/** Initialize your data structure here. */
func Constructor() MyHashMap {
    return MyHashMap{
        data:make([]*Node,10001),
        len:10001,
    }
}


/** value will always be non-negative. */
func (this *MyHashMap) Put(key int, value int)  {
    data:=this.data[key%this.len]
    if data==nil{
        this.data[key%this.len]=&Node{
           key:key,
           value:value,
        }
    }else{
            if data.key==key{
                data.value=value
                return
            }
        for data.next!=nil{
            data=data.next
            if data.key==key{
                data.value=value
                return
            }
        }
        data.next=&Node{
            key:key,
            value:value,
        }
    }
    //this.Print()
}


/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func (this *MyHashMap) Get(key int) int {
    data:=this.data[key%this.len]
    if data==nil{
        return -1
    }
    for data.next!=nil{
        if data.key==key{
            return data.value
        }
        data=data.next
    }
    if data.key==key {
         return data.value
    }
    return -1
}


/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func (this *MyHashMap) Remove(key int)  {
    data:=this.data[key%this.len]
    if data==nil{
        return
    }
    if data.key==key{
        this.data[key%this.len]=data.next
        //this.Print()
        return
    }
    for data.next!=nil{
        if data.next.key!=key{
            data=data.next
        }else{
            data.next=data.next.next
        }
    } 
}

func (this *MyHashMap)Print(){
   fmt.Println("----",this.len,":")
   for i:=0;i<len(this.data);i++{
       d:=this.data[i]
       if d!=nil{
           fmt.Println(this.data[i].key)
           for d.next!=nil{
               d=d.next
                fmt.Println(d.key)
           }     
       }
   }
   fmt.Println(":------")
}
/**
 * Your MyHashMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Put(key,value);
 * param_2 := obj.Get(key);
 * obj.Remove(key);
 */
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-12-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 golang算法架构leetcode技术php 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
python干货——函数
👨‍🎓作者:Java学术趴 🏦仓库:Github、Gitee ✏️博客:CSDN、掘金、InfoQ、云+社区 💌公众号:Java学术趴 🚫特别声明:原创不易,未经授权不得转载或抄袭,如需转载可联系小编授权。 🙏版权声明:文章里的部分文字或者图片来自于互联网以及百度百科,如有侵权请尽快联系小编。 👋大家好!我是你们的老朋友Java学术趴。任何的语言都离不开函数,都包括内置函数和自定义函数,函数的作用就是对功能进行封装以便于无效调用。 9.1 函数的基础 函数就是一段含有特殊功能的代码块 使用函数完成
Java学术趴
2022/06/03
7530
python干货——函数
python3--函数进阶
TypeError: func() missing 4 required keyword-only arguments: 'a', 'b', 'c', and 'd'
py3study
2018/08/02
5310
Python 变量作用域与函数
一个程序的所有的变量并不是在哪个位置都可以访问的,访问权限决定于这个变量是在哪里赋值的,变量的作用域决定了在哪一部分程序你可以访问哪个特定的变量名称,两种最基本的变量作用域,第一种是局部变量,第二种是全局变量.定义在函数内部的变量拥有一个局部作用域,定义在函数外的拥有全局作用域,而局部变量只能在其被声明的函数内部访问,全局变量则可以在整个程序范围内访问.
王 瑞
2022/12/28
2.6K0
5.0 Python 定义并使用函数
函数是python程序中的基本模块化单位,它是一段可重用的代码,可以被多次调用执行。函数接受一些输入参数,并且在执行时可能会产生一些输出结果。函数定义了一个功能的封装,使得代码能够模块化和组织结构化,更容易理解和维护。在python中,函数可以返回一个值或者不返回任何值,而且函数的参数可以是任何python对象,包括数字、字符串、列表、元组等。python内置了许多函数,同时也支持用户自定义函数。
王 瑞
2023/08/13
4020
Python函数用法
python中函数的参数有位置参数、默认参数、可变参数、命名关键字参数和关键字参数,这个顺序也是定 义函数时的必须顺序。
星陨1357
2023/03/14
4630
Python学习记录day3
2)list(),原理是调用__init__,内部执行for循环将元素添加到list中。
py3study
2020/01/03
3990
python基础3
 交换: a,b=b,a 相当于定义了一个元组t=(b,a) 然后将t[0]的值给了a,t[1]的值给了b ####字典#### 定义用花括号 集合定义若为空的话,会默认为字典,所以集合不能为空 子典只能通过关键字来查找值,因为字典是key-value(关键字-值),因此不能通过值来查找关键字 In [1]: dic = {"user1":"123","user2":"234","user3":"789"} In [3]: dic["234"] --------------------------------------------------------------------------- KeyError                                  Traceback (most recent call last) <ipython-input-3-2845b64d96b1> in <module>() ----> 1 dic["234"] KeyError: '234' 字典是一个无序的数据类型,因此也不能进行索引和切片等操作。 In [1]: dic = {"user1":"123","user2":"234","user3":"789"} In [2]: dic["user1"] Out[2]: '123' In [5]: dic["user2"] Out[5]: '234' In [7]: user = ['user1','user2','user3'] In [8]: passwd = ['123','234','456'] In [9]: zip(user,passwd) Out[9]: [('user1', '123'), ('user2', '234'), ('user3', '456')] In [10]: 当你有一个用户名单和密码,若使用列表的类型,判断用户是否和密码一致时,就比较麻烦,而使用字典时,只需通过关键子就可以返回相对应的值,(如上例子:当定义一个子典当你搜索user1时,字典类型就会返回该关键字对应的密码,此时只需判断该密码是否匹配即可) ####字典的基本操作### In [17]: dic. dic.clear       dic.items       dic.pop         dic.viewitems dic.copy        dic.iteritems   dic.popitem     dic.viewkeys dic.fromkeys    dic.iterkeys    dic.setdefault  dic.viewvalues dic.get         dic.itervalues  dic.update       dic.has_key     dic.keys        dic.values 字典添加 In [12]: dic Out[12]: {'user1': '123', 'user2': '234', 'user3': '789'} In [13]: dic["westos"]='linux' In [14]: dic Out[14]: {'user1': '123', 'user2': '234', 'user3': '789', 'westos': 'linux'} In [15]: dic["hello"]='world' In [16]: dic            ####由此可以看出字典是无序的,在添加时,并不会按照顺序往后添加#### Out[16]: {'hello': 'world',  'user1': '123',  'user2': '234',  'user3': '789',  'westos': 'linux'} In [17]: 字典更新 In [22]: dic Out[22]: {'hello': 'world', 'user1': '123', 'user2': '234', 'user3': '789'} In [23]: dic["user1"]="redhat"        ###可直接通过赋值对关键字进行更新### In [24]: dic Out[24]: {'hello': 'world', 'user1': 'redhat', 'user2': '234', 'user3': '789'} ###或者通过dic.update更新### In [25]: dic Out[25]: {'hello': 'world', 'user1': 'redhat', 'user2': '234', 'user3': '789'} In [26]: help(di
py3study
2020/01/03
4990
Python编程 函数的定义与参数
函数 只有在调用时才会执行,通过 function_name(param) 进行调用
网络豆
2023/10/15
2590
Python编程 函数的定义与参数
【愚公系列】2021年12月 Python教学课程 12-Python函数
函数(function)是用于完成特定任务的程序代码的自包含单元。在面向对象编程的类中,函数通常被称作方法。不同的函数在程序中扮演着不同的角色,起着不同的作用,执行不同的动作。比如 print()函数可以将对象打印到屏幕上;还有一些函数能够返回一个值以供程序使用,比如 len()将可计算长度的对象的元素个数返回给程序。
愚公搬代码
2021/12/14
5770
python第十四课--排序及自定义函数之自定义函数(案例五)
演示函数的定义和使用细节: 默认参数: #在设计自定义函数的时候,就存在一个默认值,就算在调用的时候不显示的传入实参,也不会报错。 #会用默认值来代替参与后期的运算
hankleo
2020/09/16
4020
[Python零基础入门篇③⓪] - 函数的定义与使用
什么是函数? --- > 函数是具有某种特定功能的代码块,可以重复使用(在前面数据类型相关章节,其实已经出现了很多 Python 内置函数了)。它使得我们的程序更加模块化,不需要编写大量重复的代码。
哈哥撩编程
2024/07/10
3080
[Python零基础入门篇③⓪] - 函数的定义与使用
006从零开始学Python—自定义函数
虽然Python的标准库中自带了很多“方法”或函数,并且第三方模块也提供了更多的现成"方法"与函数,但有时还是不能满足需求,这时就需要自定义函数了。另外,为了避免重复编写代码并使代码简洁易读,可以将常用的代码块封装为函数,在需要时调用函数即可。
1480
2019/05/22
8330
Python中函数的介绍
函数名:函数名是函数的标识符,用于唯一标识函数。在定义函数时,需要给函数一个名字,以便后续调用和引用。函数名应遵循命名规则,例如以字母或下划线开头,由字母、数字或下划线组成。命名规范可参考官网的PEP 8风格,地址如下:
小博测试成长之路
2023/09/01
4380
Python中函数的介绍
python函数基础学习
按关键字传值接收多个关键字参数,由 kwargs 接收,保存为一个字典(dict)的形式
Mirror王宇阳
2020/11/13
5850
python函数基础学习
Python基础知识点梳理
摘要: 本文主要介绍一些平时经常会用到的python基础知识点,用于加深印象,也算是对于学习这门语言的一个总结与回顾。python的详细语法介绍可以查看官方编程手册,也有一些在线网站对python语法进行了比较全面的介绍,比如菜鸟教程: python3 教程|菜鸟教程 为了方便聚焦知识点,本文涉及的操作实例并不多,想学好一门语言关键还得自己多编码多实践。
全栈程序员站长
2022/09/12
1.2K0
Python3 系列之 可变参数和关键字
对于可变参数可以联想到 C# 中的可变参数。可变参数是一个数量不确定的列表集合,可以是 list 类型,也可以是 tuple 类型 我们定义如下代码段:
py3study
2020/01/19
5510
Python的基础知识
布尔值也叫做布尔类型,总共有两个值,一个为True(真),一个为False(假),一般被用于逻辑判断
星陨1357
2023/03/14
7510
Python的基础知识
面试题集锦(一)
# 一、选择题(32分) # 1、python不支持的数据类型有(A) # A、char # B、int # C、float # D、list # 2.下列执行的结果是(E) # x = ‘foo’ x为字符串类型 # y = 2 y是int类型 # print(x+y) 不同类型的数据不可以相加 # A. foo B. foofoo C. foo2 D. 2 E.An exception is thrown
全栈程序员站长
2022/07/21
3100
【无痛学Python】基础语法3
在函数定义的时候, 可以在 ( ) 中指定 “形式参数” (简称 形参), 然后在调用的时候, 由调用者把 “实际参数” (简称 实参) 传递进去.
Skrrapper
2025/06/08
510
【无痛学Python】基础语法3
python第十四课--排序及自定义函数
1.排序 特点: 1).升序:从小到大 2).降序:从大到小 课堂实现选择排序:参看老郭选择排序.py文件 2.函数:(方法/method) 自定义函数: 概念:它表示一段作用范围(作用域),当中封装了一段业务逻辑代码,此范围有名字, 我们需要调用函数名,才能去执行它; 好处: 1).代码的复用性变强 2).代码的扩展性和维护性变好 3).代码的阅读性变好 函数有五要素: ①.函数修饰符:必须都是def开头 ②.函数返回值:函数执行完毕可能存在有返回值/没有返回值两种情况 ③.函数名:标识符(规则和规范),自己定义函数的名字 ④.形参列表定义在函数名后的小括号内,可以没有也可以定义多个 ⑤.函数体封装的功能代码 格式: ① ③(④): ⑤ ② 函数的内存执行过程: 栈: 特点:分为栈顶部分和栈底部分,满足先进后出,只运行栈顶的内容; 函数method一旦被执行了,先进栈(入栈) --> 在栈顶开辟空间执行, 如果执行到一半调用了别的函数method02,那么method就被压栈了(顶->底), method02在开辟空间执行,等到method02执行完毕了,它就被弹栈(出栈)了, 然后method01获取了执行权,它会先升栈(底->顶),到method执行完毕了,它就被弹栈(出栈)了 【注意事项】: 1).形式参数也称形参,实际参数也称实参 2).形式参数出现在定义函数的时候,没有具体的内容,只是开了个口 3).实际参数出现在函数调用的时候,将实际参数给到形式参数 --> 称为参数传递, 之后参与运算的全部都是实参而已 4).return关键字有两层含义: ①.表示函数的结束②.将结果返回给函数的调用者/调用处 5).python中没有函数重载的现象: 什么是函数重载? 在同一个作用范围内定义相同名字的函数,但是形参不同(个位、位置), 在调用函数的时候,通过传入的参数的不同,能得知到底需要执行哪一个函数 python中如果在相同的作用域中定义多个重名的函数, 最后的一个函数,会将之前所有的同名函数全部覆盖, 所以只能调用最后一个同名函数执行 6).与return同一作用范围内的后面不要显示的书写任何代码,因为永远不可能被执行到,不会报错 7).return后面也可以不定义任何有效的数据,但是这样会将None值返回给调用处,一般没有什么意义 4中最常见的自定义函数模型 1).无参无返回值 2).无参有返回值 3).有参无返回值 4).有参有返回值 参数的定义和使用细节: 分类: 1).默认参数: #在设计自定义函数的时候,就存在一个默认值,就算在调用的时候不显示的传入实参,也不会报错 #会用默认值来代替参与后期的运算
hankleo
2020/09/16
4280
相关推荐
python干货——函数
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档