public int sumInSubArrays(int[] ints) {
if (ints == null || ints.length == 0) {
return 0;
}
return dfs(ints, 0);
}
public int dfs(int[] arrs, int n) {
int s = (n << 1) + 1;
int sum = 0;
if (s > arrs.length) {
return 0;
}
for (int i = 0; i < s; i++) {
sum += arrs[i];
}
int tmpSum = sum;
for (int i = s; i < arrs.length; i++) {
tmpSum += arrs[i] - arrs[i-s];
sum += tmpSum;
}
return sum + dfs(arrs, s);
}过程的表述
想实现这过程，有：
1，fast指针在和前面的元素不等的时候呢，我就加到nums[slow++]中去。
1，有k个的限制了。
for(int i = 0; i < n; i++) {
if(i > k) {
set.remove(nums[i-k]);
}
}2，对数据的连续字符串
可以对if(i > 0) {set.remove(nums[i])}
/**
* 需要2个条件:1，个数；2，种类要相等。
* @param s1
* @param s2
* @return
*/
public boolean checkInclusion(String s1, String s2){
char[] pattern = s1.toCharArray();
char[] text = s2.toCharArray();
int pLen = s1.length();
int tLen = s2.length();
int[] preF = new int[26];
int[] wFre = new int[26];
for (int i = 0; i < pLen; i++) {
preF[pattern[i]-'a']++;
}
int pCnt = 0;
for (int i = 0; i < pLen; i++) {
if (preF[i] > 0) {
pCnt++;
}
}
int left = 0, right = 0;
// 滑动窗口的字、符与s1对应相等的时候。
int winCnt = 0;
while(right < tLen) {
if(preF[text[right]-'a'] > 0) {
wFre[text[right]-'a']++;
if (wFre[text[right]-'a'] == preF[text[right]-'a']){
winCnt++;
}
}
right++;
while (pCnt == winCnt){
if (right- left == pLen){
return true;
}
if (preF[text[left]-'a'] > 0) {
wFre[text[left]-'a']--;
if (wFre[text[left]-'a'] < preF[text[left]-'a']) {
winCnt--;
}
}
left++;
}
}
return false;
}public int removeDuplicate(int[] nums) {
int n = nums.length;
if(n < 2) {
return 2;
}
int slow = 2,fast = 2;
while(fast < n) {
if(nums[slow-2] != nums[fast]){
nums[slow] = nums[fast];
slow++;
}
++fast;
}
return slow;
}
//原地修改数组，使得所有的元素只出现一次,因为是要的长度啊。
public int removeOne(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}//滑动窗口的题目了。有什么要注意的是什么？
public int limit(int[] nums, int limit) {
TreeMap<Integer> map = new TreeMap();
int n = nums.length;
int left = 0, right = 0;
int ret = 0;
while(right < n) {
map.put(nums[right], map.getOrDefalut(nums[right],0)+1);
while(map.lastKey()- map.firstKey() > limit) {
map.put(nums[left],map.get(nums[left])-1);
if(map.get(nums[left]) == 0) {
map.remove(nums[left]);
}
left++;
}
ret = Math.max(ret, right - left +1);
right++;
}
}
//随便一个数组，需要的什么呢？有一个limit数值。问题有1，对数据的延迟删除的。2，有一个makeBalance的问题是什么？需要不断的对数据的中点的移动啊。
对数据的处理呢？有的问题是说数据流进了。
public class Leet0203 {
public double[] medianWindow(int[] nums, int k) {
DualHeap dh = new DualHeap(k);
for (int i = 0; i < k; i++) {
dh.insert(nums[i]);
}
double[] ans = new double[nums.length-k+1];
ans[0] = dh.getMedian();
/*why */
for (int i = k; i < nums.length; i++) {
dh.insert(nums[i]);
dh.erase(nums[i-k]);
ans[i-k+1] = dh.getMedian();
}
return ans;
}
/*自己的问题是说?
* 1, 为啥要维持主的是delayed的map元素?
* */
private class DualHeap{
int k;
/*大根：元素小的一部分了*/
PriorityQueue<Integer> small;
/*小根：元素大的一部分的元素了*/
PriorityQueue<Integer> large;
/*why??？*/
Map<Integer, Integer> delayed;
private int smallSize, largeSize;
public DualHeap(int k) {
this.k = k;
/**@对于他的比较就是说。有-1就是小于的。默认是-1
*
* 就是一个降序的排序了；
* */
this.small = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
/*原来如此、底层要的是
* @{pre < post element}
* */
return o2.compareTo(o1);
}
});
/*
*升序了，需要的是什么呢？*/
this.large = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
this.smallSize = 0;
this.largeSize= 0;
this.delayed = new HashMap<>();
}
public double getMedian() {
return (k & 1) == 1 ? small.peek() :((double) small.peek()+large.peek())/2;
}
public void insert(int num) {
if (small.isEmpty() || num< small.peek()) {
small.offer(num);
++smallSize;
} else {
large.offer(num);
++largeSize;
}
makeBalance();
}
/**@需要自己对数据的模拟啊，不要这样因为我们知道，优先队列是不支持移出非堆顶元素这一操作的，
因此我们可以考虑使用「延迟删除」的技巧，即：就会出现了delayed的东西了.*/
public void erase(int num) {
delayed.put(num, delayed.getOrDefault(num,0) +1);
if (num < small.peek()) {
--smallSize;
if (num == small.peek()) {
prune(small);
}
}else {
--largeSize;
if (num == large.peek()) {
prune(large);
}
}
makeBalance();
}
/*function is to ? pop the heap element, and update the map
* 在 \texttt{prune(heap)}prune(heap)
* 完成之后，我们就可以保证 \textit{heap}heap
* 的堆顶元素是不需要被「延迟删除」的。
* */
public void prune(PriorityQueue<Integer> heap){
while(!heap.isEmpty()) {
/*延迟的删除，对要删除的尽量*/
int num = heap.peek();
if (delayed.containsKey(num)){
delayed.put(num, delayed.get(num)-1);
if (delayed.get(num) == 0) {
delayed.remove(num);
}
heap.poll();
} else{
break;
}
}
}
public void makeBalance(){
if (smallSize > largeSize+1) {
large.offer(small.poll());
--smallSize;
++largeSize;
/*small的peek有问题的*/
prune(small);
} else if (smallSize < largeSize){
small.offer(large.poll());
++smallSize;
--largeSize;
prune(large);
}
}
}
}有利用的是less。表明在lr的区间内有多少的字母没有达到k个字母了。
public int longestSubstringAnswer(String s, int k) {
int ret = 0;
int n = s.length();
for (int t = 1; t <= 26 ; t++) {
int l = 0, r = 0;
int[] cnt = new int[26];
int tot = 0;
int less = 0;
while (r < n) {
cnt[s.charAt(r)-'a']++;
if (cnt[s.charAt(r)-'a'] == 1) {
tot++;
less++;
}
if (cnt[s.charAt(r)-'a'] == k) {
less--;
}
while(tot > t) {
cnt[s.charAt(l)-'a']--;
if (cnt[s.charAt(l)-'a'] == 0) {
tot--;
less--;
}
}
l++;
}
if (less == 0) {
ret = Math.max(ret, r-l+1);
}
r++;
}
return ret;
}