|
| 1 | +// -------------------- Complex solution -------------------- |
| 2 | +// --------- LinkedList --------- |
| 3 | +typedefstructNode { |
| 4 | +intvalue; |
| 5 | +structNode*next; |
| 6 | +}Node; |
| 7 | + |
| 8 | +typedefstructLinkedListHead { |
| 9 | +Node*next; |
| 10 | +}LinkedListHead; |
| 11 | + |
| 12 | +Node*newNode(intkey) { |
| 13 | +Node*node= (Node*)malloc(sizeof(Node)); |
| 14 | +node->value=key; |
| 15 | +node->next=NULL; |
| 16 | +returnnode; |
| 17 | +} |
| 18 | + |
| 19 | +LinkedListHead*newLinkedList() { |
| 20 | +LinkedListHead*head= (LinkedListHead*)malloc(sizeof(LinkedListHead)); |
| 21 | +head->next=NULL; |
| 22 | +returnhead; |
| 23 | +} |
| 24 | + |
| 25 | +boollinkedListContains(LinkedListHead*head,intkey) { |
| 26 | +Node*currentNode=head->next; |
| 27 | +while (currentNode) { |
| 28 | +if (currentNode->value==key)return true; |
| 29 | +currentNode=currentNode->next; |
| 30 | + } |
| 31 | +return false; |
| 32 | +} |
| 33 | + |
| 34 | +voidlinkedListPush(LinkedListHead*head,intkey) { |
| 35 | +Node*node=newNode(key); |
| 36 | +node->next=head->next; |
| 37 | +head->next=node; |
| 38 | +} |
| 39 | + |
| 40 | +voidlinkedListRemove(LinkedListHead*head,intkey) { |
| 41 | +Node*previousNode=head->next; |
| 42 | +if (previousNode==NULL)return; |
| 43 | +if (previousNode->value==key) { |
| 44 | +head->next=previousNode->next; |
| 45 | +free(previousNode); |
| 46 | +return; |
| 47 | + } |
| 48 | +Node*currentNode=previousNode->next; |
| 49 | +while (currentNode) { |
| 50 | +if (currentNode->value==key) { |
| 51 | +previousNode->next=currentNode->next; |
| 52 | +free(currentNode); |
| 53 | +return; |
| 54 | + } |
| 55 | +currentNode=currentNode->next; |
| 56 | + } |
| 57 | +} |
| 58 | + |
| 59 | +voidfreeLinkedList(LinkedListHead*head) { |
| 60 | +Node*previousNode=head->next; |
| 61 | +if (previousNode) { |
| 62 | +Node*currentNode=previousNode->next; |
| 63 | +while (currentNode) { |
| 64 | +free(previousNode); |
| 65 | +previousNode=currentNode; |
| 66 | +currentNode=currentNode->next; |
| 67 | + } |
| 68 | +free(previousNode); |
| 69 | + } |
| 70 | +free(head); |
| 71 | +} |
| 72 | +// --------- LinkedList --------- |
| 73 | + |
| 74 | +// ----------- HashSet ---------- |
| 75 | +typedefstruct { |
| 76 | +LinkedListHead*head; |
| 77 | +}MyHashSet; |
| 78 | + |
| 79 | +#defineHASH_SET_DEFAULT_SIZE 10000 |
| 80 | + |
| 81 | +MyHashSet*myHashSetCreate() { |
| 82 | +MyHashSet*obj= |
| 83 | + (MyHashSet*)malloc(sizeof(MyHashSet)*HASH_SET_DEFAULT_SIZE); |
| 84 | +for (inti=0;i<HASH_SET_DEFAULT_SIZE;i++) { |
| 85 | +obj[i].head=newLinkedList(); |
| 86 | + } |
| 87 | +returnobj; |
| 88 | +} |
| 89 | + |
| 90 | +intgetHashPosition(intkey) {returnkey %HASH_SET_DEFAULT_SIZE; } |
| 91 | + |
| 92 | +voidmyHashSetAdd(MyHashSet*obj,intkey) { |
| 93 | +intpos=getHashPosition(key); |
| 94 | +if (obj[pos].head==NULL)obj[pos].head=newLinkedList(); |
| 95 | +if (!linkedListContains(obj[pos].head,key)) |
| 96 | +linkedListPush(obj[pos].head,key); |
| 97 | +} |
| 98 | + |
| 99 | +voidmyHashSetRemove(MyHashSet*obj,intkey) { |
| 100 | +linkedListRemove(obj[getHashPosition(key)].head,key); |
| 101 | +} |
| 102 | + |
| 103 | +boolmyHashSetContains(MyHashSet*obj,intkey) { |
| 104 | +LinkedListHead*head=obj[getHashPosition(key)].head; |
| 105 | +if (head==NULL||head->next==NULL)return false; |
| 106 | +returnlinkedListContains(head,key); |
| 107 | +} |
| 108 | + |
| 109 | +voidmyHashSetFree(MyHashSet*obj) { |
| 110 | +for (inti=0;i<HASH_SET_DEFAULT_SIZE;i++) |
| 111 | +if (obj[i].head!=NULL)freeLinkedList(obj[i].head); |
| 112 | +free(obj); |
| 113 | +} |
| 114 | +// ----------- HashSet ---------- |
| 115 | +// -------------------- Complex solution -------------------- |
| 116 | + |
| 117 | +// -------------------- Simpler and faster solution -------------------- |
| 118 | +typedefstruct { |
| 119 | +bool*values; |
| 120 | +}MyHashSet; |
| 121 | + |
| 122 | +MyHashSet*myHashSetCreate() { |
| 123 | +MyHashSet*obj= (MyHashSet*)malloc(sizeof(MyHashSet)); |
| 124 | +obj->values= (bool*)calloc(1000001,sizeof(bool)); |
| 125 | +returnobj; |
| 126 | +} |
| 127 | + |
| 128 | +voidmyHashSetAdd(MyHashSet*obj,intkey) {obj->values[key]= true; } |
| 129 | + |
| 130 | +voidmyHashSetRemove(MyHashSet*obj,intkey) {obj->values[key]= false; } |
| 131 | + |
| 132 | +boolmyHashSetContains(MyHashSet*obj,intkey) {returnobj->values[key]; } |
| 133 | + |
| 134 | +voidmyHashSetFree(MyHashSet*obj) {free(obj); } |
| 135 | +// -------------------- Simpler and faster solution -------------------- |
| 136 | + |
| 137 | +/** |
| 138 | + * Your MyHashSet struct will be instantiated and called as such: |
| 139 | + * MyHashSet* obj = myHashSetCreate(); |
| 140 | + * myHashSetAdd(obj, key); |
| 141 | +
|
| 142 | + * myHashSetRemove(obj, key); |
| 143 | +
|
| 144 | + * bool param_3 = myHashSetContains(obj, key); |
| 145 | +
|
| 146 | + * myHashSetFree(obj); |
| 147 | +*/ |