Day 91, #159 #173, Longest Substring with At Most Two Distinct Characters, Binary Search Tree Iterator

Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.
------------------------------------------------------
have two counters for each char, once a third char comes in, exhaust either counter, then set it to the third char

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        char first = '\0', second = '\0';
        int count1 = 0, count2 = 0;
        int start = 0,longest = 0;
        for (int i = 0; i < s.length(); i++) {
            if (count1 == 0 && count2 == 0) {
                first = s[i];
                count1++;
            }else if (count2 == 0 && first != s[i]) {
                second = s[i];
                count2++;
            }else if (first == s[i]) {
                count1++;
            }else if (second == s[i]) {
                count2++;
            }else {
                while (true) {
                    if (s[start] == first) count1--;
                    else count2--;
                    start++;
                    if (count1 == 0) {
                        first = s[i];
                        count1 = 1;
                        break;
                    }
                    if (count2 == 0) {
                        second = s[i];
                        count2 = 1;
                        break;
                    }
                }
            }
            
            longest = max(longest,i - start + 1);
        }
        
        return longest;
    }
};

网上看到的,i, j 记录2个不同char的最新位置

int lengthOfLongestSubstringTwoDistinct(string s) {
        int i = 0, j = -1;
        int maxLen = 0;
        for (int k = 1; k < s.size(); k++) {
            if (s[k] == s[k-1]) continue;
            if (j > -1 && s[k] != s[j]) {
                maxLen = max(maxLen, k - i);
                i = j + 1;
            }
            j = k - 1;
        }
        return maxLen > (s.size() - i) ? maxLen : s.size() - i;
    }

更新

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char,int> dic;
        int start = 0, longest = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (dic.find(s[i]) != dic.end()) {
                dic[s[i]]++;
            }else {
                dic[s[i]] = 1;
            }
            while (dic.size() > 2) {
                dic[s[start]]--;
                if (dic[s[start]] == 0) {
                    dic.erase(s[start]);
                }
                start++;
            }
            longest = max(longest,i - start + 1);
        }
        
        return longest;
    }
};

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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases. ----------------------------------------------------------------

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        TreeNode *p = root;
        
        while (p != NULL) {
            st.push(p);
            p = p->left;
        }
        
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return st.size() > 0;
    }

    /** @return the next smallest number */
    int next() {
        if (st.empty()) throw exception();
        TreeNode *rt = st.top();
        TreeNode *p = rt->right;
        st.pop();
        
        while (p != NULL) {
            st.push(p);
            p = p->left;
        }
        
        return rt->val;
    }
private: 
    stack<TreeNode *> st;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

Another implementation

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        current = root;
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !st.empty() || current != NULL;
    }

    /** @return the next smallest number */
    int next() {
        while (current != NULL) {
            st.push(current);
            current = current->left;
        }
        
        current = st.top();
        st.pop();
        int rt = current->val;
        current = current->right;
        return rt;
    }
private:
    stack<TreeNode*> st;
    TreeNode *current;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

更新

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        this->root = root;
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !st.empty() || root != NULL;
    }

    /** @return the next smallest number */
    int next() {
        while (!st.empty() || root) {
            if (root != NULL) {
                st.push(root);
                root = root->left;
            }else {
                TreeNode *rt = st.top();
                st.pop();
                root = rt->right;
                return rt->val;
            }
        }
    }
private:
    stack<TreeNode *> st;
    TreeNode *root;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

Java, Jun-14-2018

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {
    
    private Stack st;

    public BSTIterator(TreeNode root) {
        st = new Stack<>();
        pushToStack(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !st.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode cur = st.pop();
        pushToStack(cur.right);
        
        return cur.val;
    }
    
    private void pushToStack(TreeNode root) {
        while (root != null) {
            st.push(root);
            root = root.left;
        }
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */