資訊專(zhuān)欄INFORMATION COLUMN
Problem
esign a HashSet without using any built-in hash table libraries.
To be specific, your design should include these functions:
add(value): Insert a value into the HashSet.
contains(value) : Return whether the value exists in the HashSet or not.
remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.
Example:
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1); // returns true
hashSet.contains(3); // returns false (not found)
hashSet.add(2);
hashSet.contains(2); // returns true
hashSet.remove(2);
hashSet.contains(2); // returns false (already removed)
Note:
All values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashSet library.
class MyHashSet {
class Bucket {
ListNode head = new ListNode(-1);
}
class ListNode {
int key;
ListNode next;
ListNode(int key) {
this.key = key;
}
}
int size = 10000;
Bucket[] buckets = new Bucket[size];
int hash(int key) {
return key%size;
}
ListNode find(Bucket bucket, int key) {
ListNode head = bucket.head;
ListNode pre = head;
while (head != null && head.key != key) {
pre = head;
head = head.next;
}
return pre;
}
public void add(int key) {
int i = hash(key);
if (buckets[i] == null) buckets[i] = new Bucket();
ListNode pre = find(buckets[i], key);
if (pre.next == null) pre.next = new ListNode(key);
}
public void remove(int key) {
int i = hash(key);
if (buckets[i] != null) {
ListNode pre = find(buckets[i], key);
if (pre.next != null) pre.next = pre.next.next;
}
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
int i = hash(key);
if (buckets[i] != null) {
ListNode pre = find(buckets[i], key);
return pre.next == null ? false : true;
}
return false;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77181.html
摘要：題目鏈接題目分析設(shè)計(jì)一個(gè)哈希類(lèi)。需要有添加元素函數(shù)，判斷元素存在的函數(shù)，移除元素函數(shù)。思路這真的沒(méi)什么好說(shuō)的了我把要存的值作為數(shù)組的鍵存儲(chǔ)。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D87 705. Design HashSet 題目鏈接 705. Design HashSet 題目分析 設(shè)計(jì)一個(gè)哈希類(lèi)。 需要有add添加元素函數(shù)，contains判斷元素存在的函數(shù)，remov...
Problem Design a Phone Directory which supports the following operations: get: Provide a number which is not assigned to anyone.check: Check if a number is available or not.release: Recycle or release...
摘要：題目鏈接和基本一樣，都可以用，但是大了之后會(huì)有很多無(wú)效的時(shí)間保存在里面，要的話(huà)，可能需要遍歷或者用輔助，時(shí)間復(fù)雜度超過(guò)，所以用一個(gè)來(lái)做，每次根據(jù)新的改變。 359. Logger Rate Limiter 題目鏈接：https://leetcode.com/problems... 和Design Hit Counter基本一樣，都可以用hashmap，但是timestamp大了之后會(huì)有...
Problem Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure.find - Find if there exists any pair of number...
摘要：題目鏈接直接用一個(gè)，結(jié)果了看了加了個(gè)，不過(guò)感覺(jué)沒(méi)什么必要加，反正保存的都一樣，只是的時(shí)間大于，用可以保證?？戳祟}目條件是可以隨便返回一個(gè)值，但是不讓這么做。很無(wú)語(yǔ)啊如果這道題要求要求的是的，那就和一樣了。 Design Phone Directory 題目鏈接：https://leetcode.com/problems... 直接用一個(gè)set，結(jié)果tle了= = public clas...
閱讀 2814·2021-11-24 10:23
閱讀 1183·2021-11-17 09:33
閱讀 2539·2021-09-28 09:41
閱讀 1453·2021-09-22 15:55
閱讀 3669·2019-08-29 16:32
閱讀 1941·2019-08-29 16:25
閱讀 1079·2019-08-29 11:06
閱讀 3449·2019-08-29 10:55
