注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(67)-用加号或者减号计算[算法]  

2018-01-20 02:28:05|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题:给你由n个非负的整数a1, a2, …, an组成的数组,以及另外一个整数S,你可以在每个整数前面添上+或者-得到一个算数表达式。请问总共有多少中方法使得表达式的计算结果是S

例如,输入数组{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


分析:这是LeetCode的第494题。


解法一: 回溯法(DFS)


我们逐一扫描这个数组。对每个数字,我们都有两个选择,一是在这个数字前面添加加号,二是在这个数字前面添加减号。当给这个数字添加加号或者减号之后,我们再接着扫描下一个数字。因此这是典型的能用回溯法(回溯法也是DFS)解决的问题,可以用递归解决。下面是该解法的Java代码:

public int findTargetSumWays(int[] nums, int S) {
    if (nums == null) {
        return 0;
    }

    int sum = 0;
    for (int num : nums) {
        sum += num;
    }

    return helper(nums, 0, S, sum);
}

private int helper(int[] nums, int index, int S, int sum) {
    if (index == nums.length) {
        return S == 0 ? 1 : 0;
    }

    if (S <= sum && S >= -sum) {
        return helper(nums, index + 1, S + nums[index], sum - nums[index])
             + helper(nums, index + 1, S - nums[index], sum - nums[index]);
    }

    return 0;
}


在上述代码的helper函数中,参数S的意思是数组nums中从下标index开始之后所有数字的目标计算结果,而sum是数组nums中从下标index开始之后所有数字的和。


由于对于数组中的每个数字都有2个选择,因此如果数组的长度是n,那么这个解法的时间复杂度就是O(2^n)。


由于回溯法的时间复杂度很高,在用回溯法解题的时候如果有可能应尽量剪枝避免不比较的计算。


在上述代码中,我们事先计算好数组中所有数字的和sum。每当扫描到一个数字的时候,由于sum的含义是从index之后所有数字的和,所以要把当前数字从sum里面减去。当后面所有数字都添加加号时,S得到最大的结果sum;当后面所有数字都添加减号时,S得到最小的结果-sum。当S>sum或者S<-sum时,则一定不可能找到结果为S的解法,因此没有必要再递归下去。


解法二:动态规划


我们换个角度来看这个问题。假设我们把在前面添加加号的数字单独拿出来,它们的和记为p。剩下的数字我们在它们的前面都添加减号。这些添加减号的数字的和,我们用n表示。按照题目的要求,p-n=S。我们不难求得数组中所有数字的和,记为sum,并且有p+n=sum,也就是n=sum-p。把n=sum-p代入p-n=S中,得到p-(sum-p)=S,也就是p=(S+sum)/2。


分析到这里,我们发现这个题目实际上是求解在数组中有多少种方法可以找出若干数字使得它们的和等于p(即(S+sum)/2)。所以这个解法的总体思路如下:

public int findTargetSumWays(int[] nums, int S) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int sum = 0;
    for (int num : nums) {
        sum += num;
    }

    if ((sum + S) % 2 == 1 || sum < S) {
        return 0;
    }

    return subsetSum(nums, (sum + S) >>> 1);
}

 

接下来求解在数组中有多少种方法可以找出若干数字使得它们的和等于p。这是典型的0-1背包问题,可以用动态规划求解。


我们定义函数f(i,j)表示数组中前i个数字中选出若干个和为j的数字的方法总数。我们分析就能知道f(i,j)=f(i-1,j)+f(i-1,j-nums[i])。这是因为当我们在考虑第i个数字的时候,有两种选择,一个是不选第i个数字,此时f(i,j)=f(i-1,j)。另一种是我们选择第i个数字,此时f(i,j)=f(i-1,j-nums[i]),也就是在前i-1个数字中选出若干个和为j-nums[i]的方法总数。


我们可以定义一个二维数组,它的行数为数组长度n加1,列数为数字之和p加1的。该数组的第i行第j列是函数f(i,j)的结果。我们再仔细分析发现,我们在求解f(i,j)时只需要用到该二维数组里的第i-1行。并且如果在同一行里我们从右到左求解,我们发现f(i-1,j)在求解完f(i,j)之后再也不需要了。因此我们实际上只需要保留二维数组中的一行就够了,可以减少空间的开销。


以下是数组中选出若干个和为p的方法总数的Java代码:

private int subsetSum(int[] nums, int target) {
    int dp[] = new int[target + 1];
    Arrays.fill(dp, 0);
    dp[0] = 1;

    for (int num : nums) {
        for (int j = target; j >= num; --j) {
            dp[j] += dp[j - num];
        }
    }

    return dp[target];
}


如果数组的长度是n,从数组中选出的数字的目标和为p,那么上述基于动态规划的解法的时间复杂度是O(np),而空间复杂度是O(p)。


本文转载自微信公众号青云算法扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(655)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018