class Solution {
public:
//滑动窗口
//window里面出现pcnt里面没有的，则窗口左指针向右移动，窗口内不能出现needs中没有的。
//保证窗口内都是pcnt中的数据，一旦窗口大小等于p.size()则出现一条满足的结果
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> pcnt;
        unordered_map<char, int> window; //窗口
        for(auto c:p) pcnt[c]++;
        vector<int> res;
        int left = 0, right = 0; //定义滑动窗口的两端
        while(right < s.size()){ // 右窗口开始不断向右移动
            int curR = s[right];
            window[curR]++; // right当前访问到的字符curR个数+1
            //curR可能在pcnt中没有出现过,或出现的次数超出了，此时需要移动left窗口
            //例如没有出现过的字符，则要使left移动right，此时可以删掉window中刚刚新增的字符
            while(window[curR] > pcnt[curR]) { 
                char curL = s[left];
                left++;
                window[curL]--;
            }

            if(right-left+1 == p.size()) res.push_back(left);

            right++;
         }
         return res;
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return false;
        int sum = 0;
        for(auto x:nums) sum += x;
        if(sum%2) return false;
        int maxNum = *max_element(nums.begin(), nums.end());
        int target = sum/2;
        if(maxNum > target) return false;
        // f[i][j] 表示用0～i个数字能否凑成j。
        vector<vector<bool>> f(n, vector<bool>(target+1, 0));
        for(int i=0; i<n; i++) f[i][0] = true;
        f[0][nums[0]] = true;
        for(int i=1; i<n; i++){
            for(int j=1; j<=target; j++){
                f[i][j] = f[i-1][j];
                if(j>=nums[i]) {
                    f[i][j] = f[i-1][j] | f[i-1][j-nums[i]];
                }
            }
        }
        return f[n-1][target];
    }
};


class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return false;
        int sum = 0;
        for(auto x:nums) sum += x;
        if(sum%2) return false;
        int maxNum = *max_element(nums.begin(), nums.end());
        int target = sum/2;
        if(maxNum > target) return false;
        // f[i][j] 表示用0～i个数字能否凑成j。
        vector<bool> f(target+1, 0);
        f[0] = true;
        for(int i=1; i<n; i++){
            for(int j=target; j>=nums[i]; j--){
                f[j] = f[j] | f[j-nums[i]];
            }
        }
        return f[target];
    }
};

class Solution {
public:
    string decodeString(string s) {
        stack<int> nums;
        stack<string> strs;

        int num = 0;
        string cur;
        for(int i=0; i<s.size(); i++){
            if(s[i] == '['){
                nums.push(num);
                strs.push(cur);
                num = 0;
                cur = "";
            } else if(s[i] == ']') {
                string tmp = cur;

                int t = nums.top();
                nums.pop();
                cur = strs.top();
                strs.pop();
                while(t--) cur += tmp;
            } else if(isdigit(s[i])){
                num = num * 10 + s[i] - '0' ; 
            } else {
                cur += s[i];
            }
        }
        return cur;
    }
};

class Solution {
public:
//nlog(k)使用哈希表统计每个数字出现的个数，然后维护一个大小为k的小顶堆即可。
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int,int>>> q;
        unordered_map<int, int> hash;
        for(int x :nums) hash[x]++; //每个num和其出现次数
        int i = 0;
        for(auto &it:hash){
            if(i < k) {
                i++;
                q.push(make_pair(it.second, it.first));
            } else {
                if(q.top().first < it.second) {
                    q.pop();
                    q.push(make_pair(it.second, it.first));
                }
            }
        }
        vector<int> res(k);
        for(int i=0; i<k; i++){
            res[i] = q.top().second;
            q.pop();
        }
        return res;
    }
};


class Solution {
public:
//O(n)首先用哈希表统计出所有数出现的次数。由于所有数出现的次数都在 1 到 n之间，所以我们可以用计数排序的思想，
//统计出次数最多的前 k 个元素的下界。然后将所有出现次数大于等于下界的数输出。
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> hash;
        for(auto x : nums) hash[x]++; //每个字出现多少次
        vector<int> s(n+1,0); //每个次数，有多少个字
        for(auto &x : hash) s[x.second]++;

        int t = 0, i = n; //i为出现次数的下界
        while(t < k) {
            t += s[i];
            i--;
        }

        vector<int> res;
        for(auto &x : hash)
            if(x.second > i) res.push_back(x.first);

        return res;
    }
};

class UnionFind {
public:
    vector<int> p;
    UnionFind(int num){
        for(int i=0; i < num; i++) p.push_back(i);
    }

    int find(int x){
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    bool Union(int a, int b){
        int fa = find(a), fb = find(b);
        bool res = fa==fb;
        p[fa] = fb;
        return res;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        UnionFind UF(N+1);
        vector<int> res(2, 0);
        for(int i=0; i < N; i++){
            int u = edges[i][0], v = edges[i][1];
            if(UF.Union(u, v)) {
                res = {u, v};
            }
        }
        return res;
    }
};

//排序nlog(n)，按照左右比较原数组和新数组。不同的区间就是需要调整的区间
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> temp;
        temp.assign(nums.begin(), nums.end());
        sort(temp.begin(), temp.end());
        int left = 0 , right = n - 1;
        while(left < n && nums[left]==temp[left]) left ++;
        while(right>=left && nums[right]==temp[right]) right --;
        return right - left + 1;
    }

class Solution {
public:
// 方法2.O(n)时间。主要思路遍历4遍。找左右边界点。
//整体思路和题解1其实是类似的，找到两段已经排好序的长度。我们先使用一遍扫描找到左边保持升序的最后一个点的位置left,
//和从右向左看保持降序的最后一个点的位置right。如果已经这时候left == right说明已经排好序了，无需调整。
//接下来我们从left + 1的位置向右扫描，如果遇到有比nums[left]小的元素，说明最起码left不在正确位置上，那么left —。
//同样的，我们从right - 1的位置向左扫描，如果遇到有比nums[right]大的元素，说明最起码nums[right]不在正确的位置上，right ++。
//最后，left和right之间的元素就是需要重新排序的元素，长度为right - left - 1。
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l+1 < n && nums[l+1] >= nums[l]) l++;
        if(l == n-1) return 0;
        while(r-1 >= 0 && nums[r]>= nums[r-1]) r--;

        for(int i = l+1; i<n; i++ )
            while(l>=0 && nums[i] < nums[l])
                l--;

        for(int i=r-1; i >=0 ; i--)
            while(r<n && nums[r]<nums[i])
                r++;
        return r - l - 1;
    }
};

class Solution {
public:
//令f[i]表示 i 的二进制表示中1的个数。 则f[i]可以由f[i/2]转移过来，
//i 的二进制表示和 ⌊i/2⌋的二进制表示除了最后一位都一样， 所以f[i] = f[i/2] + (i&1);
    vector<int> countBits(int num) {
        vector<int> f(num + 1, 0);
        for (int i = 1; i <= num; i ++ )
            f[i] = f[i >> 1] + (i & 1);
        return f;
    }
};

class Solution {
public:
//f[i][0]表示已经偷完以 i 为根的子树，且不在 i 行窃的最大收益；
//f[i][1]表示已经偷完以 i 为根的子树，且在 i 行窃的最大收益；
//状态转移
//f[i][1]：因为在 i行窃，所以在 i 的子节点不能行窃，只能从f[i->left][0]和f[i->right][0]转移；
//f[i][0]:因为不在 i 行窃，所以对 i的子节点没有限制，直接用左右子节点的最大收益转移即可；
    unordered_map<TreeNode*,unordered_map<int,int>> f;
    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root][0], f[root][1]);
    }

    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->left);
        dfs(root->right);
        f[root][1] = root->val + f[root->left][0] + f[root->right][0];
        f[root][0] = max(f[root->left][0],f[root->left][1])+max(f[root->right][0],f[root->right][1]);
    }
};

class Solution {
public:
// 完全背包问题。
// 相当于有 n 种物品，每种物品的体积是硬币面值，价值是1。问装满背包最少需要多少价值的物品？
// 状态表示： f[j] 表示凑出 j价值的钱，最少需要多少个硬币。
// 第一层循环枚举不同硬币，第二层循环从小到大枚举所有价值（由于每种硬币有无限多个，所以要从小到大枚举），
// 然后用第 i 种硬币更新 f[j] = min(f[j], f[j - coins[i]] + 1)。
    int coinChange(vector<int>& coins, int m) {
        vector<int> f(m + 1, 1e8);
        f[0] = 0;
        for (auto v: coins)
            for (int j = v; j <= m; j ++ )
                f[j] = min(f[j], f[j - v] + 1);
        if (f[m] == 1e8) return -1;
        return f[m];
    }
};


class Solution {
public:
    vector<int> memo;
    // dfs凑出target额度需要的最小几个币
    int dfs(vector<int>& coins, int target) {
        if (target < 0) return -1;
        if (memo[target] != INT_MAX) return memo[target];

        for (int i = 0; i < coins.size(); ++i) {
            int t = dfs(coins, target - coins[i]);
            if (t >= 0) memo[target] = min(memo[target], t + 1);
        }

        if (memo[target] == INT_MAX) memo[target] = -1;
        return memo[target];
    }

    int coinChange(vector<int>& coins, int amount) {
        if (coins.empty()) return -1;
        memo = vector<int>(amount + 1, INT_MAX);
        memo[0] = 0; // 凑出0元，只要0个币

        return dfs(coins, amount);
    }
};

动态规划解法
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n); // f[i]为以i结尾最长序列长度
        f[0] = 1;
        int res = 1;
        for(int i = 1; i<n; i++) {
            f[i] = 1;
            for(int j = 0; j<i; j++) {  
                if(nums[i] > nums[j]){
                    f[i] = max(f[i], f[j]+1);
                    res = max(res, f[i]);
                }
            }
        }
        return res;
    }
};

O(nlog(n))
class Solution {
public:
// 长度为i的最长子序列最后一个元素是stk[i],
// 枚举找到第一个不小于nums[i]的位置，替换掉，这样不妨碍当前stk[i]计算最长序列，也不影响后续增长序列
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> stk; //长度为i的最长子序列最后一个元素是stk[i],
        stk.push_back(nums[0]);
        for(int i = 1; i<n; i++) {
            if(nums[i] > stk.back()) stk.push_back(nums[i]);
            else {
                auto x = lower_bound(stk.begin(), stk.end(), nums[i]);
                *x = nums[i];
            }
        }
        return stk.size();
    }
};