简阳电力建设立项网站,广东东莞划定多个高风险区,长治网站运营,网站主页设计素材1146. 快照数组 - 力扣#xff08;LeetCode#xff09; 实现支持下列接口的「快照数组」- SnapshotArray#xff1a; SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时#xff0c;每个元素都等于 0。void set(index, val) - 会将指定索引…1146. 快照数组 - 力扣LeetCode 实现支持下列接口的「快照数组」- SnapshotArray SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时每个元素都等于 0。void set(index, val) - 会将指定索引 index 处的元素设置为 val。int snap() - 获取该数组的快照并返回快照的编号 snap_id快照号是调用 snap() 的总次数减去 1。int get(index, snap_id) - 根据指定的 snap_id 选择快照并返回该快照指定索引 index 的值。 示例 输入[SnapshotArray,set,snap,set,get][[3],[0,5],[],[0,6],[0,0]]
输出[null,null,0,null,5]
解释
SnapshotArray snapshotArr new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5); // 令 array[0] 5
snapshotArr.snap(); // 获取快照返回 snap_id 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // 获取 snap_id 0 的快照中 array[0] 的值返回 5 提示 1 length 50000题目最多进行0 snap_id 我们调用 snap() 的总次数0 val 10^9 class SnapshotArray {HashMapInteger,HashMapInteger, Integer map new HashMapInteger,HashMapInteger, Integer();int count 0;public SnapshotArray(int length) {map.clear();HashMapInteger,Integer tmp new HashMapInteger,Integer();map.put(count,tmp);}public void set(int index, int val) {if(map.containsKey(count)) {map.get(count).put(index,val);} else {int num count-1;HashMapInteger,Integer tmp2 map.get(num);while(tmp2 null) {num--;tmp2map.get(num);}HashMapInteger,Integer tmp;tmp (HashMapInteger,Integer)tmp2.clone();tmp.put(index,val);map.put(count,tmp);}}public int snap() {count;return count-1;}public int get(int index, int snap_id) {int num snap_id;HashMapInteger,Integer tmp map.get(num);while(tmp null) {num--;tmp map.get(num);}if(tmp.containsKey(index)) {return tmp.get(index);} else {return 0;}}
}/*** Your SnapshotArray object will be instantiated and called as such:* SnapshotArray obj new SnapshotArray(length);* obj.set(index,val);* int param_2 obj.snap();* int param_3 obj.get(index,snap_id);*/ 每日一题今天是中等题。今天这道题其实博主本人只是用了模拟的方法熟悉Java的数据结构后去调用api而已。大家可以去题解看看更好的解法博主这里只作为参考当无法更快的时候更重要的是先解出题目。个人看法 首先读题。跟昨天的题目实际上差不多要求实现一个接口。其中含有SnapshotArray初始化函数getset方法以及snap的快照方法。题目所说的快照实际上就是所给snap_id时间点的数组状态。博主这里使用hashmap来映射snap和数组状态。这样使用就只需要直接去调api就可以了。用一个count来记录调用了几次snap也就是存了几次快照。初始化时可以先创建一个hashmap。对应的最开始的时候的数组。这里主要是让后面可以直接根据这里的hashmap来clone。 set的时候需要先判断是否是新的count因为新的count说明之前的数组状态已经定格了也就是就算之后再改变同个位置的值也需要返回旧数组状态的值。如果是新的要先clone旧的在新的中再去更新并更新map中的counthashmap对。不一定每一次都有新的值要放入如果没有新的值需要放入即便这时候拍快照也意味着和之前的状态是一样的所以可以直接一直往前找直到找到对应最近的快照再clone。 get的时候一样假如需要的snap_id对应的hashmap为空说明是没有变化的往前找到最近的不为空的hashmap就可以了如果没有对应的键说明没有修改过需要返回0。 这样这道题就可以解决了。 其实这里使用到了时间换空间的方法假如对于每个count都去创建hashmap的话到后面就会出现内存不够的错误观察到数量级只有50000次就可以用时间换空间的方法用循环往前找就可以了。
结果如下
