1. 数组的连续子序列最大和

题目
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

方法一：分治法O（nlogn）

因为最大子序列和可能在三处出现，整个出现在数组左半部，或者整个出现在右半部，又或者跨越中间，占据左右两半部分。递归将左右子数组再分别分成两个数组，直到子数组中只含有一个元素，退出每层递归前，返回上面三种情况中的最大值。

#include<limits.h>
int Max3(int a,int b,int c)
{
    int Max = a;
    if(b > Max)
        Max = b;
    if(c > Max)
        Max = c;
    return Max;
}
int MaxSubSum2(int *arr,int left,int right)
{
    int MaxLeftSum,MaxRightSum;    //左右边的最大和
    int MaxLeftBorderSum,MaxRightBorderSum;    //含中间边界的左右部分最大和
    int LeftBorderSum,RightBorderSum;    //含中间边界的左右部分当前和
    int i,center;
    //递归到最后的基本情况
    if(left == right)
        //(X)if(arr[left]>0)
            return arr[left];
        //(X)else
          //(X)  return 0;
    //求含中间边界的左右部分的最大值
    center = (left + right)/2;
    MaxLeftBorderSum = INT_MIN;
    LeftBorderSum = 0;
    for(i=center;i>=left;i--)
    {
        LeftBorderSum += arr[i];
        if(LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    MaxRightBorderSum = INT_MIN;
    RightBorderSum = 0;
    for(i=center+1;i<=right;i++)
    {
        RightBorderSum += arr[i];
        if(RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }
    //递归求左右部分最大值
    MaxLeftSum = MaxSubSum2(arr,left,center);
    MaxRightSum = MaxSubSum2(arr,center+1,right);
    //返回三者中的最大值
    return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
}
/*
将分支策略实现的算法封装起来
*/
int MaxSubSum2_1(int *arr,int len)
{
    return MaxSubSum2(arr,0,len-1);
}

方法二：神奇的方法O(n)

连续子序列最大和的特征：若A[i]+A[j]< 0则i,j必不在最大连续子序列的序列中。

#include<limits.h>
class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
    int i,len;  
    int MaxSum = INT_MIN;  //防止数组全是小于零的数
    int ThisSum= 0;  
    len = nums.size(); 
    for(i=0;i<len;i++)  
    {  
        ThisSum+= nums[i];  
        if(ThisSum > MaxSum)    
            MaxSum = ThisSum;  
        if(ThisSum< 0)  
            ThisSum= 0;  
    }  
    return MaxSum;  
    }
};

2. 二叉树中的最大“路径”和

题目：
路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其最大路径和

示例：

递归&分治法 - 图1
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

class Solution {
private:
    int maxSum = INT_MIN;
public:
    int maxGain(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node->val + leftGain + rightGain;
        // 更新答案
        maxSum = max(maxSum, priceNewpath);
        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

3. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = “3[a]2[bc]”
输出：”aaabcbc”

示例 2：
输入：s = “3[a2[c]]”
输出：”accaccacc”

class Solution {
public:
    string src; 
    size_t ptr;
    int getDigits() {
        int ret = 0;
        while (ptr < src.size() && isdigit(src[ptr])) {
            ret = ret * 10 + src[ptr++] - '0';
        }
        return ret;
    }
    string getString() {
        if (ptr == src.size() || src[ptr] == ']') {
            // String -> EPS
            return "";
        }
        char cur = src[ptr]; int repTime = 1;
        string ret;
        if (isdigit(cur)) {
            // String -> Digits [ String ] String
            // 解析 Digits
            repTime = getDigits(); 
            // 过滤左括号
            ++ptr;
            // 解析 String
            string str = getString(); 
            // 过滤右括号
            ++ptr;
            // 构造字符串
            while (repTime--) ret += str; 
        } else if (isalpha(cur)) {
            // String -> Char String
            // 解析 Char
            ret = string(1, src[ptr++]);
        }
        return ret + getString();
    }
    string decodeString(string s) {
        src = s;
        ptr = 0;
        return getString();
    }
};

4. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
递归&分治法 - 图2
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

官解：
class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// mysolution
class Solution {
private:
    TreeNode* ancestor=NULL;
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        bool ifp=false,ifq=false;
        recursion(root,ifp,ifq,p,q);
        return ancestor;
    }
    bool recursion(TreeNode *root, bool &ifp,bool &ifq,TreeNode* p, TreeNode* q){
        if(!root) return false;
        bool find1,find2;
        bool bp1 =false,bq1 =false;
        find1 = recursion(root->left,bp1,bq1,p,q);
        if(find1) return true;
        bool bp2 =false,bq2 =false;
        find2 = recursion(root->right,bp2,bq2,p,q);
        if(find2) return true;
        if(root->val == p->val){
            ifp = true;
            ifq = (bq1||bq2);
        }
        else if(root->val == q->val){
            ifq = true;
            ifp = (bp1||bp2);
        }else{
            ifp = (bp1||bp2);
            ifq = (bq1||bq2);
        }
        if(ifp && ifq && !ancestor){
            ancestor = root;
            return true;
        }
        return false;
    }
};

5. 分支界限——大礼包

在LeetCode商店中，有许多在售的物品。
然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
任意大礼包可无限次购买。

示例 1:
输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释:
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2，你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B，所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。

示例 2:
输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
输出: 11
解释:
A，B，C的价格分别为¥2，¥3，¥4.
你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。
你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
说明:
最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。

class Solution
{
private:
    map<vector<int>, int> records;
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        if(records.find(needs)!=records.end())
            return records[needs];
        int res=0,n=needs.size();
        for (int i = 0; i < n;i++)
        {
            res += needs[i] *price[i];
        }
        for (auto gift: special){
            vector<int> copyneeds(needs);
            int i;
            for (i = 0; i < n;i++){
                if(gift[i] > needs[i]){
                    break;
                }
                else{
                    copyneeds[i] -= gift[i];
                }
            }
            if(i==n){
                res = min(res, gift[i] + shoppingOffers(price, special, copyneeds));
            }
        }
        records[needs] = res;
        return res;
    }
};

6.为表达式设计优先级

题目：
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及。
示例:
输入: “23-45”
输出: [-34, -14, -10, -10, 10]
解释:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
算法:
每一个表达式都可以写成 exp = exp1 op exp2 的形式，因此可用递归求解。
此外可用*备忘录优化，记录已经算出所有结果的表达式。

class Solution {
private:
    unordered_map<string, vector<int>> mymap;
public:
    vector<int> diffWaysToCompute(string expression) {
        if(mymap.find(expression)!=mymap.end()){
            return mymap[expression];
        }
        int n=expression.size(),num=0,i;
        vector<int> res;
        for(i=0;i<n;i++){
            if(expression[i]<'0' || expression[i]>'9') break;
            num = num*10 + expression[i] - '0';
        }
        if(i==n){
            res.push_back(num);
            return res;
        }
        for(i=0;i<n;i++){
            if(expression[i]>='0' && expression[i]<='9') continue;
            vector<int> left = diffWaysToCompute(expression.substr(0, i));
            vector<int> right = diffWaysToCompute(expression.substr(i+1,n-1-i));
            for(auto x : left){
                for(auto y: right){
                    switch(expression[i]){
                        case '+':res.push_back(x+y);break;
                        case '-':res.push_back(x-y);break;
                        case '*':res.push_back(x*y);break;
                        default:break;
                    }
                }
            }
        }
        mymap[expression] = res;
        return res;
    }
};