Leetcode summary of 20200301-20200308

// 1185. Day of the Week
// https://leetcode.com/problems/day-of-the-week/
class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        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}
        };
        function<bool(int)> is_leap_year = [](int y) {
            if (y % 100 != 0) return y % 4 == 0;
            else return y % 400 == 0;
        };
        int days = 0;
        vector<int> y_d{365, 366};
        for (int i = 1971; i < year; ++i) {
            days += y_d[is_leap_year(i)];
        }
        auto& m = cols[is_leap_year(year)];
        days += accumulate(begin(m), next(m.begin(), month-1), 0) + day;
        days %= 7;
        vector<string> weeks = {"Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday"};
        return weeks[days == 0? 6 : days-1];
    }
};

// 1154. Day of the Year
// https://leetcode.com/problems/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];

    }
};

// 1360. Number of Days Between Two Dates
// https://leetcode.com/problems/number-of-days-between-two-dates/
class Solution {
public:
    int daysBetweenDates(string date1, string date2) {
        vector<vector<int>> month_days = {
            {31, 28, 31, 30,31,30,31,31,30,31,30,31},
            {31, 29, 31, 30,31,30,31,31,30,31,30,31},
        };
        int leap_days[2] = {365, 366};
        int y1, m1, d1;
        int y2, m2, d2;
        function<void(int&, int&, int&, string&)> parse = [](int&y ,int& m, int& d, string& s) {
            y = stoi(s.substr(0, 4));
            m = stoi(s.substr(5, 2));
            d = stoi(s.substr(8, 2));
        };
        function<bool(int)> is_leap = [](int y) {
            if (y % 100 == 0) return y % 400 == 0;
            return y % 4 == 0;
        };
        parse(y1, m1, d1, date1);
        parse(y2, m2, d2, date2);
        int days = 0;
        int s1 = y1, s2 = y2;
        if (s1 > s2) swap(s1, s2);
        for (int i = s1; i < s2; ++i) {
            days += leap_days[is_leap(i)];
        }
        auto& m_d1 = month_days[is_leap(y1)];
        int days1 = d1 + accumulate(begin(m_d1), next(m_d1.begin(), m1-1), 0);
        auto& m_d2 = month_days[is_leap(y2)];
        int days2 = d2 + accumulate(begin(m_d2), next(m_d2.begin(), m2-1), 0);
        if (y1 < y2) {
            return days + days2 - days1;
        } else if (y1 > y2) {
            return days + days1 - days2;
        } else {
            return abs(days1 - days2);
        }
    }
};

// 1370. Increasing Decreasing String
// https://leetcode.com/problems/increasing-decreasing-string/
class Solution {
public:
    string sortString(string s) {
        vector<int> x(26, 0);
        for_each(begin(s), end(s), [&](char c) { ++x[c-'a'];});
        string res;
        int size = s.size();
        while (res.size() < size) {
            for (int i = 0; i < 26; ++i) {
                if (x[i] != 0)  {
                    res += i + 'a';
                    --x[i];
                }
            }
            for (int i = 25; i >= 0; --i) {
                if (x[i] != 0)  {
                    res += i + 'a';
                    --x[i];
                }
            }
        }
        return res;
    }
};

// 1356. Sort Integers by The Number of 1 Bits
// https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/
class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        unordered_map<int, int> cached;
        function<int(int)> n_b = [&](int n) {
            if (cached.find(n) != cached.end()) return cached[n];
            int key = n;
            int cnt = 0;
            while (n != 0) { n &= (n-1); ++cnt;}
            cached[key] = cnt;
            return cnt;
        };
        function<bool(int, int)> cmp = [&](int l, int r) {
            auto ll = n_b(l);
            auto rr = n_b(r);
            return ll == rr ? l < r : ll < rr;
        };
        sort(begin(arr), end(arr), cmp);
        return arr;
    }
};

// 1372. Longest ZigZag Path in a Binary Tree
// https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int longestZigZag(TreeNode* root) {
        if (!root || (!root->left && !root->right)) return 0;
        int max_length = 0;
        function<int(TreeNode*, bool, int)> traverse = [&](TreeNode* node, bool d, int n)
        {
            // d: true, right
            // d: false, left
            if (!node) return n;
            n = n + 1;
            int x, y;
            if (d) {
                x = node->right ? traverse(node->right, !d, n) : n;
                y = node->left ? traverse(node->left, d, 0) : 0;
            } else {
                x = node->left ? traverse(node->left, !d, n) : n;
                y = node->right ? traverse(node->right, d, 0) : 0;
            }
            return max(x, y);
        };
        return max(traverse(root->left, true, 0), traverse(root->right, false, 0));
    }
};

// 1362. Closest Divisors
// https://leetcode.com/problems/closest-divisors/
class Solution {
public:
    vector<int> closestDivisors(int num) {
        int s = num + 2;
        int k = sqrt(s);
        for (; k >= 1; --k) {
            auto x = (num+1) % k;
            if (x == 0) return {k, (num+1)/k};
            if (x == (k-1)) return {k, (num+2)/k};
        }
        return {0, 0};
    }
    vector<int> closestDivisorsSlow(int num) {
        int a = num + 1;
        int b = num + 2;
        function<bool(int)> is_prime = [](int x) {
            if (x == 1) return false;
            if (x < 4) return true;
            if (x % 2 == 0 || x % 3 == 0) return false;
            int w = 2;
            int k = 5;
            while (k * k <= x) {
                 if (x % k == 0) return false;
                 k += w;
                 w = 6 - w;
            }
            return true;
        };
        function<pair<int,int>(int)> factor = [&](int n) {
            if (is_prime(n)) return make_pair(1, n);
            int r = (int)sqrt(n);
            while (n % r != 0) {
                ++r;
            }
            int d = n / r;
            if (d > r) swap(d, r);
            return make_pair(d, r);
        };
        auto p1 = factor(a);
        auto p2 = factor(b);
        if (p1.second - p1.first < p2.second - p2.first) {
            return {p1.first, p1.second};
        } else {
            return {p2.first, p2.second};
        }
    }
};

// 220. Contains Duplicate III
// https://leetcode.com/problems/contains-duplicate-iii/
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int size = nums.size();
        if (k == 0 || size < 2) return false;
        multiset<int> s;
        s.insert(nums[0]);
        // cout << "--------------" << endl;
        for (int i = 1; i < size; ++i) {
            auto l = s.lower_bound(nums[i]);
            decltype(l) r = prev(l);

            /*
            if (l != s.end()) cout << "*l = " << *l << endl;
            else cout << "*l is end()" << endl;
            cout <<"*prev(l) = " << *prev(l) << endl;
            */

            if (l != s.end() && (abs(*l - (long long)nums[i])) <= t) return true;
            if (r != s.end() && (abs(*prev(l) - (long long)nums[i])) <= t) return true;
            // cout << "X: " << nums[i]<< " "<< s.size() << endl;
            if (s.size() == k) {

                auto ite = s.find(nums[i-k]);
                // cout << "del: " << *ite << endl;
                s.erase(ite);
            }
            // cout << "Y: " << nums[i]<< " "<< s.size() << endl;
            s.insert(nums[i]);
        }
        return false;
    }
};

// 211. Add and Search Word - Data structure design
// https://leetcode.com/problems/add-and-search-word-data-structure-design/
class WordDictionary {
    struct Node {
        bool end;
        vector<Node*> output;
        Node(): output(26, nullptr), end(false) {}
    };
    vector<Node*> _heads;
public:
    /** Initialize your data structure here. */
    WordDictionary(): _heads(26, nullptr) {
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        vector<Node*>* starts = &_heads;
        int size = word.size();
        for (int i = 0; i < size; ++i) {
            char c = word[i];
            int index = c - 'a';
            if (!(*starts)[index]) {
                (*starts)[index] = new Node;
            }
            if (i == size-1) (*starts)[index]->end = true;
            starts = &((*starts)[index]->output);
        }
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        function<bool(int, vector<Node*>&)> sea = [&](int index, vector<Node*>& nodes) {
            if (word[index] != '.') {
                int pos = word[index] - 'a';
                if (nodes[pos] == nullptr) return false;
                else {
                    if (index == word.size() - 1) {
                        return nodes[pos]->end;
                    }
                    return sea(index+1, nodes[pos]->output);
                }
            } else {
                for (int i = 0; i < 26; ++i) {
                    if (nodes[i] != nullptr) {
                        if (index == word.size() - 1) {
                            if (nodes[i]->end) return true;
                        } else {
                            bool res = sea(index+1, nodes[i]->output);
                            if (res) return res;
                        }
                    }
                }
                return false;
            }
        };
        return sea(0, _heads);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

// 209. Minimum Size Subarray Sum
// https://leetcode.com/problems/minimum-size-subarray-sum/
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        // use prefix sum
        partial_sum(begin(nums), end(nums), begin(nums));
        int c = INT_MAX;
        int size = nums.size();
        int prev = 0;
        for (int i = 0; i < size; ++i) {
            int target = s + prev;
            auto it = lower_bound(begin(nums), end(nums), target);
            if (it == nums.end()) break;
            int dis = distance(nums.begin(), it) - i + 1;
            c = min(c, dis);
            prev = nums[i];
        }

        return c == INT_MAX ? 0 : c;
    }
    int minSubArrayLenFast(int s, vector<int>& nums) {
        int i = 0;
        int j = 0;
        int size = nums.size();
        int sum = 0;
        int c = INT_MAX;
        while (true) {
            while (j < size && sum < s) {
                sum += nums[j];
                ++j;
            }
            if (sum < s) break;
            int dis = j - i;
            if (dis < c) c = dis;
            sum -= nums[i];
            ++i;
        }
        return c == INT_MAX? 0 : c;
    }
};

// 208. Implement Trie (Prefix Tree)
// https://leetcode.com/problems/implement-trie-prefix-tree/
class Trie {
    struct TrieNode {
        bool end;
        vector<TrieNode*> out;
        TrieNode(): end(false), out(26, nullptr) {}
    };
    vector<TrieNode*> _heads;
public:
    /** Initialize your data structure here. */
    Trie():_heads(26, nullptr) {

    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        // cout << "Insert: " << word << endl;
        function<void(const string&, int, vector<TrieNode*>&)> insert_helper = [&](
            const string& word, int start, vector<TrieNode*>& heads
        ) {
            if (start >= word.size()) return;
            int index = word[start] - 'a';
            if (!heads[index]) heads[index] = new TrieNode;
            heads[index]->end = heads[index]->end || (start == word.size() - 1);
            // cout << "char: " << word[start] << ", heads[index]->end: " << heads[index]->end << endl;
            insert_helper(word, start+1, heads[index]->out);
        };
        insert_helper(word, 0, _heads);
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        // cout << "Search: " << word << endl;
        function<bool(const string&, int start, const vector<TrieNode*>&)> search_helper = [&](const string& word, int start, const vector<TrieNode*>& heads) {
            int size = word.size();
            int index = word[start] - 'a';
            if (!heads[index]) return false;
            if (size == start+1) {
                return heads[index] && heads[index]->end;
            } else {
                return search_helper(word, start+1, heads[index]->out);
            }
        };
        if (word.empty()) return true;
        return search_helper(word, 0, _heads);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        function<bool(const string&, int start, const vector<TrieNode*>&)> search_helper = [&](const string& word, int start, const vector<TrieNode*>& heads) {
            int size = word.size();
            int index = word[start] - 'a';
            if (!heads[index]) return false;
            if (size == start+1) {
                return heads[index] != nullptr;
            } else {
                return search_helper(word, start+1, heads[index]->out);
            }
        };
        if (prefix.empty()) return true;
        return search_helper(prefix, 0, _heads);
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

// 207. Course Schedule
// https://leetcode.com/problems/course-schedule/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> course; // id -> outputs
        vector<bool> deps(numCourses, false);
        for (vector<int>& dep: prerequisites) {
            course[dep[1]].push_back(dep[0]);
            deps[dep[0]] = true;
        }
        vector<bool> taken(numCourses, false);
        unordered_set<int> s;
        function<bool(int)> dfs = [&](int i) {
            if (taken[i]) return false;
            s.insert(i);
            taken[i] = true;
            for (int d : course[i]) {
                if(!dfs(d)) return false;
            }
            taken[i] = false;
            return true;
        };
        for (int i = 0; i < numCourses; ++i) {
            if (deps[i]) continue;
            if (!dfs(i)) return false;
        }
        return s.size() == numCourses;
    }
};

// 1365. How Many Numbers Are Smaller Than the Current Number
// https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> bkp(nums);
        sort(begin(bkp), end(bkp));
        vector<int> result;result.reserve(nums.size());
        for (int n : nums) {
            auto ite = lower_bound(begin(bkp), end(bkp), n);
            result.push_back(distance(bkp.begin(), ite));
        }
        return result;
    }
};

// 1367. Linked List in Binary Tree
// https://leetcode.com/problems/linked-list-in-binary-tree/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {

        bool k = false, lr = false;
        function<bool(ListNode*, TreeNode*, bool)> dfs = [&](
            ListNode* head, TreeNode* root, bool cont
        ) {
            if (!head) return true;
            if (!root) return false;
            if (cont) {
                if (head->val != root->val) return false;
                return dfs(head->next, root->left, true) || dfs(head->next, root->right, true);
            }
            if (head->val == root->val)
            k = dfs(head->next, root->left, true) || dfs(head->next, root->right, true);
        if (!k)
            return dfs(head, root->left, false) || dfs(head, root->right, false);
        return k;
        };
        return dfs(head, root, false);

    }
};

// 1366. Rank Teams by Votes
// https://leetcode.com/problems/rank-teams-by-votes/
class Solution {
    struct Vote {
        char c;
        array<int, 26> votes;
        Vote(): c('0') {}
        bool operator()(const Vote&l, const Vote& r) {
            if (l.c == '0') return false;
            if (r.c == '0') return true;
            for (int i = 0; i < 26; ++i) {
                if (l.votes[i] != r.votes[i])
                    return l.votes[i] > r.votes[i];
            }
            return l.c < r.c;
        }
    };
public:
    string rankTeams(vector<string>& votes) {
        int size = votes.size();
        if (size == 1 || votes[0].size() == 1) return votes[0];
        vector<Vote> v(26);
        int team_size = votes[0].size();
        for(string& vote: votes) {
            for (int i = 0; i < team_size; ++i) {
                char team = vote[i];
                int t_id = team - 'A';
                v[t_id].votes[i] += 1;
                v[t_id].c = team;
            }
        }
        sort(v.begin(), v.end(), Vote());
        string s;
        for (auto& vv: v) {
            if (vv.c == '0') break;
            s += vv.c;
        }
        return s;

    }
};