class MaxQueue {
public:
    queue<int> que;         // 保存队列中所有的数子
    deque<int> maxque;      // 保存队列中最大的数字(两端操作为O(1))
    MaxQueue() {
    }

    int max_value() {
        return maxque.size() ? maxque.front() : -1;
    }

    void push_back(int value) {
        que.push(value);

        // 维护 maxque 为递减序列，每次可以输出当前队列中最大的数
        while(!maxque.empty() && maxque.back() < value)
            maxque.pop_back();

        maxque.push_back(value);
    }

    int pop_front() {
        if(que.empty())
            return -1;

        int result = que.front();
        que.pop();
        if(result == maxque.front())
            maxque.pop_front();

        return result;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n == 1) return 0;

        return (lastRemaining(n - 1, m) + m) % n;
    }
};

// 动态规划
class Solution {
public:
    vector<double> dicesProbability(int n) {
        // 保存概率结果
        vector<double> result;

        // 判断边界条件
        if(n == 0)  return result;

        // 计算所有可能出现的情况
        double sum = pow(6, n);

        // 定义状态(dp[n][s]: 当有 n 个骰子的时候，和为 s 的情况的个数)
        vector<vector<int>> dp(n + 1, vector<int>(6 * n + 1, 0));

        // 状态初始化(dp[1][1] = 1, dp[1][2] = 1, ...)
        for(int i = 1; i <= 6; ++i)
            dp[1][i] = 1;

        // 状态转移(当有 2 个以上骰子的时候)
        // 枚举骰子的个数
        for(int i = 2; i <= n; ++i)
        {
            // 枚举各个骰子的总和
            for(int j = i; j <= 6 * n; ++j)     
            {
                // 枚举当前骰子所出现的数字
                for(int k = 1; k <= 6; ++k)
                {
                    if(j - k < 0) break;
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }

        // 计算和为 i 时所出现的情况占总情况的概率
        for(int i = n; i <= 6 * n; ++i)
            result.push_back(dp[n][i] * 1.0 / sum);

        return result;
    }
};

// 二分
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] != mid) r = mid;
            else l = mid + 1;
        }

        if(l == nums[l]) l++;

        return l;
    }
};

// 间隔法
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 第一个元素不是 0 的情况
        if(nums[0]) return 0;

        // 一般情况
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] - nums[i - 1] > 1)
            {
                return nums[i] - 1;
            }
        }

        return nums.size();
    }
};

// 三指针方法：2, 3, 5
class Solution {
public:
    int nthUglyNumber(int n) {
        // 判断边界条件
        if(n == 0)  return 0;

        // 保存所有结果集
        vector<int> result;
        result.push_back(1);

        // 三个指针从头开始遍历
        int i = 0, j = 0, k = 0;
        int index = n;
        while(n--)
        {
            int num = min(result[i] * 2, min(result[j] * 3, result[k] * 5));
            if(num == result[i] * 2) i++;
            if(num == result[j] * 3) j++;
            if(num == result[k] * 5) k++;

            result.push_back(num);
        }

        // 返回数组中最后一个元素
        return result[index - 1];
    }
};

// 哈希表法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 哈希表统计次数
        unordered_map<int, int> hash;
        for(auto& e : nums)
            hash[e]++;

        // 遍历哈希表
        int len = nums.size() / 2;
        for(auto& e : hash)
        {
            if(e.second > len)
                return e.first;
        }

        return 0;
    }
};

// 排序法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 对数组进行排序
        sort(nums.begin(), nums.end());

        // 返回最中间的数
        return nums[nums.size() / 2];
    }
};

// 摩尔投票法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 遍历数组中的元素
        int count = 0;
        int result = 0;
        for(auto& e : nums)
        {
            if(count <= 0)
                result = e;

            if(result == e)
                count++;
            else
                count--;
        }

        return result;
    }
};

// 暴力搜索
class Solution {
public:
    vector<string> result;
    string str;
    vector<int> flag;  // 记录已经使用过的字符
    vector<string> permutation(string s) {
        // 判断边界条件
        if(s == "")
            return result;

        // 是相同的元素在一起
        sort(s.begin(), s.end());

        // 初始化标记数组
        flag.resize(s.size(), 1);

        // 暴力搜索
        dfs(s, 0, s.size());

        // 返回所有结果集
        return result;
    }

    void dfs(string s, int start, int len)
    {
        // 当前搜索的长度已经满足要求
        if(start == len)
        {
            result.push_back(str);
            return;
        }

        for(int i = 0; i < len; ++i)
        {
            // 前一个相同的元素没有使用时，当前元素不能先使用
            // 等下一轮递归进行的时候从头遍历开始进行使用
            if(i && s[i] == s[i - 1] && flag[i - 1] == 1)
            {
                continue;
            }

            if(flag[i] == 1)
            {
                str += s[i];
                flag[i] = 0;
                dfs(s, start + 1, len);

                // 恢复原有状态
                flag[i] = 1;
                str.pop_back();
            }
        }

        return ;
    }
};

LeetCode 剑指offer 36

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
// list + 中序遍历
class Solution {
public:
    list<Node*> nodelist;       // 保存树中的每一个节点
    Node* treeToDoublyList(Node* root) {
        // 判断边界条件
        if(root == NULL)
            return root;

        // 递归中序遍历
        dfs(root);

        // 遍历 list 将所有节点的指针进行更改
        Node* head = nodelist.front();
        auto begin = nodelist.begin();
        while((*begin)->val != nodelist.back()->val)  // 走到最后一个节点停止
        {
            // 更改指针指向
            auto cur = *begin;
            auto next = *(++begin);
            cur->right = next;
            next->left = cur;
        }
        head->left = nodelist.back();
        nodelist.back()->right = head;

        // 返回头节点
        return head;
    }

    void dfs(Node* root)
    {
        if(root == NULL)
            return;

        dfs(root->left);
        nodelist.push_back(root);
        dfs(root->right);
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
// 中序遍历的过程中更改指针的链接情况
class Solution {
public:
    Node* head = NULL;      // 保存双向链表的头结点
    Node* last = NULL;      // 保存遍历过程中的上一个结点
    Node* treeToDoublyList(Node* root) {
        // 判断边界条件
        if(root == NULL)
            return NULL;

        // 中序遍历
        dfs(root);

        // 链接头尾节点
        head->left = last;
        last->right = head;

        // 返回头节点
        return head;
    }

    void dfs(Node* root)
    {
        // 当前为空节点
        if(root == NULL)
            return;

        // 递归左子树
        dfs(root->left);

        // 当前节点的左子树为空，则当前节点为 头节点
        if(head == NULL && root->left == NULL)
        {
            head = root;
        }

        // 更改指针链接情况
        root->left = last;
        if(last != NULL)
            last->right = root;
        last = root;

        // 递归右子树
        dfs(root->right);
    }
};

/**
 * 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 curc = 0, maxc = 0, last = 0;
    vector<int> result;
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return result;
    }

    // 中序遍历
    void dfs(TreeNode* root)
    {
        if(root == NULL)
            return ;

        // 递归左子树
        dfs(root->left);

        // 如果当前数是第一个数或者当前数与上一个数相等
        if(!curc || root->val == last) {
            curc++;
            last = root->val;
        } else {
            last = root->val;
            curc = 1;
        }

        // 如果当前这个数是出现最多的，则为众数
        if(curc > maxc) {
            result = {root->val};
            maxc = curc;
        } else if(curc == maxc) {
            result.push_back(root->val);
        }

        // 递归右子树
        dfs(root->right);
    }
};

// 冒泡排序
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 冒泡排序
        for(int i = 0; i < k; ++i)
        {
            for(int j = 1; j < nums.size(); ++j)
            {
                if(nums[j - 1] > nums[j])
                    swap(nums[j - 1], nums[j]);
            }
        }

        // 返回第 k 大的数字
        return *(nums.rbegin() + k - 1);
    }
};

// 堆排序
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 初始化(默认大顶堆)
        priority_queue<int> heap(nums.begin(), nums.end());

        // 寻找第 k 大的元素
        k--;
        while(k--)
        {
            heap.pop();
        }

        return heap.top();
    }
};

// 快速选择：“模板题”
// 随机选择一个数，大的放左边，小的放右边。
class Solution {
public:
    int quick_select(vector<int>& nums, int l, int r, int k)
    {
        // 区间只有一个数的时候，直接返回
        if(l == r)
            return nums[l];

        // 随机选择一个数
        int num = nums[(l + r) >> 1];
        int left = l - 1, right = r + 1;
        while(left < right)
        {
            // 大的放左边，小的放右边
            do left++; while(nums[left] > num);
            do right--; while(nums[right] < num);

            if(left < right)
                swap(nums[left], nums[right]);
        }

        // 左边数组的个数大于 k 
        if(right >= k)
            return quick_select(nums, l, right, k);
        else 
            return quick_select(nums, right + 1, r, k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 快速选择(从 0 开始计数)
        return quick_select(nums, 0, nums.size() - 1, k - 1);
    }
};