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; 
}
Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License