wordpress applyfilters,郑州网站制作专业乐云seo,学习做网站的孛校,企业如何建设网站呢494. 目标和 - 力扣#xff08;LeetCode#xff09;
方法一#xff0c;暴力dfs
直接进行深搜查找出所有的情况#xff0c;缺点严重超时#xff0c;只能过20个案例
留一下超时的
class Solution {//首先定义全局变量int[] abs { 1, -1 }; //用来记录当前遍历的数的正…494. 目标和 - 力扣LeetCode
方法一暴力dfs
直接进行深搜查找出所有的情况缺点严重超时只能过20个案例
留一下超时的
class Solution {//首先定义全局变量int[] abs { 1, -1 }; //用来记录当前遍历的数的正负ListListInteger list; //所有的结果ListInteger res; //记录当前的结果public int findTargetSumWays(int[] nums, int target) {//初始化res new LinkedList();list new ArrayList();dfs(nums, target, 0, 0);return list.size();}//可直接套用dfs模版public void dfs(int[] nums, int target, int sum, int index) {//如果满足条件则把当前的记录加入所有的结果当中if (res.size() nums.length sum target) {list.add(new ArrayList(res));return;}//从index进行遍历避免遍历重复数据for (int i index; i nums.length; i) {//遍历数字的正负两种情况for (int j 0; j 2; j) {int x nums[i] * abs[j];res.add(x);dfs(nums, target, sum x, i 1);//剪枝移除最后的数据res.remove(res.size() - 1);}}}
}
dfs优化 可通过
因为这一道题不需要记录所有的方法只需要统计一共的个数所以可以进行优化
class Solution {//定义全局变量int count 0;public int findTargetSumWays(int[] nums, int target) {count 0;dfs(nums, target, 0, 0);return count;}public void dfs(int[] nums, int target, int sum, int index) {if (index nums.length) {//这里的if不能合并因为不管sum满不满足条件都需要回溯if (sum target) {count;}return;}//当前数为正数dfs(nums, target, sum nums[index], index 1);//当前数为负数dfs(nums, target, sum - nums[index], index 1);}
}
