文档章节

LeetCode 494解题思路

爱喝冰可乐
 爱喝冰可乐
发布于 2017/09/03 10:03
字数 379
阅读 5
收藏 0

问题链接:https://leetcode.com/problems/target-sum/description/

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

自己写的暴力搜索的方法,确实不行后来参考了讨论区大神的做法,感觉不得不佩服大神,真是又简单又省时间的算法。

直接上Code:

class Solution {
  public int findTargetSumWays(int[] nums, int s) {
        int sum = 0;
        for (int n : nums)
            sum += n;
        return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1); 
    }   

    public int subsetSum(int[] nums, int s) {
        int[] dp = new int[s + 1]; 
        dp[0] = 1;
        for (int n : nums)
            for (int i = s; i >= n; i--)
                dp[i] += dp[i - n]; 
        return dp[s];
    } 
}

首先,结果肯定分为只有“+”和只有“-”。设第一部分和为sum(P),第二部分和为sum(N)。
 

sum(P) - sum(N) = target 

sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N) 

2 * sum(P) = target + sum(nums)

这问题就很简单了。就是背包问题,从sums中挑选数字放入背包中,只要是满足背包刚好是(target + sum(nums))>>> 1就行。

每次foreach循环后都是和为1有几种情况,2有几种情况......s有几种情况。所及最后返回dp[s]。

© 著作权归作者所有

爱喝冰可乐
粉丝 0
博文 2
码字总数 545
作品 0
深圳
程序员
私信 提问
LeetCode - 014 - 最长公共前缀(longest-common-prefix)

Create by jsliang on 2019-06-03 10:13:01 Recently revised in 2019-06-03 17:29:09 为方便小伙伴们的查看,欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/04
0
0
LeetCode - 021 - 合并两个有序链表(merge-two-sorted-lists)

Create by jsliang on 2019-06-05 08:37:00 Recently revised in 2019-06-05 17:31:37 为方便小伙伴们的查看,欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/06
0
0
LeetCode - 027 - 移除元素(remove-element)

Create by jsliang on 2019-06-06 15:56:49 Recently revised in 2019-06-10 07:42:46 为方便小伙伴们的查看,欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/10
0
0
LeetCode - 007 - 整数反转(reverse-integer)

Create by jsliang on 2019-05-19 09:42:39 Recently revised in 2019-05-19 16:08:24 Hello 小伙伴们,如果觉得本文还不错,记得给个 star , 小伙伴们的 star 是我持续更新的动力!GitHub ...

jsliang
05/19
0
0
LeetCode - 026 - 删除排序数组中的重复项(remove-duplicates-from-sorted-array)

Create by jsliang on 2019-06-06 11:11:26 Recently revised in 2019-06-06 14:30:57 为方便小伙伴们的查看,欢迎切换到不同地址~ 文档库 LeetCode 系列 GitHub 地址 文档库 LeetCode 系列 ...

jsliang
06/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 如果是个帅小伙你愿意和他出去吗

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 小小编辑推荐:《Ghost 》游戏《死亡搁浅》原声 《Ghost 》游戏(《死亡搁浅》原声) - Au/Ra / Alan Walker 手机党少年们想听歌,请使劲儿戳...

小小编辑
今天
176
6
java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
16
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部