Leetcode 494：目标和

题目描述

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

解题思路

这个题本质上是一个背包问题。但是如果不进行一些推导，我们很难看出这是一个背包问题。所以这真的是很考察人的逻辑思维能力。

由题目可知，数组里面的数字要么为加上的数字要么为减去的数字，所以我们可以将这两组数字分为两组，一组为要加上的数字，我们命名为P，它的和为sum(P)；一组为要减去的数字，我们命名为N，它的和为sum(N)。另外我们将数组中所有和命名为sum(nums)。那么可以得到sum(P)-sum(N)=target。

进一步推导，

sum(nums)+sum(P)-sum(N)=target+sum(nums)
==>sum(P)+sum(N)+sum(P)-sum(N)=target+sum(nums)
==>2*sum(P)=target+sum(nums)
==>sum(P)=(target+sum(nums))/2

那么这个问题就转化为了：在nums数组中选择哪些数字，使它们的和为(target+sum(nums))/2。这个问题，我们就可以使用0-1背包来解决。

其实从这个新的问题我们就可以看出，若sum(P)为奇数，那么就不存在相应的组合。

0-1背包问题，我们可以使用动态规划的思想来解决。我们新建一个dp数组，大小为(target+sum(nums))/2+1。对于数组中每一个元素来说，其下标代表着和为当前数的方案数（例如dp[4]=9代表和为4有9种情况）。
代码中for循环的意思，其实是针对前i个数的情况下，和的值为相应下标有多少种情况（例如在对于第3个1的情况下dp[4]就是代表着加入这个数组只有前3个数字，那么就在这三个数字情况下和为4有多少种情况）。其实这是一个动态更新的过程。

我们知道对于0-1背包问题来说，当前物品有两种情况，一为选择二为不选择。所以对于0-1背包问题来说，目标值=当前物品不选择且前一步骤达到目标值的情况+前一步骤没有达到目标值且加上当前物品恰好达到目标值的情况。
那么对于dp[i]=dp[i]+dp[i-num]来说，等号后面的dp[i]的值是上一步计算出来的和为i的情况数，也就是说我们在上一步选择完成之后已经达到了我们的target，那么当前数字肯定不选择，所以dp[i]就是代表了这种情况。

对于后面的dp[i-num]来说，就是前一步骤没有达到目标值且加上当前物品恰好达到目标值的情况。其实dp[i-num]就是到目前为止和为i-num有多少种选择，所以这也就等价于前一步骤没有达到目标值且加上当前物品恰好达到目标值的情况。

故这就是整个题目的思路。

代码实现

 int findTargetSumWays(vector<int>& nums, int S) {
    int sum = 0;
    int times = 0;
    for (int n : nums)
    {
        sum += n;
    }
    if (sum < S||(sum+S)%2==1)
        return 0;
    S = (S + sum) / 2;
    vector<int>dp(S + 1, 0);
    dp[0] = 1;
    for (int num : nums)
    {
        for (int i = S;i >= num;i--)
            dp[i] += dp[i - num];
    }
    return dp[S];
}

Leetcode 538：把二叉搜索树转换成累加树

题目描述

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

示例

输入: 二叉搜索树:
5
/ \
2 13

输出: 转换为累加树:
18
/ \
20 13

解题思路

这个题其实就是一个变相的中序遍历，所以按照中序遍历进行处理即可。具体看代码。

代码实现

    int num=0;
    TreeNode* convertBST(TreeNode* root) {
        if(root!=nullptr)
        {
            convertBST(root->right);
            root->val=root->val+num;
            num=root->val;
            convertBST(root->left);
            return root;
        }
        return nullptr;
    }