poj3320Jessica's Reading Problem—尺取法(java)

题目链接

大意：给序列数字，找出最小子序列，包含所有的元素类型。例如
5
1 8 8 8 1
输出2，因为1 8就包含了所有元素

思路：尺取法

• 这个和裸的尺取优点不同的是，他需要一个map来维护判断而不是sum维护判断。在右侧从左向右遍历的同时，用一个map<Integer,Integer>来维护元素，map.keyset()就可以判断是否包含所有元素，数值用来判断改元素出现次数是否应移除改元素—左侧标记右移的时候判断。
• 所以具体的解题方法是：left,right=0,right向右遍历，向map中添加元素（数量等信息），如果包含了所有元素，那么left右移，对应改变map，一直到map不包含所有为止。然后右侧继续—

附上代码：

package 暴力;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class poj3320 {

	public static void main(String[] args) throws IOException {
		// TODO 自动生成的方法存根
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();int p=(int)in.nval;
		int value[]=new int[p];
		Map<Integer, Integer>map=new HashMap<Integer,Integer>();
		Set<Integer>set=new HashSet<Integer>();
		for(int i=0;i<p;i++)
		{ in.nextToken(); value[i]=(int)in.nval; set.add(value[i]);
		}
		int l=0;int len=p-1;
		map.put(value[0], 1);
		for(int i=1;i<p;i++)
		{ if(map.containsKey(value[i])) {map.put(value[i], map.get(value[i])+1);} else map.put(value[i],1); while(map.keySet().size()==set.size()) { if(i-l<=len) {len=i-l;} if(map.get(value[l])>1) {map.put(value[l], map.get(value[l])-1);} else map.remove(value[l]); if(l<i) l++; }
		} out.println(len+1);
		out.flush();
	}

}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
 

• 如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/88673080