优秀个人网站,app软件开发培训班,太原注册公司网站,为什么要建设企业的微网站这是悦乐书的第299次更新#xff0c;第318篇原创01 看题和准备今天介绍的是LeetCode算法题中Easy级别的第167题(顺位题号是706)。在不使用任何内置哈希表库的情况下设计HashMap。具体而言#xff0c;你的设计应包括以下功能#xff1a;put(key#xff0c;value)#xff1a…这是悦乐书的第299次更新第318篇原创01 看题和准备今天介绍的是LeetCode算法题中Easy级别的第167题(顺位题号是706)。在不使用任何内置哈希表库的情况下设计HashMap。具体而言你的设计应包括以下功能put(keyvalue)将一个(keyvalue)对插入HashMap。如果该值已存在于HashMap中请更新该值。get(key)返回指定键映射到的值如果此映射不包含键的映射则返回-1。remove(key)如果此映射包含键的映射则删除值键的映射。例如MyHashMap hashMap new MyHashMap();hashMap.put(1,1);hashMap.put(2,2);hashMap.get(1); //返回1hashMap.get(3); //返回-1(未找到)hashMap.put(2,1); //更新现有值hashMap.get(2); //返回1hashMap.remove(2); //删除2的映射hashMap.get(2); //返回-1(未找到)注意所有key和value都将在[0,1000000]范围内。操作次数将在[1,10000]范围内。请不要使用内置的HashMap库。本次解题使用的开发工具是eclipsejdk使用的版本是1.8环境是win7 64位系统使用Java语言编写和测试。02 第一种解法为了实现键值对的效果内层使用了二维数组外层使用ArrayList。其中二维数组是一个一行两列的结构第一行第一列存储key的值第一行第二列存储value的值。另外我们还需要单独写一个contains方法来判断当前的key是否存在于HashMap中。put方法的时间复杂度为O(n)get方法的时间复杂度为O(n)remove的时间复杂度为O(n)contains方法的时间复杂度为O(n)。class MyHashMap {List list;/** Initialize your data structure here. */public MyHashMap() {list new ArrayList();}/** value will always be non-negative. */public void put(int key, int value) {if (contains(key)) {for (int[][] arr : list) {if (arr ! null arr[0][0] key) {arr[0][1] value;break;}}} else {list.add(new int[][]{{key, value}});}}public boolean contains(int key){for (int[][] arr : list) {if (arr ! null arr[0][0] key) {return true;}}return false;}/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */public int get(int key) {for (int[][] arr : list) {if (arr ! null arr[0][0] key) {return arr[0][1];}}return -1;}/** Removes the mapping of the specified value key if this map contains a mapping for the key */public void remove(int key) {if (contains(key)) {for (int i0; iif (list.get(i)[0][0] key) {list.remove(i);break;}}}}}/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap obj new MyHashMap();* obj.put(key,value);* int param_2 obj.get(key);* obj.remove(key);*/03 第二种解法我们也可以使用一个小track依旧使用数组但是变成了一维数组因为题目给定了key和value的范围所以数组的容量为其最大范围加1。因为最小值可以为0而数组默认值是0避免误判将数组的初始值全部赋值为-1。put方法的时间复杂度为O(1)get方法的时间复杂度为O(1)remove的时间复杂度为O(1)但是空间复杂度较高。class MyHashMap {int[] arr;/** Initialize your data structure here. */public MyHashMap() {arr new int[1000001];Arrays.fill(arr, -1);}/** value will always be non-negative. */public void put(int key, int value) {arr[key] value;}/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */public int get(int key) {return arr[key];}/** Removes the mapping of the specified value key if this map contains a mapping for the key */public void remove(int key) {arr[key] -1;}}/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap obj new MyHashMap();* obj.put(key,value);* int param_2 obj.get(key);* obj.remove(key);*/04 第三种解法class MyHashMap {/** Initialize your data structure here. */ListNode[] nodes;public MyHashMap() {nodes new ListNode[10000];}/** value will always be non-negative. */public void put(int key, int value) {int idx key%10000;if(nodes[idx]null){nodes[idx] new ListNode(-1,-1);nodes[idx].next new ListNode(key,value);}else{ListNode pre find(nodes[idx], key);if(pre.next null){pre.next new ListNode(key, value);}else{pre.next.value value;}}}/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */public int get(int key) {int idx key%10000;if(nodes[idx] null) return -1;else{ListNode pre find(nodes[idx], key);if(pre.next null) return -1;else return pre.next.value;}}public ListNode find(ListNode root, int key){ListNode pre null;ListNode cur root;while(cur!null cur.key ! key){pre cur;cur cur.next;}return pre;}/** Removes the mapping of the specified value key if this map contains a mapping for the key */public void remove(int key) {int idx key%10000;if(nodes[idx] null) return;else{ListNode pre find(nodes[idx], key);if(pre.next null) return;else{pre.next pre.next.next;}}}class ListNode{int key;int value;ListNode next;ListNode(int key, int value){this.key key;this.value value;}}}/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap obj new MyHashMap();* obj.put(key,value);* int param_2 obj.get(key);* obj.remove(key);*/05 小结算法专题目前已日更超过四个月算法题文章167篇公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词获取系列文章合集。以上就是全部内容如果大家有什么好的解法思路、建议或者其他问题可以下方留言交流点赞、留言、转发就是对我最大的回报和支持
