Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2022/10/06 10:18)推噓4(4推 0噓 2→)

留言6則, 6人參與討論串30/719 (看更多)

981. Time Based Key-Value Store 設計一個資料結構，這個資料結構儲存key/value值，他可以接受相同key不同時間儲存不同value，實作以下功能： 1.TimeMap() 建構函數。 2.void set(String key, String value, int timestamp) 設定一個key/value鍵值對，且包含時間資訊。 3.String get(String key, int timestamp) 透過key獲得一個value值，若有多個value，向下取離timestamp最近的，若不存在key返回""。限制：所有輸入的timestamp都是嚴格遞增 Example 1: Input ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output [null, null, "bar", "bar", null, "bar2", "bar2"] Explanation TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2" 思路： 1.用兩層Map求解 2.第一層Map紀錄key/Map，第二層Map儲存time/value依據timestamp由大到小排序（用TreeMap排序） 3.set()操作就是若不存在key值直接new一個TreeMap然後放入key/value/time 若存在key值就把TreeMap拿出來一樣放入key/value/time 4.get操作先判斷有沒有key，不存在就返回"" 否則遍歷TreeMap由大找到小若存在 timestamp是小於輸入的就直接返回他的value Java Code： class TimeMap { Map<String, Map<Integer, String>> map; public TimeMap() { map = new HashMap<>(); } public void set(String key, String value, int timestamp) { if(!map.containsKey(key)) { Map<Integer, String> list = new TreeMap<>(Comparator.reverseOrder()); list.put(timestamp, value); map.put(key, list); } else { Map<Integer, String> list = map.get(key); list.put(timestamp, value); } } public String get(String key, int timestamp) { if(!map.containsKey(key)) return ""; Map<Integer, String> list = map.get(key); for(Map.Entry<Integer, String> entry : list.entrySet()) if(entry.getKey() <= timestamp) return entry.getValue(); return ""; } } 資料結構設計比較沒有一個標準解，來集思廣益一下ㄚ -- https://i.imgur.com/OTNN84M.jpg