/*
 * @lc app=leetcode id=416 lang=cpp
 *
 * [416] Partition Equal Subset Sum
 *
 * https://leetcode.com/problems/partition-equal-subset-sum/description/
 *
 * algorithms
 * Medium (46.89%)
 * Likes:    12640
 * Dislikes: 260
 * Total Accepted:    1M
 * Total Submissions: 2.1M
 * Testcase Example:  '[1,5,11,5]'
 *
 * Given an integer array nums, return true if you can partition the array into
 * two subsets such that the sum of the elements in both subsets is equal or
 * false otherwise.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,5,11,5]
 * Output: true
 * Explanation: The array can be partitioned as [1, 5, 5] and [11].
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1,2,3,5]
 * Output: false
 * Explanation: The array cannot be partitioned into equal sum subsets.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 *
 *
 */

// @lc code=start
class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int n = nums.size();
        int subset_sum = sum / 2;
        vector<vector<bool>> dp(n + 1, vector<bool>(subset_sum + 1));
        dp[0][0] = true;

        for (int i = 1; i <= n; i++)
        {
            int cur = nums[i - 1];
            for(int j = 0; j <= subset_sum; j++) {
                if(j < cur) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] || (dp[i - 1][j - cur]);
            }
        }
        return dp[n][subset_sum];
    }
};
// @lc code=end

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int target = sum >> 1;
        vector<bool> dp(target + 1);
        dp[0] = true;

        for (int num : nums)
        {
            for (int i = target; i >= num; --i)
            {
                dp[i] = dp[i] || dp[i - num];
                if (dp[target])
                {
                    return dp[target];
                }
            }
        }
        return dp[target];
    }
};

class Solution {
public:
    int longestPalindrome(string s) {
        int mid = 0, res = 0;
        unordered_map<char, int> freq;
        for(auto& c : s) ++freq[c];
        for(auto& f : freq) {
            res += f.second;
            if(f.second % 2 == 1) {
                --res;
                mid = 1;
            }
        }
        return (mid == 1) ? ++res : res;
    }
};

class Solution {
public:
    // 用 map 儲存 a/b, b/c 和結果的關係
    // 以 graph 的題目來說，會有一點類似 adjacencyt list 的感覺
    // {
    //   {"a", {"b": 2.0}},
    //   {"b", {"a": 1/2.0}},
    //   {"b", {"c": 3.0}},
    //   {"c", {"b": 1/3.0}},
    // }
    unordered_map<string, unordered_map<string, double>> graph;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for (int i = 0; i < equations.size(); ++i) {
            string A = equations[i][0];
            string B = equations[i][1];
            graph[A][B] = values[i];
            graph[B][A] = 1.0 / values[i];
        }

        vector<double> res;

        for (auto q : queries) {
            // 如果沒在分母或分子的話，返回 -1.0
            if(!graph.count(q[0]) || !graph.count(q[1])) {
                res.push_back(-1.0);
                continue;
            }
            // 每次的 query，都要新的 seen hashset
            unordered_set<string> seen;
            res.push_back(dfs(q[0], q[1], seen));
        }
        return res;
    }
    double dfs(string up, string down, unordered_set<string>& seen) {
        // 如果在 graph 看到有對應的值，直接返回值是多少
        if (graph[up].count(down))
            return graph[up][down];

        // iterate graph 的分子
        for (auto a : graph[up]) {
            // 如果已經走訪過的，略過
            if (seen.count(a.first)) continue;

            // 將走訪的值插入到 set 裡
            seen.insert(a.first);

            // d = C / B
            double t = dfs(a.first, down, seen);
            // A / B = C / B * A / C
            if (t > 0.0) return t * a.second;
        }
        return -1.0;
    }
};

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        vector<int> freq(26);

        for(auto& c : magazine) ++freq[ c - 'a'];

        for(int i = 0; i < ransomNote.size(); i++)
        {
            int c = ransomNote[i] - 'a';
            if (--freq[c] < 0) return false;
        }
        return true;
    }
};

class RandomizedSet {
private:
    unordered_map<int, int> m;
    vector<int> nums;
public:
    RandomizedSet() {}

    bool insert(int val)
    {
        if(m.count(val)) return false;

        nums.push_back(val);

        m[val] = nums.size() - 1;

        return true;
    }

    bool remove(int val)
    {
        if (!m.count(val)) return false;

        int lastElement = nums.back();

        nums[m[val]] = lastElement;
        m[lastElement] = m[val];

        nums.pop_back();
        m.erase(val);
        return true;
    }

    int getRandom()
    {
        return nums[rand() % nums.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        if (nums1.size() > nums2.size()) return intersect(nums2, nums1);

        unordered_map<int, int> m;

        for (int num : nums1) ++m[num];
        int k = 0;
        for (int num : nums2)
        {
            if (m.count(num) && m[num] >= 1)
            {
                --m[num];
                nums1[k++] = num;
            }
        }
        return vector<int>{nums1.begin(), nums1.begin() + k};
    }
};

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        int i = 0, j = 0, k = 0;
        while (i < nums1.size() && j < nums2.size())
        {
            if (nums1[i] < nums2[j])
            {
                ++i;
            }
            else if (nums1[i] > nums2[j])
            {
                ++j;
            }
            else
            {
                nums1[k++] = nums1[i++];
                ++j;
            }

        }
        return vector<int>{nums1.begin(), nums1.begin() + k};
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        // base case
        // 如果 k == n，回傳原數列
        if(k == n) return nums;

        // {數字, 出現的頻率}
        unordered_map<int, int> freq;
        priority_queue<pair<int, int>> q;
        vector<int> res;

        // 算數字出現的頻率
        for(auto num : nums) ++freq[num];

        // 將出現頻率的推到 priority queue 排列
        // 預設是 max heap，由大排到小
        for(auto it : freq) {
            q.push({it.second, it.first});
        }

        for(int i = 0; i < k; i++) {
            // 將出現頻率前 k 的數字推到 res
            res.push_back(q.top().second); q.pop();
        }
        return res;
    }
};

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int size)
    {
        parent.resize(size);
        rank.resize(size, 1);
        for (int i = 0; i < size; ++i)
        {
            parent[i] = i;
        }
    }

    int find(int node)
    {
        if (parent[node] != node)
        {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }

    void unionNodes(int node1, int node2)
    {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) return;
        if (rank[root1] < rank[root2])
        {
            parent[root1] = root2;
        }
        else if (rank[root1] > rank[root2])
        {
            parent[root2] = root1;
        }
        else
        {
            parent[root2] = root1;
            rank[root1]++;
        }
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges)
    {
        UnionFind uf(n);

        for (const auto& edge : edges)
        {
            uf.unionNodes(edge[0], edge[1]);
        }

        int count = 0;

        for (int i = 0; i < n; ++i)
        {
            if (uf.find(i) == i)
            {
                ++count;
            }
        }
        return count;
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges)
    {
        int count = 0;
        vector<bool> seen(n);
        vector<vector<int>> graph(n);

        for (auto edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        for (int i = 0; i < n; ++i)
        {
            if (!seen[i])
            {
                ++count;
                dfs(graph, seen, i);
            }
        }
        return count;
    }
    void dfs(vector<vector<int>>& graph, vector<bool>& seen, int node)
    {
        if (seen[node]) return;

        seen[node] = true;
        for (int i = 0; i < graph[node].size(); ++i)
        {
            dfs(graph, seen, graph[node][i]);
        }
    }
};