1. Sliding Window
找出通用子数列（给定数列包含“2”，“4”如“【2，2，4，4，2，4，4】）
一个通用子数列满足以下两个条件
一：子数列是连续的，即从原数列里按顺序取出的子集合)，eg.
[2],[2],[4],[4],[2],[4],[4],[2,2],[2,4],[4,4]…[2,2,4],[2,4,4],等，[2,4,4,2]就不属于这类，因为“2”不连续在一起。
二：子数列中“2”与“4”的个数是相同的：24，42，2244，24,这类属于universal subarray.
写一个函数根据传递的array找到对应universal array的个数。
分析：
这是一个典型的sliding window类型的题,下图是我们的整体思路，初始化一个sliding window， from 指针为0，to 指针为-1,代表最初的sliding window为空，endofsliding=0 代表起始的sliding window里最后一个元素为0，这里可以设置为任何不为2或4的元素，segement代表sliding window里的数字片段，如22，2，222，连续相同的数字为一个片段，不同的数字加入，且加入的数字和sliding window的最后一个元素endofsliding不同的时候片段segement自增，初始化一个长度为2的数组，分别用于存储2或4在sliding window里的个数，我们的slidingwindow设置为扩张到两个片段且下一个元素与sliding window的endofsliding不一样时停止，此时一个sliding window扩张完毕，我们可以对第一个sliding window计算universal array的个数里，不难发现，一个sliding window里的universal array的个数与这个window里出现的字符个数次数最小的字符的个数相同，ru
24->1,224->1,2244->2,22444->2,且我们对这个sliding
window计算universal array的个数实际上是对这个sliding里的包含第一个片段的可能的universal array个数，于是乎，当我们计数完毕后，我们应该将第一个片段的数字都抛出这个sliding window，将slidingwindow的片段缩减到1，将from 前移至下一个片段，然后再次扩张slidingwindow，至sliding window的segement 再次为2，再次计算接下来的通用数组个数，以此类推，直至整个数组遍历完毕。
根据上面的分析可以写出这样的代码：
Class CountUniversalArray{
Int segment,from,to,end,total;
Int [] arr;
Int countUniversalArrayNumber(int [] array){
Segment= 0; from=0;to=-1;end=0; total=0;
arr =new int[2];
list =array;
while(expand()){
shrink();
}
Booleanexpand(){
//扩张条件是to 要小于数组index最大，即length-1; segment不能//大于2，或者是已经为2了，但是sliding的最后一个元素与下一个//数组元素相等时还能扩张：
while((segment<2|| (segment ==2 && end == list.get(to+1))) && to
to++;
//获取当前的数组元素：
Intn = list.get[to]；
Intj = n==2?0:1;
Arr[j]++;
If(end != n){
Segment++;
End = n;
}
}
Total += Math.min(arr[0],arr[1]);
Return segment == 2;
}
Void shrink(){
While(from
Int k = list.get(from)==2?0:1;
from ++;
arr[k]--;
if(arr[k] ==0){
seg--;
}
}
}
}
}
网友评论