Sliding Window - The Smallest Window II(AIZU) && Leetcode 76
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_B
For a given array a1,a2,a3,...,aNa1,a2,a3,...,aN of NN elements and an integer KK, find the smallest sub-array size (smallest window length) where the elements in the sub-array contains all integers in range [1,2,...,K1,2,...,K]. If there is no such sub-array, report 0.
Idea: two pointer. 1.one is left and another is right, start from 0
2.move right pointer first until finding all the elements satisfying the requirements
3.move left (narrowing the subarray) until break the(sum<k)
4.then move right (repeat 2,3)
5.end with two pointers move to end
import java.util.Scanner;
public class SmallestWindow2 {
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_A
//http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2692179#1 -- reference
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int K = in.nextInt();//target
int a[] = new int[n+1];
for(int i = 1; i<=n ;i++){
a[i] = in.nextInt();
}
int tag[] = new int[K+1];
//use two pointer
int p1 = 0, p2 = 0;
int min = n+1;//smallest size
int sum = 0;
//moving the pointer and check the sum < k
while(p1<=n){
//p2 = p1;
if(sum==K) {
min = Math.min(min, p2-p1);
//System.out.println(min);
}
//main body
//move right pointer
if(sum<K){
p2++;
if(p2>n) break;
if(a[p2] <= K){
if(tag[a[p2]]==0) sum++;
tag[a[p2]]++;
}
}else {
p1++;
if(p1>n) break;
if(a[p1]<=K){
tag[a[p1]]--;
if(tag[a[p1]]==0) sum--;
}
}
}
if(min == n+1) System.out.println(0);
else System.out.println(min);
}
}
folder: smallest window with two pointers
similar problems: the folder in AIZU(1-4)
leetcode problem https://leetcode.com/problems/minimum-window-substring/description/ -- 76
.................
leetcode problem 76 minimum window substring
follow up of the previous problem: 1.can find duplicate elements 2. string instead of numbers
For string: create the hashmap: key: char, value: integer
For duplicate number: create the original hashmap for conditions.
//if(num==0) sum++;
//if(num<1) sum++; // first appears or <
if(num<Tmap.get(c)) sum++;
map.put(c,++num);
the evolving process from the last to the current one and it is interesting that num id always >=0
class Solution {
public String minWindow(String s, String t) {
int K = t.length();
int N = s.length();
int L = -1,R = -1;
int left = -1, right = -1;
int sum = 0;// size of subarray of T
int ans = N+1;
Map<Character, Integer> map = new HashMap<Character, Integer>();
Map<Character, Integer> Tmap = new HashMap<Character, Integer>();
for(Character c : t.toCharArray()){
map.put(c,0);
if(Tmap.containsKey(c)){
Tmap.put(c,Tmap.get(c)+1);
}else Tmap.put(c,1);
}
while(true){
if(sum==K){
if(ans > (right-left)){
//ans = Math.min(ans, right-left);
ans = right-left;
L = left;
R = right;
}
}
if(sum<K){ //
right++;
if(right>=N) break;
//find the elements
char c = s.charAt(right);
if(map.containsKey(c)){
int num = map.get(c);
//if(num==0) sum++;
//if(num<1) sum++; // first appears or <
if(num<Tmap.get(c)) sum++;
map.put(c,++num);
}
}else{
left++;
if(left>=N) break;
char c = s.charAt(left);
if(map.containsKey(c)){
int num = map.get(c);
num--;
map.put(c,num);
//if(num==0) sum--;
//if(num<1) sum--;
if(num<Tmap.get(c)) sum--;
}
}
}
if((L==-1) && (R==-1) )
return "";
else return s.substring(L+1,R+1);
}
}
String: str.length(), str.toCharArray(), s.substring(), s.charAt();
Hashmap: map.containsKey(), map.put(key,value), map.get(key), map.entrySet, Map.entry<Key,Value>
最新文章
- CString转string
- Storm系列（二）：使用Csharp创建你的第一个Storm拓扑（wordcount）
- 转：python类型转换、数值操作
- java获取页面编码
- CentOS 5.5 下安装Countly Web Server过程记录
- asp程序调试
- JSP HTML区别
- KesionCMS V6.5后台拿SHELL方法
- genymotion模拟器配置Genymotion-ARM-Translation 兼容包
- Java中的Object、T（泛型）、?区别
- ubuntu make menuconfig error
- 微信小程序转发微信小程序转发
- 基于webpack的react脚手架
- JS对象复制(深拷贝、浅拷贝)
- 002.HAProxy安装及常见配置
- 51nod 1689 逛街（优先队列）
- [ ZooKeeper]ZooKeeper 的功能和原理
- PLT redirection through shared object injection into a running process
- PAT乙级1002
- Linux光标移动异常