Leetcode summary of 20200209-20200216

// 682. Baseball Game
class Solution {
public:
    int calPoints(vector<string>& ops) {
        vector<int> res;
        for_each(
            begin(ops),
            end(ops),
            [&](const string& op) {
                if (op == "C") {
                    res.pop_back();
                } else if (op == "D") {
                    res.push_back(2 * res.back());
                } else if (op == "+") {
                    res.push_back(res.back() + *(prev(res.end(), 2)));
                } else {
                    res.push_back(stoi(op));
                }
            }
        );

        return accumulate(begin(res), end(res), 0);
    }
};

// 762. Prime Number of Set Bits in Binary Representation
class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        function<bool(int)> is_prime = [](int n) {
            if (n < 2) return false;
            if (n < 4) return true;
            if (n%2 == 0 || n % 3 == 0) return false;
            int i = 5;
            int w = 2;
            while (i * i <= n) {
                if (n % i == 0) return false;
                i += w;
                w = 6 - w;
            }
            return true;
        };
        function<int(int)> bit_num = [](int n) {
            int cnt = 0;
            while (n != 0) {
                ++cnt;
                n &= (n-1);
            }
            return cnt;
        };
        int cnt = 0;
        for (int i = L; i <= R; ++i) {
            int n = bit_num(i);
            if (is_prime(n)) ++cnt;
        }
        return cnt;
    }
};

// 812. Largest Triangle Area
class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int size = points.size();
        typedef vector<int> V;
        function<double(V&, V&, V&)> area = [](V& a, V& b, V& c) {
            double area = a[0]*(b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0]*(a[1] - b[1]);
            return abs(area/2);
        };
        double m = -1.0;
        for (int i = 0; i < size - 2; ++i) {
            for (int j  = i + 1; j < size - 1; ++j) {
                for (int k = j + 1; k < size; ++k) {
                    double t = area(points[i], points[j], points[k]);
                    if (t > m) {
                        m = t;
                    }
                }
            }
        }
        return m;
    }
};

// 821. Shortest Distance to a Character
class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        vector<int> res;
        int size = S.size();
        int prev = -size;
        int cur = 0;
        while (S[cur] != C) ++cur;
        for (int i = 0; i < size; ++i) {
            if (i == cur) {
                res.push_back(0);
                prev = cur;
                ++cur;
                while (cur < size && S[cur] != C) ++cur;
                if (cur == size) cur *= 2;
            } else {
                res.push_back(min(i - prev, cur - i));
            }
        }

        return res;
    }
};

// 1154. Day of the Year
class Solution {
public:
    int dayOfYear(string date) {
        vector<int> time(3);
        int size = date.size();
        vector<vector<int>> cols{
            {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
            {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
        };
        time[0] = stoi(date.substr(0, 4));
        time[1] = stoi(date.substr(5, 2));
        time[2] = stoi(date.substr(8, 2));
        function<bool(int)> is_leap_year = [](int y) {
            if (y % 100 != 0) return y % 4 == 0;
            else return y % 400 == 0;
        };
        vector<int>& col = cols[is_leap_year(time[0])];
        return accumulate(begin(col), next(begin(col), time[1]-1), 0) + time[2];

    }
};

// 706. Design HashMap
class MyHashMap {
    unordered_map<int, int> _joking;
public:
    /** Initialize your data structure here. */
    MyHashMap() {

    }

    /** value will always be non-negative. */
    void put(int key, int value) {
        _joking[key] = value;
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        if (_joking.find(key) != _joking.end()) {
            return _joking[key];
        }
        return -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        _joking[key] = -1;
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

// 766. Toeplitz Matrix
class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int i = m - 1, j = 0;
        bool less_0 = false;
        while (j < n) {
            // from (i, j) -> (m, j + (m-i))
            int i_e = m, j_e = min(j + m - i, n);
            int val = matrix[i][j];
            for (int k = i, l = j; k < i_e && l < j_e; ++k, ++l) {
                if (matrix[k][l] != val) return false;
            }
            if (i > 0) {
                --i;
            } else if (i == 0) {
                if (less_0) ++j;
                less_0 = true;
            }
        }
        return true;
    }
};

// 868. Binary Gap
class Solution {
public:
    int binaryGap(int N) {
        int s = -1;
        int pos = 0;
        int m = 0;
        while (N != 0) {
            int bit = N & 0x1;
            if (bit == 1) {
                if (s == -1) s = pos;
                m = max(m, pos - s);
                s = pos;
            }
            N >>= 1;
            ++pos;
        }
        return m;
    }
};

// 867. Transpose Matrix
class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& A) {
        int m = A.size();
        int n = A[0].size();
        vector<vector<int>> res;
        for (int i = 0; i < n; ++i) {
            vector<int> col;
            for (int j = 0; j < m; ++j) {
                col.push_back(A[j][i]);
            }
            res.push_back(col);
        }
        return res;
    }
};

// 830. Positions of Large Groups
class Solution {
public:
    vector<vector<int>> largeGroupPositions(string S) {
        vector<vector<int>> res;
        int size = S.size();
        for (int i = 0; i < size;) {
            int j = i;
            while (j < size && S[j] == S[i]) ++j;
            if (j - i >= 3) {
                res.push_back({i, j - 1});
            }
            i = j;
        }
        return res;
    }
};

// 1046. Last Stone Weight
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(stones.begin(), stones.end());
        while (pq.size() > 1) {
            auto y = pq.top(); pq.pop();
            auto x = pq.top(); pq.pop();
            if (x == y) continue;
            else pq.push(y - x);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

// 1078. Occurrences After Bigram
class Solution {
public:
    vector<string> findOcurrences(string text, string first, string second) {
        istringstream iss(text);
        vector<string> s;
        vector<string> res;
        copy(istream_iterator<string>(iss), istream_iterator<string>(), back_inserter(s));
        if (s.size() < 3) return res;
        int index = 2;
        for_each(
            next(begin(s), 2),
            end(s),
            [&](const string& ss) {
                // cout << "ss: " << ss << endl;
                bool x = s[index-1].compare(second) == 0;
                x = x && s[index-2].compare(first) == 0;
                if (x) res.push_back(ss);
                ++index;
            }
        );
        return res;
    }
};

// 1089. Duplicate Zeros
class Solution {
public:
    void duplicateZerosCopy(vector<int>& arr) {
        int i = 0, j = 0;
        int size = arr.size();
        vector<int> cpy(arr.begin(), arr.end());
        for (int j = 0; j < size;) {
            if (cpy[j] != 0) {
                arr[i++] = cpy[j++];
            } else {
                arr[i++] = cpy[j++];
                if (i >= size) break;
                arr[i++] = 0;
            }
            if (i >= size) break;
        }
    }
    void duplicateZeros(vector<int>& arr) {
        int size = arr.size();
        int shifts = 0;
        int i = 0;
        for (; i < size; ++i) {
            if (i + shifts >= size) break;
            if (arr[i] == 0) ++shifts;
        }
        --i;
        // cout << "i: " << i << " arr[i]: " << arr[i] << endl;
        int j = size - 1;
        while (i >= 0) {
            if (arr[i] != 0) {
                arr[j--] = arr[i--];
            } else {
                int k = i;
                arr[j--] = arr[i--];
                if (k + shifts < size) arr[j--] = 0;
            }
            // if (j < 0) break;
        }
        // [1,0,0,2,3,4,0]
        // [0,1,2,2,2,]
        // []
    }
};

// 1137. N-th Tribonacci Number
class Solution {
public:
    int tribonacci(int n) {
        vector<int> p{0, 1, 1};
        if (n < 3) return p[n];
        for (int i = 3; i <= n; ++i) {
            int sum = p[0] + p[1] + p[2];
            p[0] = p[1];
            p[1] = p[2];
            p[2] = sum;
        }
        return p[2];
    }
};

// 1160. Find Words That Can Be Formed by Characters
class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        char m[27] = {0};
        for_each(begin(chars), end(chars), [&](char c) {++m[c - 'a'];});
        int sum = 0;
        for_each(
            begin(words),
            end(words),
            [&](const string& s) {
               char mm[27] = {0};
               bool res = true;
               for_each(begin(s), end(s), [&](char c) {
                   auto x = c - 'a';
                   ++mm[x];
                   res &= (mm[x] <= m[x]);
               });
               if (res) sum += s.size();
            }
        );
        return sum;
    }
};

// 1175. Prime Arrangements
class Solution {
    static constexpr int kMod = 1e9 + 7;
    // 5
    // 1 2 3 4 5
    // A(3 * 3) * A(2,2)
public:
    int numPrimeArrangements(int n) {
        function<bool(int)> is_prime = [](int n) {
            if (n < 2) return false;
            if (n < 4) return true;
            if (n % 2 == 0 || n % 3 == 0) return false;
            int w = 2;
            int i = 5;
            while (i * i <= n) {
                if (n % i == 0) return false;
                i += w;
                w = 6 - w;
            }
            return true;
        };
        function<long long(int, int)> m = [](int n, int m) {
            // m out of n
            long long res = 1;
            while (m <= n) {
                res %= kMod;
                res *= m;
                ++m;
            }
            return res;
        };
        vector<bool> s(n+1, false);
        s[2] = false;
        s[0] = true;
        s[1] = true;
        for (int i = 2; i <= n; ++i) {
            if (!s[i]) {
                for (int j = i * 2; j<= n; j += i) {
                    s[j] = true;
                }
            }
        }
        int a = count(begin(s), end(s), false);
        int b = n - a;
        // cout << "a: " << a << " b: " << b << endl;
        // A(prime_pos, prime_pos) * A(non_prime_pos, non_prime_pos)
        return (m(a, 1) % kMod) * (m(b, 1) % kMod) % kMod;

    }
};

// 1170. Compare Strings by Frequency of the Smallest Character
class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        function<int(const string&)> f = [](const string& s) {
            map<char, int> m;
            for_each(begin(s), end(s), [&](char c) { ++m[c];});
            return (*begin(m)).second;
        };
        vector<int> dst;
        for_each(begin(words), end(words),
                [&](const string& s) { dst.push_back(f(s));});
        sort(begin(dst), end(dst));
        vector<int> res;
        for_each(begin(queries), end(queries),
                 [&](const string& s) {
                     int cnt = f(s);
                     auto x = upper_bound(begin(dst), end(dst), cnt);
                     res.push_back(distance(x, end(dst)));
                 }
        );
        return res;
    }
};

// 1184. Distance Between Bus Stops
class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        int sum = accumulate(begin(distance), end(distance), 0);
        auto b = begin(distance);
        if (start > destination) swap(start, destination);
        int diff = accumulate(next(b, start), next(b, destination), 0);
        return min(diff, sum - diff);
    }
};

// 1189. Maximum Number of Balloons
class Solution {
public:
    int maxNumberOfBalloons(string text) {
        string s = "balloon";
        unordered_map<char, int> m;
        for_each(begin(s), end(s), [&](char c) {m[c] = 0;});
        for_each(
            begin(text),
            end(text),
            [&](char c) { if (m.find(c) != m.end()) {++m[c];}}
        );
        vector<int> t;
        for_each(begin(m), end(m),
                 [&](auto c) {
                     int x = c.second;
                     if (c.first == 'l' || c.first == 'o') x /= 2;
                     t.push_back(x);
                 });
        return *min_element(t.begin(), t.end());
    }
};

// 1200. Minimum Absolute Difference
class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        vector<vector<int>> res;
        int min_d = INT_MAX;
        int size = arr.size();
        for (int i = 1; i < size; ++i) {
            int d = arr[i] - arr[i-1];
            if (d < min_d) {
                min_d = d;
                res.clear();
                res.push_back({arr[i-1], arr[i]});
            } else if (d == min_d) {
                res.push_back({arr[i-1], arr[i]});
            }
        }
        return res;
    }
};

// 1207. Unique Number of Occurrences
class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> m;
        for_each(
            arr.begin(),
            arr.end(),
            [&](int c) {++m[c];}
        );
        unordered_set<int> s;
        for_each(
            m.begin(),
            m.end(),
            [&](auto x) {s.insert(x.second);}
        );
        return s.size() == m.size();
    }
};

// 1217. Play with Chips
class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        int odd = 0;
        int even = 0;
        for_each(
            chips.begin(),
            chips.end(),
            [&](int c){
                (c & 0x1) ? ++odd:++even;
            }
        );
        return min(odd, even);
    }
};

// 1221. Split a String in Balanced Strings
class Solution {
public:
    int balancedStringSplit(string s) {
        int l = 0, r = 0;
        int cnt = 0;
        for (char c : s) {
            if (c == 'L') {
                ++l;
            } else if (c == 'R') {
                ++r;
            }
            if (l == r) {
                l = 0;
                r = 0;
                ++cnt;
            }
        }
        return cnt;
    }
};

// 1232. Check If It Is a Straight Line
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        sort(begin(coordinates), end(coordinates));
        int size = coordinates.size();
        int x_diff = coordinates[1][0] - coordinates[0][0];
        int y_diff = coordinates[1][1] - coordinates[0][1];
        for (int i = 2; i < size; ++i) {
            int x = coordinates[i][0] - coordinates[0][0];
            int y = coordinates[i][1] - coordinates[0][1];
            if (x_diff == 0 && x != 0) return false;
            else if (y_diff == 0 && y != 0) return false;
            else if (x * y_diff != x_diff * y) return false;
        }
        return true;
    }
};

// 1237. Find Positive Integer Solution for a Given Equation
/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 * public:
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     int f(int x, int y);
 * };
 */

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        int x = 1, y = 1000;
        vector<vector<int>> res;
        while (x <= 1000 && y >= 1) {
            if (customfunction.f(x, y) < z) {
                ++x;
            } else if (customfunction.f(x, y) > z) {
                --y;
            } else {
                res.push_back({x, y});
                --y;
                ++x;
            }
        }

        return res;
    }
};

// 1260. Shift 2D Grid
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        typedef vector<int> V;
        typedef vector<V> VV;
        int m = grid.size();
        int n = grid[0].size();
        int total = m * n;
        k = k % total;
        if (k == 0) return grid;
        function<void(int s, int e)> reverse = [&](int s, int e) {
            while (s <= e) {
                swap(grid[s/n][s%n], grid[e/n][e%n]);
                ++s; --e;
            }
        };
        reverse(total - k, total - 1);
        reverse(0, total - k - 1);
        reverse(0, total - 1);
        return grid;
    }
};

// 1252. Cells with Odd Values in a Matrix
class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<int> rows(n, 0);
        vector<int> cols(m, 0);
        for (auto& indice: indices) {
            ++rows[indice[0]];
            ++cols[indice[1]];
        }
        int odd_sum = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                auto sum = rows[i] + cols[j];
                odd_sum += (sum % 2);
            }
        }
        return odd_sum;
    }
};

// 1275. Find Winner on a Tic Tac Toe Game
class Solution {

public:
    string tictactoe(vector<vector<int>>& moves) {
        int size = moves.size();
        vector<vector<int>> board(3, vector<int>(3, -100));
        int who = true;
        for (auto& move: moves) {
            int r = move[0];
            int c = move[1];
            board[r][c] = who;
            who = !who;
        }
        for (int i = 0; i < 3; ++i) {
            int col_sum = 0;
            int row_sum = 0;
            for (int j = 0; j < 3; ++j) {
                // each row
                row_sum += board[i][j];
                col_sum += board[j][i];
            }
            if (row_sum == 0) return "B";
            else if (row_sum == 3) return "A";
            if (col_sum == 0) return "B";
            else if (col_sum == 3) return "A";
        }
        int x = board[0][0] + board[1][1] + board[2][2];
        int y = board[0][2] + board[1][1] + board[2][0];
        if (x == 0) return "B";
        else if (x == 3) return "A";
        if (y == 0) return "B";
        else if (y == 3) return "A";
        return size == 9 ? "Draw": "Pending";
    }
};

// 1281. Subtract the Product and Sum of Digits of an Integer
class Solution {
public:
    int subtractProductAndSum(int n) {
        if (n == 0) return 0;
        int mul = 1;
        int sum = 0;
        while (n != 0) {
            int r = n % 10;
            sum += r;
            mul *= r;
            n /= 10;
        }
        return mul - sum;
    }
};

// 1287. Element Appearing More Than 25% In Sorted Array
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        auto b = arr.begin();
        int size = arr.size();
        double quad = size / 4.0;
        auto e = arr.end();
        while (b != e) {
            auto u = upper_bound(b, e, *b);
            int n = distance(b, u);
            if (n > quad) return *b;
            else b = u;
        }
        return -1;
    }
};

// 65. Valid Number
class Solution {
public:
    bool isNumber(const string& s) {
        if (s.empty()) return false;
        int i = 0;
        int j = s.size() - 1;
        while (i <= j && s[i] == ' ') ++i;
        while (j >= i && s[j] == ' ') --j;
        if (i > j) return false;
        if (s[i] == '+' || s[i] == '-') ++i;
        if (s[i] == 'e') return false;
        bool has_e = false;
        bool allow_dot = true;
        while (i <= j) {
            if (has_e && s[i] == 'e') return false;
            if (!allow_dot && s[i] == '.') return false;
            if (s[i] == '.') {
                allow_dot = false;
                bool prev = false, next = false;
                if (i > 0 && s[i-1] >= '0' && s[i-1] <= '9') prev = true;
                if (i < j && s[i+1] >= '0' && s[i+1] <= '9') next = true;
                if (!(prev || next)) return false;
            } else if (s[i] == 'e') {
                has_e = true;
                allow_dot = false;
                if (i == j) return false;
                if (s[i+1] == '+' || s[i+1] == '-') ++i;
                if (i == j) return false;
            } else if (s[i] > '9' || s[i] < '0') {
                return false;
            }
            ++i;

        }
        return true;
    }
};

// 1093. Statistics from a Large Sample
class Solution {
public:
    vector<double> sampleStats(vector<int>& count) {
        double mx = INT_MIN;
        double mn = INT_MAX;
        double mode = 0;
        double cnt_max = 0;
        int cnt_all = 0;
        double median = 0;
        double mean = 0;
        double sum = 0;
        int size = count.size();
        for (int i = 0; i < size; ++i) {
            if (!count[i]) continue;
            if (i > mx) mx = i;
            if (i < mn) mn = i;
            if (count[i] > cnt_max) {
                cnt_max = count[i];
                mode = i;
            }
            cnt_all += count[i];
            sum += count[i] * i;
        }

        if (cnt_all % 0x1 == 1) {
            // odd
            int half = cnt_all / 2; // 11 / 2 = 5
            int cnt = 0;
            for (int i = 0; i < size; ++i) {
                if (!count[i]) continue;
                cnt += count[i];
                if (cnt >= half) {
                    median = i;
                    break;
                }
            }
        } else {
            // even
            int half = cnt_all / 2; // 10 / 2 = 5
            int cnt = 0;
            for (int i = 0; i < size; ++i) {
                if (!count[i]) continue;
                cnt += count[i];
                if (cnt == half) {
                    int j = i + 1;
                    median = i;
                    while (j < size && count[j] == 0) ++j;
                    if (j < size) {
                        median = (median + j) / 2;
                    }
                    // cout << "median: " << median << "i: " << i << " j: " << j << endl;
                    break;
                } else if (cnt > half) {
                    median = i;
                    break;
                }
            }
        }
        mean = sum / cnt_all;
        return {mn, mx, mean, median, mode};
    }
};

// 134. Gas Station
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0;
        int cur_sum = 0;
        int cur_index = 0;
        int size = cost.size();
        for (int i = 0; i < size; ++i) {
            cur_sum += gas[i] - cost[i];
            if (cur_sum < 0) {
                cur_sum = 0;
                cur_index = i + 1;
            }
            total += gas[i] - cost[i];
        }
        return total < 0 ? -1 : cur_index;
    }
};

// 32. Longest Valid Parentheses
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int m = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                } else {
                    m = max(m, i - st.top());
                }
            }
        }
        return m;
    }
};

// 36. Valid Sudoku
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row = board.size();
        int col = board[0].size();
        bitset<10> bit;
        // validate each row
        for (int i = 0; i < row; ++i) {
            bit.reset();
            for (int j = 0; j < col; ++j) {
                if (board[i][j] == '.') continue;
                int n = board[i][j] - '0';
                if (bit.test(n)) return false;
                bit.set(n, true);
            }
        }

        // validate each col
        for (int i = 0; i < col; ++i) {
            bit.reset();
            for (int j = 0; j < row; ++j) {
                if (board[j][i] == '.') continue;
                int n = board[j][i] - '0';
                if (bit.test(n)) return false;
                bit.set(n, true);
            }
        }

        // validate cell
        for (int i = 0; i < row; i += 3) {
            for (int j = 0; j < col; j += 3) {
                bit.reset();
                // (i,j) --> (i+3, j+3)
                for (int k = i; k < i + 3; ++k) {
                    for (int l = j; l < j + 3; ++l) {
                        if (board[k][l] == '.') continue;
                        int n = board[k][l] - '0';
                        if (bit.test(n)) return false;
                        bit.set(n, true);
                    }
                }
            }
        }
        return true;
    }
};

// 43. Multiply Strings
class Solution {
public:
    static string add(const string& num1, const string& num2) {
        if (num1.empty()) return num2;
        if (num2.empty()) return num1;
        int size1 = num1.size();
        int size2 = num2.size();
        int i = size1 - 1;
        int j = size2 - 1;
        string result;
        int carry = 0;
        while (i >= 0 || j >= 0) {
            int left = i >= 0 ? num1[i--] - '0' : 0;
            int right = j >= 0 ? num2[j--] - '0' : 0;
            int sum = left + right + carry;
            result += (sum % 10) + '0';
            carry = sum / 10;
        }
        if (carry) result += carry + '0';
        reverse(result.begin(), result.end());
        return result;
    }

    string multiply_by_one(const string& num, char c) {
        if (c == '0') return "0";
        if (c == '1') return num;
        int size = num.size();
        int carry = 0;
        int j = size - 1;
        string result;
        int cc = c - '0';
        while (j >= 0) {
            int sum = (num[j] - '0') * cc + carry;
            result += (sum%10) + '0';
            carry = sum / 10;
            --j;
        }
        if (carry) result += carry + '0';
        reverse(result.begin(), result.end());
        return result;
    }
    string multiply(string num1, string num2) {
        vector<string> tmp;
        if (num1.size() < num2.size()) num1.swap(num2);
        auto b = num2.rbegin();
        auto e = num2.rend();
        int i = 0;
        while (b != e) {
            string t = multiply_by_one(num1, *b);
            int k = i;
            while (k--) t.push_back('0');
            tmp.push_back(t);
            ++i;

            ++b;
        }
        return accumulate(tmp.begin(), tmp.end(), string(""), add);
    }
};

// 42. Trapping Rain Water
class Solution {
public:
    int trap(vector<int>& heights) {
        stack<pair<int,int> > st;
        int size = heights.size();
        int water = 0;
        for (int i = 0; i < size; ++i) {
            int height = 0;
            while (!st.empty()) {
                auto bar = st.top().first;
                auto index = st.top().second;
                water += (min(bar, heights[i]) - height) * (i - st.top().second - 1);

                height = bar;
                if (height > heights[i]) break;
                else st.pop();
            }
            st.push(make_pair(heights[i], i));
        }
        return water;
    }
};

// 1266. Minimum Time Visiting All Points
class Solution {
    typedef vector<int> V;
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        function<int(const V&, const V&)> f = [](const V& p1, const V& p2)-> int {
            int x1 = p1[0], y1 = p1[1];
            int x2 = p2[0], y2 = p2[1];
            int d1 = int(abs(x2 - x1));
            int d2 = int(abs(y2 - y1));
            return max(d1, d2);
        };
        int total = 0;
        int size = points.size();
        for (int i = 0; i < size - 1; ++i) {
            total += f(points[i], points[i+1]);
        }
        return total;
    }
};

// 1346. Check If N and Its Double Exist
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> s(begin(arr), end(arr));
        int zero = 0;
        for (int& a : arr) {
            if (a == 0) {
                ++zero;
                if (zero > 1) return true;
            } else if ((a & 0x1) == 0) {
                if (s.find(a / 2) != s.end()) return true;
            }
        }
        return false;
    }
};

// 1342. Number of Steps to Reduce a Number to Zero
class Solution {
public:
    int numberOfSteps (int num) {
        int steps = 0;
        while (num != 0) {
            if ((num & 0x1) == 0) num /= 2;
            else {num -= 1; num /= 2;steps += (num!=0);}
            ++ steps;
        }
        return steps;
    }
};

// 1331. Rank Transform of an Array
class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<pair<int, int> > t;
        int size = arr.size();
        for (int i = 0; i < size; ++i) {
            t.push_back({arr[i], i});
        }
        sort(t.begin(), t.end());
        int rank = 0;
        int prev = 0;
        vector<int> res(size, 0);
        for(auto& p : t) {
            if (rank == 0) {
                prev = p.first;
                rank = 1;
                res[p.second] = rank;
            } else if (p.first == prev) {
                res[p.second] = rank;
            } else {
                ++rank;
                res[p.second] = rank;
                prev = p.first;
            }
        }
        return res;
    }
};

// 1332. Remove Palindromic Subsequences
class Solution {
public:
    int removePalindromeSub(string s) {
        if (s.empty()) return 0;
        function<bool()> is_p = [&]() {
            int i = 0, j = s.size() - 1;
            while (i <= j && s[i] == s[j]) {
                ++i;--j;
            }
            return i > j;
        };
        return is_p() ? 1 : 2;
    }
};

// 1337. The K Weakest Rows in a Matrix
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int m = mat.size();
        int n = mat[0].size();
        int i = 0;
        vector<int> res(k);
        for_each(mat.begin(), mat.end(), [&](vector<int>& v) {v.push_back(i++);});
        sort(mat.begin(), mat.end());

        i = 0;
        generate(res.begin(), res.end(), [&]() {return mat[i++].back();});
        return res;
    }
};

// 1323. Maximum 69 Number
class Solution {
public:
    int maximum69Number (int num) {
        string s = to_string(num);
        int size = s.size();
        for (int i = 0; i < size; ++i) {
            if (s[i] == '6') {
                s[i] = '9';
                break;
            }
        }
        return stoi(s);
    }
};

// 1317. Convert Integer to the Sum of Two No-Zero Integers
class Solution {
public:
    vector<int> getNoZeroIntegers(int n) {
        // 602
        // 1 9 1
        // 1 1 4
        // 100
        // 1 4
        // 9 5

        // 200
        // 1 1 1
        // 9 8
        string s1, s2;
        while (n != 0) {
            int remain = n % 10;
            if (n == 1) {
                s1 += '1';
                break;
            } else if (remain < 2) {
                s1 += '9';
                s2 += '1' + remain;
                n /= 10;
                --n;
            } else {
                s1 += '1';
                s2 += remain - 1 + '0';
                n /= 10;
            }
        }
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        return {stoi(s1), stoi(s2)};
    }
};

// 1304. Find N Unique Integers Sum up to Zero
class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> res(n, 0);
        auto b = res.begin();
        if ((n & 0x1) != 0) {
            --n;
            ++b;
        }
        n = n / 2;
        int half = n;
        generate(b, next(b, half), [&]() {return n--;});
        generate(next(b, half), res.end(), [&](){return --n;});
        // iota(b, next(b, n), 1);
        // iota(next(b,n), res.end(), -n);
        return res;
    }
};

// 1309. Decrypt String from Alphabet to Integer Mapping
class Solution {
public:
    string freqAlphabets(string s) {
        string res;
        int size = s.size();
        for (int i = 0; i < size;) {
            auto j = i + 2;
            if (j >= size ||  s[j] != '#') {
                res += 'a' + s[i] - '0' - 1;
                ++i;
            } else {
                res += stoi(s.substr(i, 2)) + 'a' - 1;
                i = j + 1;
            }
        }
        return res;
    }
};

// 1313. Decompress Run-Length Encoded List
class Solution {
public:
    vector<int> decompressRLElist(vector<int>& nums) {
        int size = nums.size();
        vector<int> res;
        for (int i = 0; i < size; i += 2) {
            int n = nums[i];
            int val = nums[i+1];
            while (n-- > 0) res.push_back(val);
        }
        return res;
    }
};

// 1299. Replace Elements with Greatest Element on Right Side
class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int size = arr.size();
        int m = arr[size-1];
        arr[size-1] = -1;
        for (int j = size - 2; j >= 0; --j) {
            int t = arr[j];
            arr[j] = m;
            m = max(t, m);
        }
        return arr;
    }
};

// 1295. Find Numbers with Even Number of Digits
class Solution {
public:
    int findNumbers(vector<int>& nums) {
        return count_if(
            nums.begin(),
            nums.end(),
            [](const int& n) { return to_string(n).size() % 2 == 0;}
        );
    }
};

// 1290. Convert Binary Number in a Linked List to Integer
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int x = 0;
        while (head) {
            x <<= 1;
            x += head->val;
            head = head->next;
        }
        return x;
    }
};