資訊專欄INFORMATION COLUMN
Problem
The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:
size=3, capacity=4
[null, 21, 14, null]
↓ ↓
9 null
↓
null
The hash function is:
int hashcode(int key, int capacity) {
return key % capacity;
}
here we have three numbers, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.
rehashing this hash table, double the capacity, you will get:
size=3, capacity=8 index: 0 1 2 3 4 5 6 7 hash : [null, 9, null, null, null, 21, 14, null]
Given the original hash table, return the new hash table after rehashing .
NoticeFor negative integer in hash table, the position can be calculated as follow:
C++/Java: if you directly calculate -4 % 3 you will get -1. You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
Python: you can directly use -1 % 3, you will get 2 automatically.
Given [null, 21->9->null, 14->null, null],
return [null, 9->null, null, null, null, 21->null, 14->null, null]
Note Solution public class Solution {
public ListNode[] rehashing(ListNode[] hashTable) {
if (hashTable == null || hashTable.length == 0) return hashTable;
int cap = hashTable.length*2;
ListNode[] res = new ListNode[cap];
ListNode[] temp = new ListNode[cap];
for (int i = 0; i < cap/2; i++) {
ListNode cur = hashTable[i];
while (cur != null) {
ListNode node = new ListNode(cur.val);
hashTable[i] = cur.next;
int index = (cur.val%cap + cap)%cap;
if (res[index] == null) {
res[index] = node;
temp[index] = node;
}
else {
temp[index].next = node;
temp[index] = node;
}
cur = cur.next;
}
}
return res;
}
};
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65747.html
摘要：劍指最小棧聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處解題思路實(shí)現(xiàn)功能實(shí)現(xiàn)一個(gè)最小棧，要求操作均為復(fù)雜度，解題思路用棧存儲(chǔ)數(shù)據(jù)用最小棧存儲(chǔ)中最小元素，保證棧頂元素與棧頂元素同步，表示此時(shí)最小值將與此時(shí)最小值比較，將更小的一方壓棧，保證中棧頂始終 劍指offer/LintCode12_最小棧 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處https://segmentfault.com/u/yz...
摘要：劍指用兩個(gè)棧模擬隊(duì)列聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處解題思路實(shí)現(xiàn)功能用兩個(gè)棧模擬實(shí)現(xiàn)一個(gè)隊(duì)列的，和操作解題思路假設(shè)有兩個(gè)棧隊(duì)列實(shí)現(xiàn)始終用入棧實(shí)現(xiàn)隊(duì)列和實(shí)現(xiàn)由于依次出棧并壓入中，恰好保證中順序與模擬隊(duì)列順序一致，始終保證棧頂元素為模擬 劍指offer/LintCode40_用兩個(gè)棧模擬隊(duì)列 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處https://segmentfault.com...
摘要：劍指用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處解題思路實(shí)現(xiàn)功能用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧，實(shí)現(xiàn)，，和方法解題思路假設(shè)有隊(duì)列和實(shí)現(xiàn)棧的操作實(shí)現(xiàn)棧操作始終用來(lái)入隊(duì)實(shí)現(xiàn)實(shí)現(xiàn)棧的方法模擬棧的過(guò)程中，保證兩個(gè)隊(duì)列中始終有一個(gè)隊(duì)列為空，另一 劍指offer/LintCode494_用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處https://segmentfault....
摘要：劍指緩存實(shí)現(xiàn)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處解題思路緩存兩種功能獲取的對(duì)應(yīng)，不存在返回版本版本設(shè)置緩存已滿，刪除最近最久未被使用的節(jié)點(diǎn)，添加新節(jié)點(diǎn)進(jìn)緩存緩存未滿，節(jié)點(diǎn)存在，修改節(jié)點(diǎn)不存在，添加新節(jié)點(diǎn)進(jìn)緩存解題思路由于緩存插入和刪除 劍指offer/LeetCode146/LintCode134_LRU緩存實(shí)現(xiàn) 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處[1] https://s...
閱讀 2831·2021-09-28 09:45
閱讀 1507·2021-09-26 10:13
閱讀 897·2021-09-04 16:45
閱讀 3661·2021-08-18 10:21
閱讀 1084·2019-08-29 15:07
閱讀 2633·2019-08-29 14:10
閱讀 3147·2019-08-29 13:02
閱讀 2459·2019-08-29 12:31
