ZigZag Conversion

/*
ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
*/

class Solution {
public:
    string convert(string s, int nRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function   
        if (nRows <= 1) return s;
        int size = s.size();
        if(size <= nRows) return s;
        int step = 2*nRows-2;
        int round = size/step + 1;
        int i, k, index;
        string result;
        for(i=0; i<nRows; i++){
           for(k=0; k<round; k++){
              index = i + k*step;
              if(index<size){
                result.push_back(s[index]);
              }
             
              if(!(i==0 || i== (nRows-1))){
                index = index + step - 2*i;
                if(index<size){
                 result.push_back(s[index]);
                }
              } //end if
           } //end inner for
        } //end outer for
       
        return result;
    }
    };

Best Time to Buy and Sell Stock III

/*
Best Time to Buy and Sell Stock III

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

*/
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = prices.size();
        if(size <= 1) return 0;
       
        vector<int> localMaxForward;
        int maxProfitForward = 0;
        int minValueForward = prices[0];
        localMaxForward.push_back(maxProfitForward);
       
        int i;
        int temp;
        for(i=1; i<size; i++){
            if(prices[i] < minValueForward){
                minValueForward = prices[i];
            }
            else{
                temp = prices[i] - minValueForward;
               
                if(temp>maxProfitForward){
                    maxProfitForward = temp;
                }
            }
            localMaxForward.push_back(maxProfitForward);
        }
       
       
        vector<int> result;
        int maxProfitBackward = localMaxForward[size-1];
        int maxValueBackward = prices[size-1];
        result.insert(result.begin(), maxProfitBackward);
        for(i=size-2; i>=0; i--){
            if(prices[i] > maxValueBackward){
                maxValueBackward = prices[i];
            }
            else{
                temp = maxValueBackward - prices[i] + localMaxForward[i];
                if(temp>maxProfitBackward){
                    maxProfitBackward = temp;
                }
            }
            result.insert(result.begin(), maxProfitBackward);
        }
       
        return result[0];
    }
};

Word Ladder

/*
Word Ladder
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,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:

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

*/
//cannot pass large tests due to execution time
class Solution {
public:
    bool isLadder(string first, string second){
      int firstSz = first.length();
      int secondSz = second.length();
     
      if(firstSz != secondSz || firstSz == 0) return false;
     
      int i;
      int distance = 0;
      for(i=0; i<firstSz; i++){
        if(first[i]!=second[i]) {
          distance++;
          if(distance > 1) return false;
        }   
      }
     
      if (distance == 1) return true;
      else return false;
    }
   
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int startSize = start.length();
        int endSize = end.length();
        if(startSize != endSize || startSize == 0) return 0;
       
        unordered_set<string>::iterator find;
        find = dict.find(start);
        if(find==dict.end()) return 0;
        find = dict.find(end);
        if(find==dict.end()) return 0;
       
        if(start.compare(end) == 0) return 1;
        if(isLadder(start, end)) return 2;
       
        int dictSize = dict.size();
        if(dictSize == 0) return 0;
       
        int firstIndex;
        int secondIndex;
        //Get dictionary into vector
        vector<string> words;
        int i = 0;
        for(unordered_set<string>::iterator it=dict.begin(); it!=dict.end(); it++){
          words.push_back(*it);
          if((*it).compare(start) == 0) firstIndex = i;
          if((*it).compare(end) == 0) secondIndex = i;
          i++;
        }
       
        int j;
        int maxSize = dictSize;
        vector<vector<int>> matrix;
        vector<int> line;
       
        //initialize matrix;
        for(i=0; i<dictSize; i++){
          line.push_back(maxSize);
        }
        for(i=0; i<dictSize; i++){
          matrix.push_back(line);
        }
       
        //build distance matrix
        for(i=0; i<dictSize; i++){
          for(j=i; j<dictSize; j++){
            if(i == j) matrix[i][i] = 0;
            else if(isLadder(words[i], words[j])){
              matrix[i][j] = 1;
              matrix[j][i] = 1;
            }
          }
        }
       
        int step = 1;
        int k;
        while(step <= dictSize-2){
          for(i=0; i<dictSize; i++){
            for(j=0; j<dictSize; j++){
               if(matrix[i][j]==step){
                 for(k=j+1; k<dictSize; k++){
                   if(matrix[i][k]==1 && matrix[j][k] == maxSize){
                      matrix[j][k] = step+1;
                      matrix[k][j] = step+1;
                   }
                 }
               }
            }                       
          }
          step++;
        }
       
        int result = matrix[firstIndex][secondIndex];
        if(result==maxSize) return 0;
        else return result+1;
    }
};

Longest Consecutive Sequence

/*

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
*/
//limitation on max size and offset
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if(size == 0) return 0;
        if(size == 1) return 1;
        vector<bool> indicator;
       
        int offset = 2000;
        int maxSize = 20000;
       
        int i;
        for(i=0; i<maxSize; i++){
          indicator.push_back(false);
        }
       
        for(i=0; i<size; i++){
          if((num[i]+offset) >= maxSize || (num[i]+offset) < 0) return -1;
          indicator[num[i]+offset] = true;
        }
       
        int pos = 0;
        int result = 1;
        int tempResult = 0;
       
        while(pos < maxSize){
          if((pos == 0 && indicator[pos] == true)
             ||(pos > 1 && indicator[pos-1] == false && indicator[pos] == true)){
             tempResult = 1;
          }
          else if(pos > 1 && indicator[pos-1] == true && indicator[pos] == false){
             result = max(result, tempResult);
          }
          else if(pos > 1 && indicator[pos-1] == true && indicator[pos] == true){
             tempResult++;
          }
          pos++;
        }
       
        if(indicator[maxSize-1] == true) result = max(result, tempResult);
       
        return result;
    }
};


/*
set and hash-table
*/
class Solution {

public:

int longestConsecutive(vector<int> &num)



{
  set<int> seen; // A set keeping track of whether a number is seen or not

map<int, int> startChain; // A map from the starting number to the chain size

map<int, int> endChain; // A map from the ending number to the chain size

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



{
  int value = num[i];

if (seen.find(value) == seen.end())



{

seen.insert(value);
  map<int, int>::iterator peekStart = startChain.find(value + 1);

map<int, int>::iterator peekEnd = endChain.find(value - 1);




  // Attachable to the start and attachable to the end

if (peekStart != startChain.end() && peekEnd != endChain.end())



{
  int newStart = peekEnd->first - peekEnd->second + 1;

int newLength = peekEnd->second + 1 + peekStart->second;

int newEnd = newStart + newLength - 1;



startChain.erase(startChain.find(newStart));

endChain.erase(peekEnd);

startChain.erase(peekStart);

endChain.erase(endChain.find(newEnd));
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Attachable to the start only

if (peekStart != startChain.end() && peekEnd == endChain.end())



{
  int newStart = peekStart->first - 1;

int newLength = peekStart->second + 1;

int newEnd = newStart + newLength - 1;



startChain.erase(peekStart);

endChain.erase(endChain.find(newEnd));
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Attachable to the end only

if (peekStart == startChain.end() && peekEnd != endChain.end())



{
  int newEnd = peekEnd->first + 1;

int newLength = peekEnd->second + 1;

int newStart = newEnd - newLength + 1;



startChain.erase(startChain.find(newStart));

endChain.erase(peekEnd);
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Nothing else could be done - create a chain by itself

if (peekStart == startChain.end() && peekEnd == endChain.end())



{
  int newStart = value;

int newEnd = value;

int newLength = 1;

startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}

}

}
  int max = 0;

for (map<int, int>::iterator startIterator = startChain.begin(); startIterator != startChain.end(); startIterator++)



{
  int current = startIterator->second;

if (current > max)



{

max = current;

}

}
  return max;



}

};
  

Merge Sorted Array

/*

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
*/

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n<=0) return;
        int i;
        if(m<=0 && n>0){
          for(i=0; i<n; i++){
            A[i] = B[i];
          }
          return; 
        }
        //case 1 : A[0] >= B[n-1]
        if(A[0] >= B[n-1]){
           for(i=n+m-1; i>=n; i--){
             A[i] = A[i-n];
           }
           for(i=0; i<n; i++){
             A[i] = B[i];
           }
           return;
        }
       
        if(B[0]>=A[m-1]){
          for(i=m; i<=n+m-1; i++){
            A[i] = B[i-m];
          }
          return;
        }
       
        int posA = m-1;
        int posB = n-1;
        i = n+m-1;
        while(i>=0 && posA>=0 && posB>=0){
           if(A[posA]>B[posB]){
              A[i] = A[posA];
              posA--;
           }
           else{
              A[i] = B[posB];
              posB--;
           }
           i--;
        }
        if(posB>=0){
          for(i=0; i<=posB; i++){
            A[i] = B[i];
          }
        }
       
        return;
    }
};

Gray Code

/*

Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

*/
class Solution {
public:
    int pow(int base, int n){
       if(n==0) return 1;
       if(n==1) return base;
       return base*pow(base, n-1);
    }
   
    void getGrayCode(int n, vector<int> & result){
       if(n<0) return;
       if(n==0) {
          result.push_back(0);
          return;
       }
      
       getGrayCode(n-1, result);
       int size = result.size();
       int i;
       for(i=size-1; i>=0; i--){
         result.push_back(result[i]+pow(2,n-1));
       }
       return;
    }
    vector<int> grayCode(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> result;
        if(n<0) return result;
        getGrayCode(n, result);
        return result;
    }
};

Next Permutation

/*

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

*/
class Solution {
public:
    void swap(vector<int> &num, int i, int j){
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    int partition(vector<int> &num, int i, int j){
        int smallIndex = i;;
        int pivot =  num[i];
       
        int k;
        for(k=i+1; k<=j; k++){
            if(num[k]<pivot){
                smallIndex++;
                swap(num, smallIndex, k);
            }
        }
       
        swap(num, i, smallIndex);
       
        return smallIndex;
    }
    void sort(vector<int> &num, int i, int j){
        int k;
        if(i<j){
            k = partition(num, i, j);
            sort(num, i, k-1);
            sort(num, k+1, j);
        }  
    }
    void nextPermutation(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if(size<=1) return;
       
        int i;
        int j;
        for(i=size-2; i>=0; i--){
            for(j=size-1; j>i; j--){
                if(num[i]<num[j]){
                    swap(num, i, j);
                    sort(num, i+1, size-1);
                    return;
                }
               
            }
        }
       
        int mid = size/2 - 1;
        for(i=0; i<=mid; i++){
            swap(num, i, size-1-i);
        }
    }
};