Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

 Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

--------------------------------- thinking ------------------------------------------------------------------------------
At the very beginning, I've a wrong understanding of the question. I thought if there is a duplication, the whole substring will be abandoned. This is totally wrong. e.g. abcaef
Then after realizing this mistake, I still made mistakes on the codes at "when to reset the start value", which should be when the start is smaller than the index in hash table, but I wrongly say the index is bigger than 0. e.g. abba
https://leetcode.com/discuss/32350/my-9-lines-solution-in-c ----------------------------------- codes -----------------------------------------------------------------------------------
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.size();
        if (len == 0) {
            return 0;
        }
        //unordered_map<char, int> map;
        int map[256];
        memset(map, -1, sizeof(map));
        int longest = 1;
        int start = 0;
        int i;
        for (i = 0; i < len; i++){
            //bug here, map[s[i]]should always larger than start, but not 0, because it might reverse the start far back. e.g. abba
            if (map[s[i]] >= start) {
                longest = max(longest, i - start);
                start = map[s[i]] + 1;
                //map.erase(s[i]);
            }
            map[s[i]] = i;
        }
        longest = max(longest, i - start);
        return longest;
    }

};

Find Peak Element

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.

-------------------------------------- thinking -----------------------------------------------------------------------

definitely using divide and conquer!!

What's the edge condition: 

1. when the length is 0, 1 and 2

2. when the middle point is at bottom, which is mid < left && mid < right!!! (having a bug here!) 

--------------------------------------- problems --------------------------------------------------------------------

I made a mistake on deciding which direction to go!

--------------------------------------- codes -------------------------------------------------------------------------

class Solution {

public:

    int findPeakElement(const vector<int> &num) {

        int len = num.size();

        int lft = 0;

        int rit = len - 1;

        if (len == 1) {

            return 0;

        }

        //while (lft < rit && lft >= 0 && rit < len) {

        while (lft < rit) {

            int mid = floor((lft + rit) / 2.0);

            int mid_left = mid >= 1?num[mid-1]:num[mid] - 1;

            int mid_right = mid <= len - 2?num[mid+1]:num[mid] - 1;

            if (num[mid] > mid_left && num[mid] > mid_right) {

                return mid;

            } else if (num[mid] < mid_left && mid >= 1) {//bug here, be clear about which direction we should go

                rit = mid - 1;

            } else if (num[mid] <mid_right && mid < len - 1) {

                lft = mid + 1;

            }

        }

        return lft;

    }

};

Maximum Gap

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.

----------------------------------- good codes --------------------------------------------------------------

My idea comes from this: Since the question only allow O(n) run time, I cannot do sorting, (sorting takes at least O(n log n). I can only make use of the O(n) space. Considering the worst case, where the integers are spread by equal distance, like {1,3,5,7,9}. Then the maximum gap is the 2, change any integer in between will leads to larger gap.

So I keep a gaps array which has equal gap distance and non-overlapping range. Like the example {1,3,5,7,9} become {[1,3),[3,5),[5,7),[7,9]}. Let me add some number into it without changing the minimum and maximum bound. {1,3,2,4,5,7,9}. Then, go through the num array, assign lower bound and upper bound for each gap.

The example {1,3,2,4,5,7,9} has gaps

[1,3) with lower bound = 1 and upper bound = 2;

[3,5) with lower bound = 3 and upper bound = 4;

[5,7) with lower bound = 5 and upper bound = 5;

[7,9] with lower bound = 7 and upper bound = 9;

Then go through the gaps array once, you'll be able to find out the maximum gap.

public class Solution {
    public int maximumGap(int[] num) {
        int maxGap = 0;

        // edge case
        if(num.length < 2){return maxGap;}

        // get maximum and minimum
        int min = num[0];
        int max = num[0];
        for(int i = 0;i < num.length;i++){
            if(num[i] < min)
                min = num[i];
            if(num[i] > max)
                max = num[i];
        }

        // divide into identical gaps
        Gap[] gaps = new Gap[num.length-1];
        boolean[] Engaged = new boolean[num.length-1];
        double gap = (double)(max-min)/(double)(num.length-1);
        for(int i = 0;i < gaps.length;i++)
            Engaged[Math.min((int)Math.floor((double)(num[i]-min)/gap),gaps.length-1)] = true;

        // assign maximum and minimum for each gap
        for(int i = 0;i < gaps.length;i++)
            gaps[i] = new Gap();
        for(int i = 0;i < num.length;i++){
            int index = (int)Math.floor((double)(num[i]-min)/gap);
            index = Math.min(index,gaps.length-1);

            // lower bound
            if(gaps[index].low == -1)
                gaps[index].low = num[i];
            else
                gaps[index].low = Math.min(gaps[index].low, num[i]);

            // upper bound
            if(gaps[index].high == -1)
                gaps[index].high = num[i];
            else
                gaps[index].high = Math.max(gaps[index].high, num[i]);
        }

        // find maximum gap
        for(int i = 0;i < gaps.length;i++){
            if(Engaged[i]){
                // check its inner gap
                maxGap = Math.max(gaps[i].high-gaps[i].low, maxGap);

                // lower all the way
                int j = i;
                while(--j >= 0){
                    if(Engaged[j])
                        break;
                }
                if(j >= 0)
                    maxGap = Math.max(gaps[i].low - gaps[j].high,maxGap);

                // upper all the way
                j = i;
                while(++j < num.length-2){
                    if(Engaged[j])
                        break;
                }
                if(j < gaps.length)
                    maxGap = Math.max(gaps[j].low - gaps[i].high, maxGap);
            }
        }

        return maxGap;
    }

    class Gap{
        int low;
        int high;
        Gap(){
            low = -1;
            high = -1;
        }
        Gap(int x,int y){
            low = x;
            high = y;
        }
    }
}

Fraction to Recurring Decimal

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)".

--------------------------------------------------- thinking --------------------------------------------------------------------

This problem should use hash table to record if a numerator has been repeating or not. Remember the interface of unordered_map<int, int>. And the hash key should be the numerator, while the value should be the position of current numerator!

-------------------------------------------------- problems ------------------------------------------------------------------

the overflow problem should be considered here!!! the plus-minus sign should also be considered here!! So it's very important to change the type from "int" to "long"

----------------------------------------------  codes --------------------------------------------------------------------------

class Solution {

public:

    string fractionToDecimal(int numerator, int denominator) {

        string result = "";

        if (numerator == 0) {

            return "0";

        }

        //calc symble

        if ((numerator<0)^(denominator<0)) {

            result += "-";

        }

        long n = abs(long(numerator));

        long d = abs(long(denominator));

        long r = n / d;

        result += to_string(r);

        if (n%d == 0) {

            return result;

        }

        result += ".";

        unordered_map<int, int> map;

        r = n % d;

        while (r) {

            if (map.count(r) > 0) {

                result.insert(map[r], 1, '(');

                result += ')';

                return result;

            }

            map[r] = result.size();

            r *= 10;

            long cur = r / d;

            result += to_string(cur);

            r = r % d;

        }

        return result;

    }

};

Dungeon Game

Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

--------------------------------------- thinking -------------------------------------------------------------------------

At the very beginning, I was thinking of this problem as DP problem, which is right. But the working direction is wrong. I was thinking of doing it on the increasing order. However, this problem should be resolved by back-forward order, from [m-1][n-1] to [0][0]. The reason is that we need to keep the minimum value at each step. If starting from the [0][0], it's hard to make decision which direction to go next!

--------------------------------------- problems ------------------------------------------------------------------------

the initialization of min_val[m-1] should be right considered!!

min_val[m-1] = max(1, 1 - dungeon[m-1][n-1])

--------------------------------------- codes -----------------------------------------------------------------------------

class Solution {

public:

    int calculateMinimumHP(vector<vector<int> > &dungeon) {

        //DP problem

        //get the maximum sum of the bottom-right grid

        if (dungeon.size() == 0) {

            return 1;

        }

        int m = dungeon[0].size();

        int n = dungeon.size();

        

        int i, j;

        vector<int> min_val(dungeon[n-1]);
        //bug here before

        min_val[m-1] = max(1, 1 - dungeon[n-1][m-1]);

        for (i = m - 2; i >= 0; i--) {

            min_val[i] = max(1, min_val[i+1] - dungeon[n-1][i]);

        }

        for (j = n - 2; j >= 0; j--) {

            min_val[m-1] = max(1, min_val[m-1] - dungeon[j][m-1]);

            for (i = m - 2; i >= 0; i--) {

                // here if we change to the codes below, the run time will improve a lot!

                //  int tmp = min_val[i] < min_val[i+1]?min_val[i]:min_val[i+1];
                //  min_val[i] = max(1, tmp - dungeon[j][i]);

                min_val[i] = max(1, min(min_val[i], min_val[i+1]) - dungeon[j][i]);

            }

        }

        return min_val[0];

    }

};

Binary Search Tree Iterator

Binary Search Tree Iterator

 Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

---------------------------------------------- think ------------------------------------------------------------

in-order traversal 

the usage of vector as stack

---------------------------------------------- codes --------------------------------------------------------------

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class BSTIterator {

private:

    vector<TreeNode*> stack;

public:

    BSTIterator(TreeNode *root) {

        while(root) {

            stack.push_back(root);

            root = root->left;

        }

    }

    /** @return whether we have a next smallest number */

    bool hasNext() {

        if (stack.size()) {

            return true;

        } else {

            return false;

        }

    }

    /** @return the next smallest number */

    int next() {

        TreeNode* nxt = stack.back();

        stack.pop_back();

        assert(nxt);

        int result = nxt->val;

        if (nxt->right) {

            stack.push_back(nxt->right);

            nxt = nxt->right;

            nxt = nxt->left;

            while (nxt) {

                stack.push_back(nxt);

                nxt = nxt->left;

            }

        }

        return result;

    }

};

/**

 * Your BSTIterator will be called like this:

 * BSTIterator i = BSTIterator(root);

 * while (i.hasNext()) cout << i.next();

 */

Compare Version Numbers

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

------------------------------------- think --------------------------------------------

About string to int, always remember that string can be "01" which will equal to 1 !!! Natural number doesn't allow the first bit to be 0, but string can.

------------------------------------------------------codes ------------------------------------------------------

class Solution {
public:
    int compareVersion(string version1, string version2) {
        string delimiter = ".";
        size_t pos1;
        size_t pos2;
        while ((pos1 = version1.find(delimiter)) != string::npos) {
            string v1 = version1.substr(0, pos1);
            pos2 = version2.find(delimiter);
            if (pos2 != string::npos) {
                string v2 = version2.substr(0, pos2);
                int num1 = stoi(v1);
                int num2 = stoi(v2);
                if (num1 > num2) {
                    return 1;
                } else if (num1 < num2) {
                    return -1;
                } else {
                    version1.erase(0, pos1 + delimiter.length());
                    version2.erase(0, pos2 + delimiter.length());
                }
            } else {
                if (stoi(v1) < stoi(version2)) {
                    return -1;
                } else if (stoi(v1) > stoi(version2)) {
                    return 1;
                } else {
                    version1.erase(0, pos1 + delimiter.length());
                    pos1 = version1.find(delimiter);
                    if (pos1 != string::npos) {
                        v1 = version1.substr(0, pos1);
                    } else {
                        v1 = version1;
                    }
                    if (stoi(v1) == 0) {
                        return 0;
                    } else {
                        return 1;
                    }
                }
            }
        }
     
        pos2 = version2.find(delimiter);
        if (pos2 != string::npos) {
            string v2 = version2.substr(0, pos2);
            if (stoi(version1) > stoi(v2)) {
                return 1;
            } else if (stoi(version1) < stoi(v2)) {
                return -1;
            } else {
                version2.erase(0, pos2+delimiter.length());
                pos2 = version2.find(delimiter);
                string v2;
                if (pos2 != string::npos) {
                    v2 = version2.substr(0, pos2);
                } else {
                    v2 = version2;
                }
                if (stoi(v2) == 0) {
                    return 0;
                } else {
                    return -1;
                }
            }
        } else {
            if (stoi(version1) < stoi(version2)) {
                return -1;
            } else if (stoi(version1) > stoi(version2)) {
                return 1;
            } else {
                return 0;
            }
        }
     
    }
};

----------------------------------------------------- good codes -----------------------------------------------
int compareVersion(string version1, string version2) { int m = version1.size(), n = version2.size(); int i = 0, j = 0; while (i < m && j < n) { int s1 = i; while(i < m && version1[i] != '.') ++i; string str1 = version1.substr(s1, i - s1); ++i; int s2 = j; while(j < n && version2[j] != '.') ++j; string str2 = version2.substr(s2, j - s2); ++j; int val1 = atoi(str1.c_str()); int val2 = atoi(str2.c_str()); if (val1 > val2) return 1; else if (val1 < val2) return -1; } while(i < m) { if (version1[i] != '.' && version1[i] != '0') return 1; ++i; } while(j < n) { if (version2[j] != '.' && version2[j] != '0') return -1; ++j; } return 0; }

--------------------------------------- good codes --------------------------------------------

My idea is to truncate the string by . mark, and compare the integer between every two .s. By adding some extra manipulation about string::npos, it's a valid and clean solution.

int compareVersion(string version1, string version2) {

    while (!version1.empty() || !version2.empty()) {

        string::size_type pos1 = version1.find('.');
        string::size_type pos2 = version2.find('.');

        string int1_str = version1.substr(0, pos1);
        string int2_str = version2.substr(0, pos2);

        int int1 = (int1_str.empty()) ? 0 : std::stoi(int1_str);
        int int2 = (int2_str.empty()) ? 0 : std::stoi(int2_str);

        if (int1 > int2) return 1;

        else if (int1 < int2) return -1;

        else {

            version1 = (pos1 == string::npos) ? "" : version1.substr(pos1 + 1);
            version2 = (pos2 == string::npos) ? "" : version2.substr(pos2 + 1);

        }

    }

    return 0;
}