2019-12-15

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, start = 0, n = tree.size();
        unordered_map<int, int> fruitPos;
        for (int i = 0; i < n; ++i) {
            fruitPos[tree[i]] = i;
            while (fruitPos.size() > 2) {
                if (fruitPos[tree[start]] == start) {
                    fruitPos.erase(tree[start]);
                }
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};

Sum of Subarray Minimums

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int res = 0, n = A.size(), M = 1e9 + 7;
        stack<pair<int, int>> st_pre, st_next;
        vector<int> left(n), right(n);
        for (int i = 0; i < n; ++i) {
            while (!st_pre.empty() && st_pre.top().first > A[i]) {
                st_pre.pop();
            }
            left[i] = st_pre.empty() ? (i + 1) : (i - st_pre.top().second);
            st_pre.push({A[i], i});
            right[i] = n - i;
            while (!st_next.empty() && st_next.top().first > A[i]) {
                auto t = st_next.top(); st_next.pop();
                right[t.second] = i - t.second;
            }
            st_next.push({A[i], i});
        }
        for (int i = 0; i < n; ++i) {
            res = (res + A[i] * left[i] * right[i]) % M;
        }
        return res;
    }
};

super palindrome

class Solution {
public:
    int superpalindromesInRange(string L, string R) {
        int res = 0;
        long left = stol(L), right = stol(R);
        helper("", left, right, res);
        for (char c = '0'; c <= '9'; ++c) {
            helper(string(1, c), left, right, res);
        }
        return res;
    }
    void helper(string cur, long& left, long& right, int& res) {
        if (cur.size() > 9) return;
        if (!cur.empty() && cur[0] != '0') {
            long num = stol(cur);
            num *= num;
            if (num > right) return;
            if (num >= left && isPalindrome(to_string(num))) ++res;
         }
         for (char c = '0'; c <= '9'; ++c) {
            helper(string(1, c) + cur + string(1, c), left, right, res);
        }
    }
    bool isPalindrome(string str) {
        int left = 0, right = (int)str.size() - 1;
        while (left < right) {
            if (str[left++] != str[right--]) return false;
        }
        return true;
    }
};