首页 > 试题广场 >

设计有setAll功能的哈希表

[编程题]设计有setAll功能的哈希表

热度指数：2377 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

哈希表常见的三个操作时put、get和containsKey，而且这三个操作的时间复杂度为O(1)。现在想加一个setAll功能，就是把所有记录value都设成统一的值。请设计并实现这种有setAll功能的哈希表，并且put、get、containsKey和setAll四个操作的时间复杂度都为O(1)。

[友情提示]: C++选手若有需要可以使用unordered_map替换map来将复杂度从O(log n)降为O(1)

输入描述:

第一行一个整数N表示操作数。
接下来N行，每行第一个数字opt代表操作类型
若opt=1，接下来有两个整数x, y表示设置key=x对应的value=y
若opt=2，接下来一个整数x，表示查询key=x对应的value，若key=x不存在输出-1
若opt=3，接下来一个整数x，表示把加入过的所有的key对应的value都设置为x

输出描述:

对于每个操作2，输出一个整数表示答案

示例1

输入

输出

2
-1
4
-1

备注:

算法知识视频讲解

Java

我吵醒闹钟

# 难点在于命令二的查询和命令三的赋值，
# 为了保证命令三的高效，选择了过期时间机制对其时间内统一给replace
# 于是在命令二查询时，多加个过期判断

import java.io.*;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main_1732345057357 {
    final static Map<Long, long[]> map = new HashMap<>();
    static long expire = 0;
    static long replace = 0;


    public static void main(String[] args) throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        StringBuilder res = new StringBuilder();
        String[] s = null;
        while (n-- > 0) {
            s = reader.readLine().split(" ");
            if (s[0].equals("1")) {
                long k = Long.parseLong(s[1]);
                long v = Long.parseLong(s[2]);
                map.put(k, new long[]{v, expire});
            } else if (s[0].equals("2")) {
                long k = Long.parseLong(s[1]);
                if (map.containsKey(k)) {
                    long[] ll = map.get(k);
                    if (ll[1] >= expire) {
                        res.append(ll[0]).append('\n');
                    } else {
                        res.append(replace).append('\n');
                    }
                } else {
                    res.append(Long.valueOf(-1)).append('\n');
                }
            } else if (s[0].equals("3")) {
                replace = Long.parseLong(s[1]);
                expire++;
            }
        }
        System.out.print(res.toString());
    }
}

发表于 2025-01-28 00:54:51 回复(0)

Java

牛客196305255号

一个map,一个set配合即可。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            Map<Integer,Integer> map=new HashMap<>();
            Set<Integer> set=new HashSet<>();
            StringBuilder sb=new StringBuilder();
            int allVal=0;
            int n=sc.nextInt();
            for(int i=0;i<n;i++){
                int op=sc.nextInt();
                if(op==1){
                    int key=sc.nextInt();
                    int val=sc.nextInt();
                    map.put(key,val);
                    set.add(key);
                }else if(op==2){
                    int key=sc.nextInt();
                    if(map.containsKey(key))
                        sb.append(map.get(key));
                    else if(set.contains(key))
                        sb.append(allVal);
                    else
                         sb.append(-1);
                    sb.append("\n");
                }else if(op==3){
                    map.clear();
                    allVal=sc.nextInt();
                }
            }
            System.out.println(sb.toString());
        }
        sc.close();
    }
    
}

发表于 2021-04-08 12:15:01 回复(0)

Java

眼睛想旅行121

import java.util.*;
import java.io.*;
import java.io.*;
import java.util.*;
 
class newHash{
    private Map<String,myValue> hm;
    private long time;
    private myValue allv;
    public newHash(){
        hm = new HashMap();
        time = 0;
    }
    public void put(String key,String value){
        hm.put(key,new myValue(value,this.time++));
    }
    public String get(String key){
        myValue res = hm.get(key);
        if(res==null){
            return "-1";
        }else{
            if(allv!=null && allv.time>res.time){
                return allv.value;
            }else{
                return res.value;
            }
        }
    }
    public void setAll(String value){
        allv = new myValue(value,this.time++);
    }
}
 
class myValue{
    String value;
    long time;
    public myValue(String v,long t){
        this.value=v;
        this.time=t;
    }
}
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        newHash nh = new newHash();
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++){
            String[] s = br.readLine().split(" ");
            switch(s[0]){
                case "1":  nh.put(s[1],s[2]);break;
                case "2":  sb.append(nh.get(s[1])+"\n");break;
                case "3":  nh.setAll(s[1]);break;
            }
        }
        System.out.print(sb.toString());
    }
}

发表于 2021-03-05 09:18:44 回复(0)