Shawn's Blog

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int i = 1, x1 = 0, y1 = 0, x2 = n -1, y2 = n - 1;
        while (n > 1) {
            int x = x1, y = y1;
            while (y < y2)
                ans[x][y++] = i++;
            while (x < x2)
                ans[x++][y] = i++;
            while (y > y1)
                ans[x][y--] = i++;
            while (x > x1)
                ans[x--][y] = i++;
            ++x1;
            ++y1;
            --x2;
            --y2;
            n -= 2;
        }
        if (n & 1)
            ans[x1][y1] = i;
        return ans;
    }
};

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int left = 0;
        int right = matrix[0].size() - 1;
        int top = 0;
        int bottom = matrix.size() - 1;
        vector<int> ans;
        while (true) {
            for (int i = left; i <= right; ++i)
                ans.push_back(matrix[top][i]);
            if (++top > bottom) break;
            for (int i = top; i <= bottom; ++i)
                ans.push_back(matrix[i][right]);
            if (--right < left) break;
            for (int i = right; i >= left; --i)
                ans.push_back(matrix[bottom][i]);
            if (--bottom < top) break;
            for (int i = bottom; i >= top; --i)
                ans.push_back(matrix[i][left]);
            if (++left > right) break;
        }
        return ans;
    }
};

class MyHashMap {
private:
    vector<list<pair<int, int>>> data;
    static const int base = 769;
    static int hash(int key) {
        return key % base;
    }
public:
    MyHashMap(): data(base) {
    }
    void put(int key, int value) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it)
            if ((*it).first == key) {
                (*it).second = value;
                return;
            }
        data[h].emplace_back(key, value);
    }
    int get(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it)
            if ((*it).first == key)
                return (*it).second;
        return -1;
    }
    void remove(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it)
            if ((*it).first == key) {
                data[h].erase(it);
                return;
            }
    }
};

class MyHashSet {
private:
    vector<list<int>> data;
    static const int base = 769;
    static int hash(int key) {
        return key % base;
    }
public:
    MyHashSet(): data(base) {
    }
    void add(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it)
            if ((*it) == key)
                return;
        data[h].push_back(key);
    }
    void remove(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it)
            if ((*it) == key) {
                data[h].erase(it);
                return;
            }
    }
    bool contains(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); ++it)
            if ((*it) == key)
                return true;
        return false;
    }
};

class Solution {
public:
    int calculate(string s) {
        vector<int> stk;
        char preSign = '+';
        int n = s.length(), num = 0;
        for (int i = 0; i < n; ++i) {
            if (isdigit(s[i]))
                num = num * 10 + (s[i] - '0');
            if ((!isdigit(s[i]) && s[i] != ' ') || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stk.push_back(num);
                        break;
                    case '-':
                        stk.push_back(-num);
                        break;
                    case '*':
                        stk.back() *= num;
                        break;
                    case '/':
                        stk.back() /= num;
                }
                preSign = s[i];
                num = 0;
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};

class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        int cur = 0, sign = 1, ans = 0;
        for (char c : s) {
            if (c == ' ') continue;
            else if (c == '+') {
                ans += sign * cur;
                cur = 0;
                sign = 1;
            } else if (c == '-') {
                ans += sign * cur;
                cur = 0;
                sign = -1;
            } else if (c == '(') {
                stk.push(ans);
                stk.push(sign);
                ans = 0;
                sign = 1;
            } else if (c == ')') {
                ans += sign * cur;
                cur = 0;
                ans *= stk.top(); stk.pop();
                ans += stk.top(); stk.pop();
            } else { // digit
                cur = cur * 10 + (c - '0');
            }
        }
        if (cur != 0) ans += sign * cur;
        return ans;
    }
};

class Solution {
public:
    string removeDuplicates(string S) {
        string stk;
        for (char c : S)
            if (!stk.empty() && stk.back() == c)
                stk.pop_back();
            else
                stk.push_back(c);
        return stk;
    }
};

class Solution {
public:
    int beautySum(string s) {
        const int n = s.size();
        int ans = 0;
        vector<int> dp(26);
        map<int, int> m;
        for (int i = 0; i < n; ++i) {
            fill(dp.begin(), dp.end(), 0);
            m.clear();
            for (int j = i; j < n; ++j) {
                const int c = ++dp[s[j] - 'a'];
                ++m[c];
                if (c > 1) {
                    auto it = m.find(c - 1);
                    if (--it->second == 0)
                        m.erase(it);
                }
                ans += m.rbegin()->first - m.begin()->first;
            }
        }
        return ans;
    }
};