/*
情况一：两个结点分别位于公共祖先的两个左右子树
情况二：一个结点是另一个结点的祖先

每个点最多被遍历一次，复杂度O(n)
*/

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 遍历到叶子结点也没找到，返回空
        if (!root) return NULL;

        // 递归查找p或q结点 

        // 遇到p或q结点，不再递归直接返回
        // 如果是情况一，会在其他子树找到另一个结点，返回该结点
        // 如果是情况二，祖先结点会先被递归到，另一个结点不会被找到
        // 返回该结点即返回最近公共祖先
        if (root == p || root == q) return root;

        // left返回左子树内目标结点/最近公共祖先
        auto left = lowestCommonAncestor(root->left, p, q);
        // right返回右子树内目标结点/最近公共祖先
        auto right = lowestCommonAncestor(root->right, p, q);

        // 回溯时根据结点查找情况返回结点
        // 根据分析，回溯到最后一定会返回最近公共祖先

        // 在树中找到两个，返回最近公共祖先
        // 第一次找到两个的根结点，就是最近公共祖先
        // 该if只会被执行一次
        // 只有情况一满足条件
        if (left && right) return root;
        // 找到一个，返回结点
        // 情况一：找到某个子树上唯一一个结点，或已经找到最近公共祖先
        // 情况二：返回两个结点间的的祖先结点
        if (left) return left;
        return right;
    }
};

/*
字符串处理
*/
class Solution {
public:
    int strToInt(string str) {
        int k = 0;
        while (k < str.size() && str[k] == ' ') k ++;
        long long num = 0;

        bool is_minus = false;
        if (str[k] == '+') k ++;
        else if (str[k] == '-') k ++, is_minus = true;

        while (k < str.size() && str[k] >= '0' && str[k] <= '9')
        {
            num = num * 10 + str[k] - '0';
            k ++;
        }

        if (is_minus) num *= -1;

        if (num > INT_MAX) num = INT_MAX;
        if (num < INT_MIN) num = INT_MIN;

        return (int)num;
    }
};

/*
动态规划

分成两个部分left和right
left[i] = A[0]*A[1]*…*A[i-1], left[i] = A[i-1]*left[i-1]
right[i] = A[i+1]*A[i+2]*…*A[n-1]，right[i] = A[i+1]*right[i+1]

最后结果B[i] = left[i]*right[i]

需要遍历一遍数组，复杂度O(n)

实现
只能开一个数组，可以用变量动态存储连乘结果
左侧从左向右遍历做乘法，左侧从右向左遍历做乘法
*/

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        if (A.empty()) return vector<int>();

        int n = A.size();
        vector<int> B(n);

        for (int i = 0, p = 1; i < n; i ++)
        {
            B[i] = p;
            p *= A[i];
        }

        // 倒序循环
        // i >= 0也可写成~i
        for (int i = n - 1, p = 1; i >= 0; i --)
        {
            // 左边连乘结果直接乘上右边连乘结果
            B[i] *= p;
            p *= A[i];
        }

        return B;
    }
};

/*
用位运算实现加法
相当于加法器

一位加法
a + b当前位结果是a ^ b，进位是a & b

多位加法
可以先不考虑进位做加法，再加上进位
1.不进位，哪些位是1：a ^ b
2.进位，哪些位要加1：a & b << 1
也即a ^ b + a & b << 1

注意：加上进位时，还是需要加法，且可能产生新的进位
因此要用循环这个过程，直到进位为0
*/

class Solution {
public:
    int add(int num1, int num2){
        while (num2)
        {
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1;
            num1 = sum;
            num2 = carry;
        }
        return num1;



    }
};

class Solution {
public:
    int getSum(int n) {
        int res = n;
        // 短路算法
        // if (A && B) A = false, B不执行
        // if (A || B) A = true,B不执行
        // 因此if (n > 0)可以改写成(n > 0) &&
        (n > 0) && (res += getSum(n -1));
        return res;
    }
};

/*
在第i天卖出，在1~i-1天最低价格买入，就可得到最大利润

暴力枚举：
一层枚举卖出的价格，一层枚举买入的价格，找到最低价格
复杂度O(n^2)

优化：
维护前i天的最低价格即可，可以省掉第二层循环
复杂度O(n)
*/

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if (nums.empty()) return 0;

        int res = 0;
        for (int i = 1, minv = nums[0]; i < nums.size(); i ++)
        {
            res = max(res, nums[i] - minv);
            minv = min(minv, nums[i]);
        }
        return res;
    }
};

链表模拟

/*
约瑟夫问题/枪毙问题
暴力模拟
因为要随机删除数据，用链表模拟比数组更快
据题意，要模拟环形链表
可以用数组模拟，也可以用STL内置的双向链表list模拟
n个数字需要O(n)的空间，要处理n-1次，每次要移动m步
复杂度O(nm)
*/

// list需要include
#include <list>
class Solution {
public:
    int lastRemaining(int n, int m){
        // 用STL中list模拟环形链表
        list<int> nums;
        for (int i = 0; i < n; ++i) nums.push_back(i);
        auto it = nums.begin();
        int k = m;
        // 当链表内元素超过两个
        while (nums.size() > 1){
            // 从begin开始，只要再走m - 1次即可
            while (-- k){
                it ++;
                // 迭代器移到开头实现模拟环形列表
                if (it == nums.end()) it = nums.begin();
            }
            // 删除第m个元素，同时迭代器指向下一位
            // remove删值，erase删迭代器
            it = nums.erase(it);
            if (it == nums.end()) it = nums.begin();
            k = m;
        }
        return nums.front();
    }
};

递推

/*
总结相邻两项之间的关系

f(n, m)表示n个人删除第m个人，剩下的人
每次删除一个人之后，重新编号，剩下的人变成f(n - 1, m)
将新编号再转换成旧编号，就能求解出答案

新旧编号对应关系：旧 = (新 + m) % n

也即f(n, m) = (f(n - 1, m) + m) % n

边界：剩下一个，编号为0，f(1, m) = 0

计算n-1次，每次O(1)，复杂度O(n)

可以用递归或者递推（循环）实现
*/

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

/*
排序
1.删除0
2.判断有无重复
3.判断剩下数最大差值<=4
*/

class Solution {
public:
    bool isContinuous( vector<int> nums ) {
        if (nums.empty()) return false;

        sort(nums.begin(), nums.end());
        int k = 0;
        // 删0，移指针即可
        // nums[k]是非0最左元素，也即最小元素
        while (!nums[k]) k ++;
        // 判重，判断相邻元素是否相等即可
        for (int i = k + 1; i < nums.size(); i ++)
            if (nums[i] == nums[i - 1])
                return false;
        // 判差
        return nums.back() - nums[k] <= 4;
    }
};

DFS暴搜

和记忆化搜索类似

状态含义：dfs(n, s)，投了n次，总和是s的方案数
搜索顺序：第n次投的数是i(1~6)，所有方案数只要将dfs(n-1,s-i)累加
边界：
当总和为负数，方案数为0
if (sum < 0) return 0;
当投了0次，总和为0，算一种情况
if (n == 0) return !sum;

会超时，因为枚举了所有方案
n是骰子数
最简单的dfs(n, n)，也要枚举n^2个状态，5n个数据，复杂度是O(n^3)
问题是因为，每次dfs都要从头开始算，已经计算过的中间过程没有保存下来

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<int> res;
        for (int i = n; i <= n * 6; i ++) res.push_back(dfs(n, i));
        return res;
    }

    int dfs(int n, int sum)
    {
        if (sum < 0) return 0;
        if (n == 0) return !sum;

        int res = 0;
        for (int i = 1; i <= 6; i ++)
            res += dfs(n - 1, sum - i);
        return res;
    }
};

线性DP

状态表示：f[i, j]前i次，总和是j的方案数
状态计算：
根据最后一次投的点数k分成6种情况
f[i, j] += f[i - 1][j - k]
边界情况：投0次，总和为0，唯一一种情况,，f[0][0] = 1

将所有情况都保存下来，每个情况只用计算一次复杂度O(n^2)

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<vector<int>> f(n + 1, vector<int>(n * 6 + 1));
        f[0][0] = 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= i * 6; j ++)
                // 这里用min(j, 6)代替6
                // 意思是当前点数k和不能超过总和j
                // 一方面是优化，减少了计算次数
                // 另一方面是避免出现负数，使状态矩阵越界
                for (int k = 1; k <= min(j, 6); k ++)
                    f[i][j] += f[i - 1][j - k];

        vector<int> res;
        for (int i = n; i <= n * 6; i ++) res.push_back(f[n][i]);
        return res;
    }
};

DFS暴搜

和记忆化搜索类似

状态含义：dfs(n, s)，投了n次，总和是s的方案数
搜索顺序：第n次投的数是i(1~6)，所有方案数只要将dfs(n-1,s-i)累加
边界：
当总和为负数，方案数为0
if (sum < 0) return 0;
当投了0次，总和为0，算一种合法情况，否则不合法
if (n == 0) return !sum;

会超时，因为枚举了所有方案
n是骰子数
最简单的dfs(n, n)，也要枚举n^2个状态，5n个数据，复杂度是O(n^3)
问题是因为，每次dfs都要从头开始算，已经计算过的中间过程没有保存下来

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<int> res;
        for (int i = n; i <= n * 6; i ++) res.push_back(dfs(n, i));
        return res;
    }

    int dfs(int n, int sum)
    {
        if (sum < 0) return 0;
        if (n == 0) return !sum;

        int res = 0;
        // 这里可以优化一下，i <= min(sum, 6)
        for (int i = 1; i <= 6; i ++)
            res += dfs(n - 1, sum - i);
        return res;
    }
};

线性DP

状态表示：f[i, j]前i次，总和是j的方案数
状态计算：
根据最后一次投的点数分成6种情况
f[i, j] += f[i - 1][j - k]
边界情况：投0次，总和为0，唯一一种情况,，f[0][0] = 1

将所有情况都保存下来，每个情况只用计算一次
复杂度O(n^2)

题解用滚动数组将二维DP压缩为一维DP：
https://www.acwing.com/solution/content/852/

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<vector<int>> f(n + 1, vector<int>(n * 6 + 1));
        f[0][0] = 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= i * 6; j ++)
                // 这里用min(j, 6)代替6
                // 意思是当前点数k和不能超过总和j
                // 一方面是优化，减少了计算次数
                // 另一方面是避免出现负数，使状态矩阵越界
                for (int k = 1; k <= min(j, 6); k ++)
                    f[i][j] += f[i - 1][j - k];

        vector<int> res;
        for (int i = n; i <= n * 6; i ++) res.push_back(f[n][i]);
        return res;
    }
};