Geeker第六题

待我称王封你为后i 2021-11-29 05:32 193阅读 0赞

其实这个题相对来说比较简单，只是需要借助特别的存储结构。

### 题目描述： ###

![20190722101956407.png][]    ![20190722103118484.png][]

### 题目解析： ###

有三个输入参数-N,M,T——分别表示计划表的时间范围、对计划表进行操作的次数和计划表考虑的书的数目（1~T编号）。

有三种类型的操作-1LRV,2LRV,0LR——分别表示：

1LRV——\[L，R\]的时间(闭区间)看序号V的书

2LRV——\[L，R\]的时间(闭区间)不序号V的书（如果之前有安排看，那么，就去掉V，否则不作处理）

0LR——\[L，R\]的时间(闭区间)，查看总共安排了几本书来看。

### 解题思路： ###

![20190722103046506.png][]

观察输入输出的要求，不使用数组结构；

输出是按照时间段（时间点的和）查询，不重复的书的数目，由此使用HashMap<K,V>形式，V由不重复值的Set集合来表示。

### 代码实现： ###

package javawork.geeker;
    
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.Set;
    
    public class Main6 {
    	int nb = 0;
    	static Map<Integer,Set<Integer>> listbT = new HashMap<>();
    	
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		long n = in.nextInt();
    		long m = in.nextInt();
    		int t = in.nextInt();
    		 
    		List<Integer> res = new LinkedList<>();
    		for(int i=0;i<m;i++) {
    			int opt = in.nextInt();
    			switch (opt) {
    			case 1: 
    				int l = in.nextInt();
    				int r = in.nextInt();
    				int v = in.nextInt();
    				LRV1( l, r, v);break;
    			case 2:
    				int l2 = in.nextInt();
    				int r2 = in.nextInt();
    				int v2 = in.nextInt();
    				LRV2( l2, r2, v2);break;
    			case 0:
    				int l0 = in.nextInt();
    				int r0 = in.nextInt();
    				res.add(LRV0( l0, r0));
    				break;
    			default:
    			}
    		}
    		Iterator<Integer> it = res.iterator();
    		while(it.hasNext()) {
    		System.out.println(it.next());
    		}
    
    	}
    	//操作1LRV
    	public static void LRV1(int l,int r,int v) {
    		for(int i=l-1;i<r;i++) {
    			
    			if(listbT.containsKey(i)) {
    			listbT.get(i).add(v);
    			}else {
    				Set<Integer> s = new HashSet<Integer>();
    				s.add(v);
    				listbT.put(i, s);
    				
    			}
    		}
    	}
    	//操作2LRV
    	public static void LRV2(int l,int r,int v) {
    		for(int i=l-1;i<r;i++) {
    			
    			if(listbT.containsKey(i)) {
    			Set<Integer> ls = listbT.get(i);
    			if(ls.contains(v))
    			ls.remove(v);
    			}
    		}
    	}
    	//操作0LR
    	public static int LRV0(int l,int r) {
    		Set<Integer> s = new HashSet<>();
    		for(int i=l-1;i<r;i++) {
    			if(listbT.containsKey(i)) {
    				Iterator<Integer> it = listbT.get(i).iterator();
    				while(it.hasNext()) {
    					s.add(it.next());
    				}
    			}
    		}
    		return s.size();
    	}
    }

### 注意问题： ###

做题时输出一直显示为0、0；现在发现错误应该是在：

listbT.put(i, new HashSet<Integer>(v));

是按照HashSet(int i)这种格式的初始化并不是用于添加赋值，而是初始化了容量大小，观察源码可知：

//初始化容量大小，加载因子用默认的
        public HashSet(int initialCapacity) {
            map = new HashMap<>(initialCapacity);
        }

HashSet底层是HashMap,初始化大小默认16，加载因子0.75。

[20190722101956407.png]: https://img-blog.csdnimg.cn/20190722101956407.png
[20190722103118484.png]: /images/20211129/14588dcbf55e4e8aa2c38dd5459976bd.png
[20190722103046506.png]: /images/20211129/58096be0950142acaaf92922c64e6587.png