public int partition(int[] nums, int l, int r){
int left = l, right = r, pivot = nums[left];
while(left < right){
while(left < right && nums[right] >= pivot){
right --;
}
nums[left] = nums[right];
while(left < right && nums[left] <= pivot){
left ++;
}
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
quick sort 模板
public void sortIntegers2(int[] A) {
quickSort(A, 0, A.length - 1);
}
private void quickSort(int[] A, int start, int end) {
if (start >= end) {
return;
}
int left = start, right = end;
// key point 1: pivot is the value, not the index
int pivot = A[(start + end) / 2];
// key point 2: every time you compare left & right, it should be
// left <= right not left < right
while (left <= right) {
// key point 3: A[left] < pivot not A[left] <= pivot
while (left <= right && A[left] < pivot) {
left++;
}
// key point 3: A[right] > pivot not A[right] >= pivot
while (left <= right && A[right] > pivot) {
right--;
}
if (left <= right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left++;
right--;
}
}
quickSort(A, start, right);
quickSort(A, left, end);
}
前向型或者追击型
窗口类 ->子串子数组可以往窗口类想 substring，subarray
快慢类
窗口类 vs sliding window
sliding window 的窗口大小固定.窗口类就是找个窗口 满足某条件，窗口最大或者最小
固定长度模板：K-Substring with K different characters(sliding window)
模板不能做这个Longest Substring with At Least K Repeating Characters（递归）
int findSubstring(string s){
vector<int> map(128,0);
int counter; // check whether the substring is valid
int begin=0, end=0; //two pointers, one point to tail and one head
int d; //the length of substring
for() { /* initialize the hash map here */ }
while(end<s.size()){
if(map[s[end++]]-- ?){ /* modify counter here */ }//pre临界这里，完了就被减
,map和end都要update,只有counter在if里
while(/* counter condition */){
/* update d here if finding minimum*/
//increase begin to make it invalid/valid again
if(map[s[begin++]]++ ?){ /*modify counter here*/ }//map和end都要update,只有counter在if里
}
/* update d here if finding maximum*/
}
return d;
}