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;
}
*/