Merge K sorted lists -- Leetcode

Question:


Answer:
1. Using heap. O(k*n*logk).
class Solution {
private:
    struct cmp{
        bool operator()(ListNode* lhs, ListNode *rhs){
            if(lhs->val < rhs->val) return false;
            else return true;
        }
    };
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int K = lists.size();
        if (K == 0) return NULL;
        else if (K == 1) return lists[0];
       
        ListNode *listHead(NULL), *listRear(NULL);
        ListNode *node(NULL);
     
        priority_queue<ListNode*, vector<ListNode*>, cmp> h;
       
        // push K list heads into heap
        for(int i=0; i<K; ++i)
          if(lists[i] != NULL){
            h.push(lists[i]);
            lists[i] = lists[i]->next;
          }
           
        while(!h.empty()){
                   //pop the min of k nodes in the heap.
          node = h.top(); h.pop();
          if(node->next)
            h.push(node->next);
           
                   //insert node into new list.    
          if(listRear){
              listRear->next = node;
              listRear = listRear->next;
          }
          else{
              listHead = listRear = node;
          }
        }
       
        return listHead;
    }
};

2. Merge Lists using Divide and Conquer. O(k*n*logk).

1. public ListNode mergeKLists(ArrayList<ListNode> lists) {  
2.     if(lists==null || lists.size()==0)  
3.         return null;  
4.     return helper(lists,0,lists.size()-1);  
5. }  
6. private ListNode helper(ArrayList<ListNode> lists, int l, int r)  
7. {  
8.     if(l<r)  
9.     {  
10.         int m = (l+r)/2;  
11.         return merge(helper(lists,l,m),helper(lists,m+1,r));  
12.     }  
13.     return lists.get(l);  
14. }  
15. private ListNode merge(ListNode l1, ListNode l2)  
16. {   
17.     ListNode dummy = new ListNode(0);  
18.     dummy.next = l1;  
19.     ListNode cur = dummy;  
20.     while(l1!=null && l2!=null)  
21.     {  
22.         if(l1.val<l2.val)  
23.         {  
24.             l1 = l1.next;  
25.         }  
26.         else  
27.         {  
28.             ListNode next = l2.next;  
29.             cur.next = l2;  
30.             l2.next = l1;  
31.             l2 = next;  
32.         }  
33.         cur = cur.next;  
34.     }  
35.     if(l2!=null)  
36.         cur.next = l2;  
37.     return dummy.next;  
38. }  

BST insert + delete

1. BST insert:
BTNode* insertNode(BTNode *root, int insval){
if(!root){
root=new BTNode(insval);
return root;
}

BTNode *p==root;
BTNode *cur==root;

while(cur!=NULL){
if(insval<cur->value){
p=cur;
cur=cur->left;
}
else if(insval>cur->val){
p=cur;
cur=cur->right;
}
else{
cout<<"Have exsited."<<endl;
return cur;
}
}
if(insval< p->value){
cur=new BTNode(insval);
p->left= cur;
}
else if(insval > p->val){
cur=new BTNode(insval);
p->right= cur;
}
return cur;
}

/****************************************************************************/
2. BST search, return parent.
BTNode* search(BTNode *root, int insval, &position){
if(!root) return NULL;

BTNode *p==root;
BTNode *cur==root;
    position=0;

while(cur!=NULL){
if(insval<cur->value){
p=cur;
cur=cur->left;
position=-1;
}
else if(insval>cur->val){
p=cur;
cur=cur->right;
position=1;
}
else{
cout<<"Find it."<<endl;
return p;
}
}

/******************************************************************/
3. BST delete.
BTNode* deleteNode(BTNode *root){
 ///////
 parent = search(root, node, &position);    //get parent pointer.

 if(parent == NULL)     //该节点不在二叉树中
  return root;
 else{
  switch(position){
  case -1: point = parent->left; //左子树节点
   break;
  case 1:  point = parent->right; //右子树节点
   break;
  case 0: point = parent;   //根节点
   break;
  }

//case1: 没有左子树也没有右子树
 if(point->left==NULL && point->right==NULL){
   switch(position){   //判断删除的位置
   case -1: parent->left = NULL;
    break;
   case 1: parent->right = NULL;
    break;
   case 0: parent = NULL;
    break;
   }
   free(point);
   return root;
 }
 
  //case2: 没有左子树
  if(!point->left && point->right){
   if(parent!=point)    //！！！！！！！！！！
 
    parent->right = point->right;//
   else  //
    root = root->right;    //将根节点指向右子节点！！！！！！！！！！！
   free(point);      //释放节点内存
   return root;
  }

  //case3: 没有右子树
  else if(point->right==NULL && point->left!=NULL){
   if(parent != point)
 
    parent->left = point->left;
   else
    root = root->left;     //将根节点指向左子树节点
   free(point);
   return root;
  }

  //case4: 有左子树也有右子树
  else if(point->right!=NULL && point->left!=NULL){
   parent = point;    
   child = point->left;    //设置子节点
 
   while(child->right != NULL){
    parent = child;  
    child = child->right;
   }

   //*******************************//
   point->data = child->data; //！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！左子数最大值替换删除点值

   if(parent->left == child)
    parent->left = child->left;
   else
    parent->right = child->right;
   free(child);
   return root;       //返回根节点的指针
  }

Binary Search

int bisearch(char** arr, int b,int e, char* v){

int minIdx=b,maxIdx=e,midIdx;

while(minIdx< maxIdx-1){

midIdx= minIdx+(maxIdx- minIdx)/2;

if(strcmp(arr[midIdx],v)<=0){             //end case for while:1. minI=maxI; 2.minI = maxI -1;

minIdx= midIdx;
}
else{
            maxIdx = midIdx;
}
}
if(!strcmp(arr[maxIdx],v){
return maxIdx;
}
else if(!strcmp(arr[minIdx],v){
return minIdx;
}
else{
return -1;
}
}

Heap sort

#ifndef _HEAP_SORT_H
#define _HEAP_SORT_H

#define _BOTTOM_TOP

#define LEFT(i) (((i)<<1)+1)
#define RIGHT(i) (((i)<<1)+2)
#define PARENT(i) (((i+1)>>1)-1)

void reheap_down(int * arr, int start, int end) {
    if(start >= end) return;
    int root=start;
    while(LEFT(root)<=end) {
int to_swap = LEFT(root);
if(RIGHT(root)<=end &&
arr[LEFT(root)] < arr[RIGHT(root)]) {
   to_swap = RIGHT(root);
}

if(arr[root] < arr[to_swap]) {
   swap(arr+root, arr+to_swap);
   root = to_swap;
} else {
   break;
}

    }
}

void reheap_up(int * arr, int start, int end) {
    if(start >= end) return;
    int child = end;
    int par = PARENT(child);
    while(par > -1) {
if(arr[par] < arr[child]) {
   swap(arr+par, arr+child);
   child = par;
   par = PARENT(child);
} else {
   break;
}
    }
}

void make_heap(int * arr, int size) {
#ifdef BOTTOM_UP
    int root = PARENT(size-1);
    while(root>-1) {
reheap_down(arr, root, size-1);
root--;
    }
#else
    int end = 0;
    while(end<size) {
reheap_up(arr, 0, end);
end++;
    }
#endif
}

void sort(int * arr, int size) {

    make_heap(arr, size);

    int i = size-1;
    for(i = size - 1; i>=0; i--) {
swap(arr, arr+i);
reheap_down(arr, 0, i-1);
//print_arr(arr, size);
    }
}

#endif

Word Ladder -- Leetcode

Question:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: 

1.Only one letter can be changed at a time. 2.Each intermediate word must exist in the dictionary

For example,

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Answer:

class Solution {

public:

    int ladderLength(string start, string end, unordered_set<string> &dict) {

        if (start.size() != end.size())  

            return 0;  

        if (start.empty() || end.empty())  

            return 1;  

        if (dict.size() == 0)  

            return 0; 

            

        int distance = 1;                          //!important 

        queue<string> queToPush, queToPop;  

        queToPop.push(start); 

        dict.erase(start);

         

        while (dict.size() > 0 && !queToPop.empty())  

        {  

            while (!queToPop.empty())  

            {  

                string str(queToPop.front()); 

                queToPop.pop();                           //!important

                for (int i = 0; i < str.size(); i++)  

                {  

                    char temp = str[i]; 

                    for (char j = 'a'; j <= 'z'; j++)  

                    {  

                      if (j != temp){ 

                        str[i] = j;  

                        if (str == end)  

                            return distance + 1; 

                        if (dict.count(str) > 0)  

                        {  

                            queToPush.push(str); 

                            dict.erase(str);           //delete corresponding element in dict in case of loop  

                        }  

                      }

                    }

                    str[i] = temp;

                }  

            }  

            swap(queToPush, queToPop);  

            distance++;  

        } 

        return 0; 

    }

};

merge sort + quick sort

1. Merge Sort:
void merge(int a[], int low, int mid, int high)
{
    int b[10000];    //initial enough large space! >= length of array a[].
    int i = low, j = mid + 1, k = 0;

    while (i <= mid && j <= high) {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while (i <= mid)
        b[k++] = a[i++];

    while (j <= high)
        b[k++] = a[j++];

    k--;   //Very important!
    while (k >= 0) {
        a[low + k] = b[k];
        k--;
    }
}

void mergesort(int a[], int low, int high)
{
    if (low < high) {
        int m = (high + low)/2;
        mergesort(a, low, m);
        mergesort(a, m + 1, high);
        merge(a, low, m, high);
    }
}



2. Quick Sort:

int divide(int * arr, int length, int pivot) {
    int target = arr[pivot];
    swap(arr+length-1, arr+pivot);
    pivot = 0;
    int idx = 0;

    while(idx < length-1) {
if(arr[idx] <= target) {
   swap(arr+idx, arr+pivot);
   pivot++;
}
idx++;
    }
    swap(arr+length-1, arr+pivot);
    return pivot;
}

void qsort(int * arr, int length, int pivot) {
    if(length <= 1) return;
    assert(pivot<length && pivot>=0);
    pivot = divide(arr, length, pivot);
    qsort(arr, pivot, 0);
    qsort(arr+pivot+1, length-pivot-1, 0);
}

void sort(int * arr, int size) {
    qsort(arr,  size, 0);
}

AI-- Minimax Algorithm

class ComputerPlayer
{
public:
static int min(Board *b,int alpha, int beta){
if(b->full_board())
return b->Evaluation();
int value= 10;
for(int i =1; i<=3; i++)
for(int j=1; j<=3; j++)
{
if(b->get_square(i,j)==0)
{
Board next = *b;
next.play_square(i,j,HUMANPLAYER);
value = MIN(value, max(&next, alpha,beta));
if(value <= alpha)
return value;
beta = MIN(value,beta);
}
}
return value;

}

static int max(Board *b, int alpha, int beta){
if(b->full_board())
return b->Evaluation();
int value = -10;
for(int i =1;i<=3;i++)
for(int j=1;j<=3;j++)
{
if(b->get_square(i,j)==0)
{
Board next = *b;
next.play_square(i,j,CPUPLAYER);  // =CPU;
value = MAX(value, min(&next,alpha,beta));
if(value>= beta)
return value;
alpha = MAX(alpha,value);
}
}
return value;

}

static pos miniMax(Board *b){
int value= -10;
pos next_ply;
for(int i =1;i<=3;i++)
for(int j=1;j<=3;j++)
{
if(b->get_square(i,j)==0)
{
Board next;
next= *b;
next.play_square(i,j,CPUPLAYER);
int tmp = min(&next,-10,10);
if( tmp > value)
{
value = tmp;
next_ply.x = i;
next_ply.y = j;
}
}
}
return next_ply;

}
};

Sudoku Solver -- leetcode (Recursion+Stack)

1. Recursion:
class Solution {
public:
    bool solveSudoku(vector<vector<char> > &board) {
        for (int i = 0; i < 9; ++i){
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (int k = 0; k < 9; ++k) {
                        board[i][j] = '1' + k;
                        if (isValid(board, i, j) && solveSudoku(board))
                            return true;
                    }
                    board[i][j] = '.';
                    return false;
                }
            }
        }
        return true;
    }
private:
    // 检查 (x, y) 是否合法
    bool isValid(const vector<vector<char> > &board, int x, int y) {
        int i, j;
        for (i = 0; i < 9; i++) // 检查 y 列
            if (i != x && board[i][y] == board[x][y])
                return false;
        for (j = 0; j < 9; j++) // 检查 x 行
            if (j != y && board[x][j] == board[x][y])
                return false;
        for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
            for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
                if (i != x && j != y && board[i][j] == board[x][y])
                    return false;
        return true;
    }
};

Max Heap Sort

1. class HeapSortAlgorithm {  
2.       
3.     public void HeapSort(int[] array) {  
4.         int heapSize = array.length;  
5.         for (int i = array.length / 2 - 1; i >= 0; i--) {  
6.             MaxHeapify(array, i, array.length);  
7.         }  
8.           
9.         for (int i = array.length - 1; i > 0; i--) {  
10.             swap(0, i, array);  
11.             heapSize--;  
12.             MaxHeapify(array, 0, heapSize);  
13.         }  
14.     }  
15.       
16.     /// MaxHeapify is to build the max heap from the 'position'  
17.     public void MaxHeapify(int[] array, int position, int heapSize)  
18.     {  
19.         int left = left(position);  
20.         int right = right(position);  
21.         int maxPosition = position;  
22.           
23.         if (left < heapSize && array[left] > array[position]) {  
24.             maxPosition = left;  
25.         }  
26.           
27.         if (right < heapSize && array[right] > array[maxPosition]) {  
28.             maxPosition = right;  
29.         }  
30.           
31.         if (position != maxPosition) {  
32.             swap(position, maxPosition, array);  
33.             MaxHeapify(array, maxPosition, heapSize);  
34.         }  
35.     }  
36.       
37.     /// return the left child position  
38.     public int left(int i)  
39.     {  
40.         return 2 * i + 1;  
41.     }  
42.     /// return the right child position  
43.     public int right(int i)  
44.     {  
45.         return 2 * i + 2;  
46.     }   
47. }  

MaxHeapify的时间复杂度为 O(lgn), 所以整个heap sort的复杂度为：O(n lgn).

Find Kth largest element in an unsorted array.

code:

1. Partition method (" Selection Rank " k) :

int partition (int a[], int left, int right, int pivot){
     while(true){
          while (left<= right && a[left] <= pivot){
                left ++ ;
          }
          while (left <= right && a[right] > pivot){
                right --;
          }
          if (left>right){                    //end case.
               return left-1;
          }
          swap( a+left, a+right);
      }
 }

int Kbig(int a[], int left, int right, int k){
        int pivot = a[(random()-left)%(right-left)+left] ;

        int leftEnd = partition(a, left, right, pivot);
        int leftSize = leftEnd - left +1;

        if ( leftSize == k) return Max(a+left, a+leftSize); //return pivot?                //end case.
        else if (leftSize > k) return Kbig ( a, left, leftEnd, k);
        else if (leftSize < k) return Kbig (a, leftEnd+1, right, k-leftSize);
}
 

2. Similar, using vector<int> to partition:

vector<int>  Kbig(vector<int> s, int k){
     vector<int> res, sa, sb;
     if(k<=0) return res;
     if(s.size()<=k) return s;

     // if(s.size() > k)
     Partition(s, &sa,&sb);
     return Kbig(sa, k). append (Kbig(sb, k- sa.size());
}

void Partition (vector<int> s, vector<int> &a, vector<int> &b){
   
       pos = random()%s.size();
       swap(s[0], s[pos]);
       int pivot = s[0];

       for( int i=1;i<s.size();++i){
             s[i]> pivot? a.push_back(s[i]) : b.push_back(s[i]);
       }
     
      a.size() < b.size()? a.push_back(pivot): b.push_back(pivot). // To avoid null array & more average.
}

Median of Two sorted arrays -- Leetcode (O(logn) solution)

method 1: find Kth largest element of a[m] and b[n] sorted arrays.

double findKth(int a[], int m, int b[], int n, int k)
{
    //always assume that m is equal or smaller than n
    if (m > n)
        return findKth(b, n, a, m, k);
    if (m == 0)
        return b[k - 1];
    if (k == 1)                                 //end case
        return min(a[0], b[0]);

    //divide k into two parts: pa + pb.
    int pa = min(k / 2, m), pb = k - pa;
    if (a[pa - 1] < b[pb - 1])
        return findKth(a + pa, m - pa, b, n, k - pa);
    else if (a[pa - 1] > b[pb - 1])
        return findKth(a, m, b + pb, n - pb, k - pb);
    else
        return a[pa - 1];
}

class Solution
{
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
        int total = m + n;
        if (total & 0x1)
            return findKth(A, m, B, n, total / 2 + 1);
        else
            return (findKth(A, m, B, n, total / 2)
                    + findKth(A, m, B, n, total / 2 + 1)) / 2;
    }
};
我们可以看出，代码非常简洁，而且效率也很高。在最好情况下，每次都有k一半的元素被删除，所以算法复杂度为logk，由于求中位数时k为（m+n）/2，所以算法复杂度为log(m+n)。

/******************************************************************************/

method 2:
Algorithm：

1) Calculate the medians m1 and m2 of the input arrays ar1[]
   and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.    //end case1.
     return m1 (or m2)
3) 1. If m1 is greater than m2, then median is present in one of the below two subarrays.
      a)  ar1[0....|_n/2_|]
      b)  ar2[|_n/2_|....n-1]
   2. If m2 is greater than m1, then median is present in one of the below two subarrays.
      a)  ar1[|_n/2_|....n-1]
      b)  ar2[0....|_n/2_|]
4) Repeat the above process until size of both the subarrays becomes 2.
5) If size of the two arrays is 2, use below formula to get the median.    //end case2.

       Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2 ///!!Correct, ignore the head and tail, avoid merge step, so tricky!
Example:
      ar1[] = {1, 12, 15, 26, 38},
      ar2[] = {2, 13, 17, 30, 45}
For the two arrays: m1 = 15 and m2 = 17.
For the above ar1[] and ar2[], m1 < m2. So median lies in one of the following two subarrays:
              [15, 26, 38]
         [2,  13, 17]
Get:
      m1 = 26, m2 = 13. => m1 > m2. So the subarrays become:
               [15, 26]
      [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
                         = (max(15, 13) + min(26, 17))/2
                         = (15 + 17)/2
                         = 16
_______________________________________________________________________________
code:
#include <stdio.h>

#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)

int median(int ar[],int n){
if(n%2){
return ar[n/2];
}
else{
return (ar[n/2-1]+ar[n/2])/2;
}
}

int getMedian(int ar1[],int ar2[], int n){
if(n<=0){
printf("Error, illegal array length!\n");
return -1;
}
if(n==1){
return (ar1[0]+ar2[0])/2;
}
if(n==2){
return Max(ar1[0],ar2[0])+Min(ar1[1]+ar2[1])/2;       //end case 1, subarray size=2.
}
    m1= median(ar1,n);
    m2= median(ar2,n);

if(m1==m2) return m1;                                     //end case 2, m1==m2.
if(m1<m2){
   if(n%2){    //n is odd.
           return getMedian(ar1 + n/2, ar2, n - n/2);
}
  else{      // n is even.
  return getMedian(ar1 + n/2, ar2, n - n/2);
}
}
else{
if(n%2){
return getMedian(ar1, ar2 + n/2, n - n/2);
}
else{
return getMedian(ar1, ar2 + n/2, n - n/2);
}
}
}

int main()
{
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45};
    int n1 = sizeof(ar1)/sizeof(ar1[0]);
    int n2 = sizeof(ar2)/sizeof(ar2[0]);
    if (n1 == n2)
      printf("Median is %d", getMedian(ar1, ar2, n1));
    else
      printf("Unequal array size!");
    getchar();
    return 0;
}

/*
original merging method: O(n).
Suppose the sorted array is in ascending order.
median=(res[n-1]+res[n])/2.

method 1:
int get median(int a[],int b[],n){
    int res[2*n];
int i=n-1,j=n-1,k=2*n-1;

while(i>=0 && j>=0){
   if(a[i]<b[j]){
   res[k--]=b[j--];
   }
   else{
   res[k--]=a[i--];
}
}
if(i<0){
while(j>=0){
  res[k--]=b[j--];
}
}
else{
while(i>=0){
   res[k--]=a[i--];
}
}
return (res[n-1]+res[n])/2;
}

method 2: exist boundry case bugs!!
int get median(int a[],int b[],n){
    int res[2*n];
int i=0,j=0,ka=-1,kb=-1;

while(i<n&&j<n){
   if(a[i]<b[j]){
   ka=i;
i++;
if(ka+kb==n-2){
       m1=a[ka];
   }
   if(ka+kb==n-1){
       m2=a[ka];
   }
   }
   else{
   kb=j;
j++;
if(ka+kb==n-2){
       m1=b[kb];
   }
   if(ka+kb==n-1){
       m2=b[kb];
   }
}

 
}
if(i==n){
while(j<n){
  kb=j;
  j++;
  if(ka+kb==n-1){
       m2=b[kb];
  }
}
}
else{
while(i<n){
  ka=i;
  i++;
  if(ka+kb==n-1){
       m2=a[ka];
  }
}
}
return (m1+m2)/2;
}
*/