(Leetcode) Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution:
Since there are only four possibilities for each char, we could use 2 bits to represent one char and assign them value like: 00 for ‘A’, 01 for ‘C’, 10 for ‘G’ and 11 for ‘T’.

Thus each 10-char substring could be transformed into 20 bits. We use a 32-bit int to represent the 10-char sequence. After we have the first 10 chars and move forward, each step we add a new char and remove the left-most char in the window. We could use some bit operations to represent this update.

Whenever we calculated an int value, we insert it into a map, which counts the occurrence of each int.

Finally we find out all the int value that appears more than once and transform them back to 10-char string.

My code:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> out;
        if (s.size() < 10)
            return out;
        
        unordered_map<int, int> map;
        
        string temps = s.substr(0, 10);
        int temphash = stringHash(temps);
        
        map[temphash]++;
        
        for (int i = 10; i < s.size(); i++) {
            int newhash = updateHash(s, temphash, i);
            //string temps = s.substr(i - 9, 10);
            //int newhash = stringHash(temps);
            map[newhash]++;
            temphash = newhash;
        }
        
        for (auto it = map.begin(); it != map.end(); it++) {
            if (it -> second > 1) {
                string outstring = hashToStr(it -> first);
                out.push_back(outstring);
            }
        }
        
        return out;
        
    }
    
    int stringHash(string &s) {
        // s.size() == 10;
        int out = 0;
        for (int i = 0; i < 10; i++) {
            char c = s[i];
            if (c == 'C') {
                out |= 1;
            } else if (c == 'G') {
                out |= 2;
            } else if (c == 'T') {
                out |= 3;
            }
            
            out <<= 2;
        }
        
        out >>= 2;
        
        return out;
    }
    
    int updateHash(string &s, int oldhash, int newi) {
        int mask = ~(3 << 18);
        oldhash &= mask;
        oldhash <<= 2;
        
        char newc = s[newi];
        if (newc == 'C')
            oldhash |= 1;
        else if (newc == 'G')
            oldhash |= 2;
        else if (newc == 'T')
            oldhash |= 3;
        
        return oldhash;
    }
    
    string hashToStr(int hash) {
        string out = "";
        
        int mask = 3;
        for (int i = 0; i < 10; i++) {
            int twodigit = hash & mask;
            if (twodigit == 0) {
                out = 'A' + out;
            } else if (twodigit == 1) {
                out = 'C' + out;
            } else if (twodigit == 2) {
                out = 'G' + out;
            } else {
                out = 'T' + out;
            }
            
            hash >>= 2;
        }
        
        return out;
    }
    
};

Convert Infix to Postfix in C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;


// Simply determine if character is one of the four standard operators.
bool isOperator(char character) {
    if (character == '+' || character == '-' || character == '*' || character == '/') {
        return true;
    }
    return false;
}


// If the character is not an operator or a parenthesis, then it is assumed to be an operand.
bool isOperand(char character) {
    if (!isOperator(character) && character != '(' && character != ')') {
        return true;
    }
    return false;
}


// Compare operator precedence of main operators.
// Return 0 if equal, -1 if op2 is less than op1, and 1 if op2 is greater than op1.
int compareOperators(char op1, char op2) {
    if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) { return -1; }
    else if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/')) { return 1; }
    return 0;
}


int main()
{
    // Empty character stack and blank postfix string.
    stack<char> opStack;
    string postFixString = "";
	
    char input[100];

    // Collect input
    cout << "Enter an expression: ";
    cin >> input;

    // Get a pointer to our character array.
    char *cPtr = input;

    // Loop through the array (one character at a time) until we reach the end of the string.
    while (*cPtr != '\0') {
        // If operand, simply add it to our postfix string.
        // If it is an operator, pop operators off our stack until it is empty, an open parenthesis or an operator with less than or equal precedence.
        if (isOperand(*cPtr)) { postFixString += *cPtr; }
        else if (isOperator(*cPtr)) {
            while (!opStack.empty() && opStack.top() != '(' && compareOperators(opStack.top(),*cPtr) <= 0) {
                postFixString += opStack.top();
                opStack.pop();
            }
            opStack.push(*cPtr);
        }
        // Simply push all open parenthesis onto our stack
        // When we reach a closing one, start popping off operators until we run into the opening parenthesis.
        else if (*cPtr == '(') { opStack.push(*cPtr); } 
        else if (*cPtr == ')') {
            while (!opStack.empty()) {
                if (opStack.top() == '(') { opStack.pop(); break; }
                postFixString += opStack.top();
                opStack.pop();
            }
        }

        // Advance our pointer to next character in string.
        cPtr++;
    }

    // After the input expression has been ran through, if there is any remaining operators left on the stack
    // pop them off and put them onto the postfix string.
    while (!opStack.empty()) {
        postFixString += opStack.top();
        opStack.pop();
    }


    // Show the postfix string at the end.
    cout << "Postfix is: " << postFixString << endl;
    return 0;
}

(Leetcode) Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Iterative

public List<String> generateParenthesis(int n) {
    ArrayList<String> list = new ArrayList<String>();
    Stack<String> stack = new Stack<String>();
    Stack<Integer> validationStack = new Stack<Integer>();
    stack.push("(");
    validationStack.push(0);
    while(stack.size() != 0)
    {
        String s = stack.pop();
        int v = validationStack.pop();
        if(s.length() == n * 2)
        {
            list.add(s);
            continue;
        }
        if(s.length() - v < n)
        {
            stack.push(s + "(");
            validationStack.push(v);
        }
        if(2 * v < s.length())
        {
            stack.push(s + ")");
            validationStack.push(v+1);
        }
    }
    return list;
}

Recursive

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string sofar = "";
        vector<string> out;
        dogen(n, 0, 0, sofar, out);
        return out;
    }
    
    void dogen(int n, int left, int right, string sofar, vector<string> &out) {
        if (sofar.size() == 2 * n) {
            out.push_back(sofar);
            return;
        }
        
        if (left < n) {
            dogen(n, left+1, right, sofar + '(', out);
        }
        
        if (right < left) {
            dogen(n, left, right+1, sofar + ")", out);
        }
    }
};

(Leetcode) Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28

class Solution {
public:
    int titleToNumber(string s) {
        int out = 0;
        
        for (int i = 0; i < s.size(); i++) {
            out = out * 26 + s[i] - 'A' + 1;
        }
        
        return out;
    }
};

(Leetcode) Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

string convertToTitle(int n) {
        string ans;
        while (n) {
            ans = char ((n - 1) % 26 + 'A') + ans;
            n = (n - 1) / 26;
        }
        return ans;
    }

(Leetcode) Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”.

Solutions:
Use a hash table to keep track of the mapping of the remainder and the start index of the recurring decimal.

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (!numerator) return "0";
        
        int64_t n = numerator, d = denominator;
        string out = "";
        unordered_map<int,int> um;
        
        if (n < 0 ^ d < 0) out += '-';
        n = abs(n), d = abs(d);
        
        out += to_string(n/d);
        n %= d;
        
        if (n)
            out += '.';
        
        while (n) {
            // loop
            if (um.find(n) != um.end()) {
                out.insert(um[n], 1, '(');
                out += ')';
                return out;
            }
                    
            um[n] = out.size();
                    
            n *= 10;
            out += to_string(n / d);
            n %= d;
        }
        
        return out;
    }
};

(Leetcode) Compare Version Numbers

Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Solution:
The ‘.’ character does not represent a decimal point because there could be more than one ‘.’ in one version number string.

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int i1 = 0, i2 = 0;

        int p1, p2;
        while (i1 < version1.size() || i2 < version2.size()) {
            p1 = 0, p2 = 0;
            if (i1 != version1.size()) {
                int starti1 = i1;
                while (i1 < version1.size() && version1[i1] != '.') {
                    p1 = p1 * 10 + version1[i1] - '0';
                    i1++;
                }

                if (i1 < version1.size())
                    i1++;
            }

            if (i2 != version2.size()) {
                int starti2 = i2;
                while (i2 < version2.size() && version2[i2] != '.') {
                    p2 = p2 *10 + version2[i2] - '0';
                    i2++;
                }

                if (i2 < version2.size())
                    i2++;
            }

            if (p1 > p2)
                return 1;
            if (p1 < p2)
                return -1;
        }

        return 0;

    }
};

Old code that uses substr and stoi function, which gives bad run-time.

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int i1 = 0, i2 = 0;

        int p1, p2;
        while (i1 < version1.size() || i2 < version2.size()) {
            if (i1 == version1.size())
                p1 = 0;
            else {
                int starti1 = i1;
                while (i1 < version1.size() && version1[i1] != '.')
                    i1++;
                p1 = stoi(version1.substr(starti1,i1 - starti1));

                if (i1 < version1.size())
                    i1++;
            }

            if (i2 == version2.size())
                p2 = 0;
            else {
                int starti2 = i2;
                while (i2 < version2.size() && version2[i2] != '.')
                    i2++;
                p2 = stoi(version2.substr(starti2,i2 - starti2));

                if (i2 < version2.size())
                    i2++;
            }

            if (p1 > p2)
                return 1;
            if (p1 < p2)
                return -1;
        }

        return 0;

    }
};

(Leetcode) Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Solution:
The idea is to split the range [min, max] evenly int n-1 intervals. The interval length would be (max – min)/(n-1). According to the pigeon hole principle, the max range cannot be smaller than (max – min)/(n-1). Which means if there are two numbers generates the max difference, they must be in different intervals. Then we just need to compute the max difference between successive elements that lies in adjacent intervals. To do that, we just need to record min and max value for each interval. (by adamlhh)

int maximumGap(vector<int> &num) {
    if (num.size()<2) return 0;

    int max = *max_element(num.begin(), num.end());
    int min = *min_element(num.begin(), num.end());
    int n = num.size();
    vector<int> max_idx(n, -1);
    vector<int> min_idx(n, -1);

    for (int i=0; i<n; ++i) {
        int idx = ((double) (num[i]-min) * (n-1)) / (max-min);
        if (num[i] > max_idx[idx])
            max_idx[idx] = num[i];
        if (num[i] < min_idx[idx] || min_idx[idx] == -1)
            min_idx[idx] = num[i];
    }

    int max_gap = 1;
    int i=0, j=1;
    while (i<n && j<n) {
        while (j<n && min_idx[j] == -1) ++j;
        if (j == n) break;
        if (min_idx[j] - max_idx[i] > max_gap)
            max_gap = min_idx[j] - max_idx[i];
        i = j;
        j = j+1;
    }

    return max_gap;
}

(Leetcode) Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

Solution:

class Solution {
public:
    vector<string> findMissingRanges(int A[], int n, int lower, int upper) {
        vector<string> out;
        int curstart = lower;

        for (int i=0;i<n;i++) {
            if (A[i] == curstart) {
                curstart++;
            } else if (A[i] > curstart) {
                string tempout = "";
                if (A[i] == curstart+1) {
                    tempout += to_string(curstart);
                } else {
                    tempout += to_string(curstart);
                    tempout += "->";
                    tempout += to_string(A[i]-1);
                }

                out.push_back(tempout);
                curstart = A[i]+1;
            }
        }

        string tempout = "";
        if (n>0 && A[n-1] < upper-1 || n==0 && upper > lower) {
            tempout += to_string(curstart);
            tempout += "->";
            tempout += to_string(upper);
        } else if (n>0 && A[n-1] == upper-1 || n==0 && upper == lower) {
            tempout += to_string(upper);
        }

        if (tempout != "")
            out.push_back(tempout);

        return out;
    }
};

One special test case is empty array.

(Leetcode) Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

class Solution {
public:
    int findPeakElement(const vector<int> &num) {
        int start = 0, end = num.size()-1;
        while (start<=end) {
            int mid = (start+end)/2;
            if (mid!=0 && num[mid] < num[mid-1]) {
                end = mid-1;
            } else if (mid!=num.size()-1 && num[mid] < num[mid+1] ){
                start = mid+1;
            } else {
                return mid;
            }
        }
        
    }
};