wap网站如何做,房地产政策政策最新消息,企业网站在线留言,flash网站欣赏一、题目
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a;
例如#xff0c;nums [2, 1] #xff0c;可以在 2 之前添加 #xff0c;在 1 之前添加 - 或 - 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 示例 1
输入nums [1,1,1,1,1], target 3
输出5
解释一共有 5 种方法让最终目标和为 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
1 1 1 1 - 1 3示例 2
输入nums [1], target 1
输出1 二、思路解析
这道题本质也是求相同的子问题直接考虑递归。
解法一
解法一我是定义了一个 int 类型全局变量 path在递归的过程让数组的元素依次加到和减到 path 变量中最后比较 path 的值和要求的值是否一致即可。
这种解法还是比较直观的就是有个小细节别忘了每次嵌套递归完的恢复现场操作。 解法二
而解法二我是在 dfs 函数的参数列表多加了一个 int 类型变量 path。
在嵌套递归的时候就不用再写恢复现场操作的代码了因为在每次递归调用结束后没有对状态进行修改或保存所以不需要手动恢复现场。
我们再回过头来看解法一需要实现“恢复现场”操作是因为使用了一个全局变量 path 来保存当前路径和在递归过程中会被多次修改如果不及时恢复现场可能会导致后续递归操作出现错误。
所以二者的本质区别在于是否使用了共享状态。 解法一通过全局变量共享了当前路径和导致需要实现“恢复现场”操作 解法二没有使用共享状态每次递归调用都传入了当前路径和避免了这个问题。 这一步操作值得各位仔细品味。 三、完整代码
class Solution {// // 解法一// int ret;// int target;// int path;// public int findTargetSumWays(int[] nums, int _target) {// target _target;// // 解法一// dfs(nums , 0);// return ret;// }// public void dfs(int[] nums , int pos){// if(pos nums.length){// if(path target){// ret ;// } // return;// }// path nums[pos];// dfs(nums , pos 1);// path - nums[pos];// path - nums[pos];// dfs(nums , pos 1);// path nums[pos];// }// 解法二int ret;int target;public int findTargetSumWays(int[] nums, int _target) {target _target;dfs(nums , 0 , 0);return ret;}public void dfs(int[] nums , int pos , int path){if(pos nums.length){if(path target){ret ;} return;}dfs(nums , pos 1 , path nums[pos]);dfs(nums , pos 1 , path - nums[pos]);}
} 以上就是本篇博客的全部内容啦如有不足之处还请各位指出期待能和各位一起进步
