• Shopee đêm nay có mã cho ngày 5/5

thảo luận Leetcode mỗi ngày

freedom.9 said:
leetcode.com

clonemaasterUwU - LeetCode Profile

View clonemaasterUwU's profile on LeetCode, the world's largest programming community.
leetcode.com
Đâu thấy ông nào ở Voz là ClonemaasterUwU đâu nhỉ? À bác này hả @clonemasteruwu vô chia sẻ kinh nghiệm học leetcode cho ae đi bác :ah:
Click to expand...
step 1: has 150 iq
cgE9MkI.gif

step 2: profit
XgR55w2.gif
 
freedom.9 said:
leetcode.com

clonemaasterUwU - LeetCode Profile

View clonemaasterUwU's profile on LeetCode, the world's largest programming community.
leetcode.com
Đâu thấy ông nào ở Voz là ClonemaasterUwU đâu nhỉ? À bác này hả @clonemasteruwu vô chia sẻ kinh nghiệm học leetcode cho ae đi bác :ah:
Click to expand...
chie thất nghiệp mới học leetcode thôi bác 8-) đến cơ quan chửi sếp, lên mạng nói xấu cty là có động lực cày ngay ấy mà
 
Cái bài hôm nay ối dồi ôi quá, làm ngôn ngữ nào khác chứ JS thì hehehe :ops:
À mà ko đc, chơi object thì khác mẹ gì hashmap đâu, mấy engine lớn nhất đều implement hashtable cho object rồi :ops:
 
Last edited:
chào ngày mới
JavaScript: 
var MyHashMap = function () {
  this.obj = {}
};

/**
* @param {number} key
* @param {number} value
* @return {void}
*/
MyHashMap.prototype.put = function (key, value) {
  this.obj[key] = value;
};

/**
* @param {number} key
* @return {number}
*/
MyHashMap.prototype.get = function (key) {
  if (key in this.obj) {
    return this.obj[key]
  }
  return -1
};

/**
* @param {number} key
* @return {void}
*/
MyHashMap.prototype.remove = function (key) {
  delete this.obj[key]
};

/**
* Your MyHashMap object will be instantiated and called as such:
* var obj = new MyHashMap()
* obj.put(key,value)
* var param_2 = obj.get(key)
* obj.remove(key)
*/

không ngờ top runtime lại implement bằng Map, thế thì cần gì phải làm nữa đâu :eek:
 
logachune said:
chào ngày mới
JavaScript: 
var MyHashMap = function () {
  this.obj = {}
};

/**
* @param {number} key
* @param {number} value
* @return {void}
*/
MyHashMap.prototype.put = function (key, value) {
  this.obj[key] = value;
};

/**
* @param {number} key
* @return {number}
*/
MyHashMap.prototype.get = function (key) {
  if (key in this.obj) {
    return this.obj[key]
  }
  return -1
};

/**
* @param {number} key
* @return {void}
*/
MyHashMap.prototype.remove = function (key) {
  delete this.obj[key]
};

/**
* Your MyHashMap object will be instantiated and called as such:
* var obj = new MyHashMap()
* obj.put(key,value)
* var param_2 = obj.get(key)
* obj.remove(key)
*/

không ngờ top runtime lại implement bằng Map, thế thì cần gì phải làm nữa đâu :eek:
Click to expand...
bài này phải tự viết hash hoặc dùng array chứ chơi object thì khác gì map đâu :burn_joss_stick:
 
lười xử lý collision phang luôn vector 1e6 phần tử
C++: 
class MyHashMap {
public:
    vector<int> data;
    MyHashMap(): data((long)1e6 + 1, -1){
       
    }
   
    void put(int key, int value) {
        data[key] = value;
    }
   
    int get(int key) {
        return data[key];
    }
   
    void remove(int key) {
        data[key] = -1;
    }
};
 
Ngồi khổ dâm viết BST mà nó ko ăn hết test cases các fence ơi kaka. Tìm ko ra bug trong code mình
C#: 
public class MyHashMap {
    SupperTreeNode root;
    public MyHashMap() {
     
    }

    public void Put(int key, int value) {
      this.root = InsertNode(this.root, key, value);
    }
 
    public int Get(int key) {
        SupperTreeNode cur = this.root;
        while (cur != null) {
            if(key == cur.key)
            {
                return cur.val;
            }
            if (key < cur.key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return -1;
    }
 
    public void Remove(int key) {
        this.root = DeleteNode(this.root, key);
    }

    private SupperTreeNode InsertNode(SupperTreeNode root, int key, int val)
    {
        if(root == null)
            return new SupperTreeNode(key, val, null, null);
 
        if(key < root.key)
        {
           root.left = InsertNode(root.left, key, val);
        }else if(key == root.key)
        {
            root.val = val;
        }
        else{
            root.right = InsertNode(root.right, key, val);
        }
     
        return root;
    }

     private SupperTreeNode DeleteNode(SupperTreeNode root, int key) {
        if(root == null)
            return null;
     
        if(key <  root.key )
            root.left = DeleteNode(root.left, key);
     
        else if(key > root.key)
            root.right = DeleteNode(root.right, key);
     
        else {
            if(root.left == null)
                return root.right;
         
            else if(root.right == null)
            {
               return root.left;
            }
            else{
                var item = successor(root);
                root.key = item.key;
                root.val = item.val;
                [B]root.right = DeleteNode(root.right, root.val); => Sai ở đây[/B]
            }
        }
     
        return root;
    }
 
     private (int key, int val) successor(SupperTreeNode root) {
        root = root.right;
            while (root.left != null) root = root.left;
            return (root.key, root.val);
        }
}

public class SupperTreeNode{
    public int key;
    public int val;
    public SupperTreeNode left;
    public SupperTreeNode right;
    public SupperTreeNode(int key, int val, SupperTreeNode left, SupperTreeNode right)
    {
        this.key = key;
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * 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);
 */
À thấy bug rồi kaka
root.right = DeleteNode(root.right, root.key) mới đúng :ah:
 
Khởi tạo mảng a 10^6, value -1.
remove thì gán lại giá trí -1, get thì trả giá trị a, put thì a = v.
  • 0 <= key, value <= 106
  • At most 104 calls will be made to put, get, and remove.
 
nchhnchh said:
Khởi tạo mảng a 10^6, value -1.
remove thì gán lại giá trí -1, get thì trả giá trị a, put thì a = v.
  • 0 <= key, value <= 106
  • At most 104 calls will be made to put, get, and remove.
Click to expand...
Cách này ko tối ưu cho những TH key cực to. Chẳng hạn như key = 1 tỷ.
 
freedom.9 said:
Bình thường thì mấy ngôn ngữ tụi nó implement cái data structure HashMap với O(1) như thế nào nhỉ các fence?
Click to expand...
java: jdk/src/java.base/share/classes/java/util/HashMap.java at master · openjdk/jdk (https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashMap.java)
python thì chắc cái này, xài nhiều mà đó giờ cũng chưa đọc thử :v
python: cpython/Objects/dictobject.c at main · python/cpython (https://github.com/python/cpython/blob/main/Objects/dictobject.c)
 
freedom.9 said:
Bình thường thì mấy ngôn ngữ tụi nó implement cái data structure HashMap với O(1) như thế nào nhỉ các fence?
Click to expand...
Như JS chỉ có language specification cho Map(). Còn việc implemetation thế nào là do engine như v8, SpiderMonkey làm.
Ví dụ như đây là cách mà v8 implement hashtable cho các DS như Map, Set, WeakMap, WeakSet

Optimizing hash tables: hiding the hash code · V8

Several JavaScript data structures such as Map, Set, WeakSet, and WeakMap use hash tables under the hood. This article explains how V8 v6.3 improves hash table performance.
v8.dev
 
Hỏi chat GPT, hình như nó ko phải là true O(1) như mình nghĩ mà cũng kiểu modulo, rồi collision handling như anh em mình hay code mấy bài kiểu này thôi haha. Giải Algorithm mới hay để ý chứ xài quen tay ko biết bản chất bên trong như nào :ah: như cái solution của Java mình vào đọc thử thấy tụi nó xài LinkedList luôn
nchhnchh said:
java: jdk/src/java.base/share/classes/java/util/HashMap.java at master · openjdk/jdk (https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashMap.java)
python thì chắc cái này, xài nhiều mà đó giờ cũng chưa đọc thử :v
python: cpython/Objects/dictobject.c at main · python/cpython (https://github.com/python/cpython/blob/main/Objects/dictobject.c)
Click to expand...
  1. Hash Table: The core data structure used by Dictionary<TKey, TValue> is a hash table. A hash table is an array of buckets, and each bucket can hold multiple key-value pairs. The number of buckets is typically determined based on the initial capacity provided when creating a Dictionary. The hash table allows for efficient lookups, insertions, and deletions.
  2. Hash Function: When you add a key-value pair to the dictionary using Add or TryAdd, a hash function is applied to the key to determine the index (bucket) in which to store the value. The hash function is designed to distribute keys evenly across the array of buckets.
  3. Collision Handling: Hash collisions occur when two different keys produce the same hash code and attempt to map to the same bucket. Dictionary<TKey, TValue> handles collisions using a technique called "chaining." Each bucket in the hash table can contain a linked list (or similar data structure) of key-value pairs. When a collision occurs, a new key-value pair is simply added to the linked list in the corresponding bucket.
  4. Load Factor and Resizing: To maintain efficiency, Dictionary<TKey, TValue> monitors a load factor, which is the ratio of the number of stored items to the number of buckets. When the load factor exceeds a certain threshold, the dictionary automatically resizes itself, creating a larger array of buckets and rehashing existing key-value pairs into the new array. This helps prevent excessive collisions and ensures that the dictionary's performance remains relatively constant.
  5. Key Comparisons: To handle hash collisions correctly, Dictionary<TKey, TValue> relies on comparing keys using the EqualityComparer<TKey>.Default or a custom provided comparer. The comparer is responsible for determining whether two keys are equal.
  6. Efficient Retrieval: When you retrieve a value from a Dictionary<TKey, TValue> using a key, the hash code of the key is computed, and the corresponding bucket is accessed. If the bucket contains a linked list of key-value pairs, the appropriate pair is found by comparing keys.
  7. Thread Safety: Dictionary<TKey, TValue> is not thread-safe for concurrent read-write operations. If you need thread safety, you can use the ConcurrentDictionary<TKey, TValue> class, which provides thread-safe operations.
 
Bình thường thì mấy ngôn ngữ tụi nó implement cái data structure HashMap với O(1) như thế nào nhỉ các fence?
Bản chất nó là arr, hash cái key rồi lưu value tại cái index = hash đó. truy xuất O(1) :love:

Như mấy cái arr 26 cũng là một dạng hash map đấy
 
JavaScript: 
class MyHashMap {
    constructor() {
        this.arr = Array(1337);
    }
    put(k, v) {
        const kk = k % 1337;
        this.arr[kk] ??= [];
        for (const it of this.arr[kk]) {
            if (it[0] === k) {
                it[1] = v;
                return;
            }
        }
        this.arr[kk].push([k, v]);
    }
    get(k) {
        const kk = k % 1337;
        for (const it of (this.arr[kk] ?? [])) {
            if (it[0] === k) {
                return it[1];
            }
        }
        return -1;
    }
    remove(k) {
        const kk = k % 1337;
        if (!this.arr[kk]) {
            return;
        }
        this.arr[kk] = this.arr[kk].filter(it => it[0] !== k);
    }
}
 

Similar threads

Masterchiefs
8 tờ báo Mỹ kiện OpenAI và Microsoft
Replies
9
Views
659
porpro84
porpro84
T
kiến thức Kèo play to earn miễn phí - Delabs Game
Replies
4
Views
87
Tranviethai98
T
T
kiến thức Kèo play to earn miễn phí - Delabs Games
Replies
4
Views
163
Tranviethai98
T
elementary
Ta thay đổi trước khi Google thay đổi
2 3
Replies
58
Views
4K
ProfessorX
ProfessorX
Masterchiefs
Núi lửa ở Nam Cực phun vàng thật mỗi ngày
2
Replies
24
Views
3K
xuccam2
xuccam2

Share this page

Back
Top