Misc Algorithm
convert an array
Given an array:
$[a_1, a_2, ..., a_N, b_1, b_2, ..., b_N, c_1, c_2, ..., c_N ]$
convert it to:
$[a_1, b_1, c_1, a_2, b_2, c_2, ..., a_N, b_N, c_N]$
in-place using constant extra space.
def getIndex(currentIndex, N): return (currentIndex%3)*N + (currentIndex/3) def convertArray(arr): N=len(arr)/3 for currentIndex in range(len(arr)): swapIndex=getIndex(currentIndex, N) while swapIndex<currentIndex: swapIndex=getIndex(swapIndex, N) arr[currentIndex], arr[swapIndex] = arr[swapIndex], arr[currentIndex]
sliding window
http://www.leetcode.com/2011/01/sliding-window-maximum.html
Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]
void slidingwindow(int a[], int size, int w, int b[]) {
Queue queue = new Queue();
for (int i=0; i<w; i++) {
while(!queue.empty() && a[i] >= a[queue.back()]) {
queue.popBack();
}
queue.pushBack(i);
}
for (int i=w; i<size; i++) {
b[i-w] = a[queue.front()];
while(!queue.empty() && a[i] >= a[queue.back()]) {
queue.popBack();
}
while(!queue.empty() && queue.front() <= i-w ] {
queue.popFront();
}
queue.push(i);
}
b[n-w] = a[queue.front()];
}
reverse a linked list
void reverse(Node* & head) {
Node* pre = NULL;
Node* current = p;
while(current) {
next = current->next;
current->next = pre;
pre = current;
current = next;
}
head = pre;
}
void reverse(Node*& p) {
if (!p) return;
Node* rest = p->next;
if (!rest) return;
reverse(rest);
rest->next = p;
p->next = NULL;
p=rest;
}
Post preview:
Close preview