Target Sum

wind3110991 發(fā)布于2019-08-14 17:22 / 2216人閱讀

摘要：題目鏈接，可以，不過這題可以，所以可以用做或者來做，還是得用二維數(shù)組保存算過的結(jié)果。這題的是到第個數(shù)時，能夠得到為的數(shù)量，由于可能是負(fù)數(shù)，所以要做一個，使其從開始。滾動數(shù)組優(yōu)化空間。

Target Sum

題目鏈接：https://leetcode.com/problems...

dp，可以brute force，不過這題可以memory，所以可以iteration用dp table做或者recursion：dfs+suffix array來做，還是得用二維數(shù)組保存算過的結(jié)果。這題的subproblem是到第i個數(shù)時，能夠得到sum為j的ways數(shù)量，由于sum可能是負(fù)數(shù)，所以要做一個shift，使其從0開始。滾動數(shù)組優(yōu)化空間。

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        if(nums == null || nums.length == 0) return 0;
        // dp table
        int sum = 0;
        for(int num : nums) sum += num;
        if(S > sum || S < -sum) return 0;
        // dp[i][j]: the number of ways that add up to j using [0, i]
        // function: dp[i+1][j - nums[i]] = dp[i][j]
        //           dp[i+1][j + nums[i]] = dp[i][j]
        // j = [0, 2 * sum + 1]
        int[] dp = new int[2*sum + 1];
        dp[0+sum] = 1;
        for(int i = 0; i < nums.length; i++) {
            int[] next = new int[2*sum + 1];
            for(int j = 0; j < 2 * sum + 1; j++) {
                if(j - nums[i] >= 0 && dp[j] != 0) next[j-nums[i]] += dp[j];
                if(j + nums[i] < 2 * sum + 1 && dp[j] != 0) next[j+nums[i]] += dp[j];
            }
            dp = next.clone();
        }
        return dp[0 + sum + S];
    }
}

GPU云服務(wù)器云服務(wù)器 target sum target roject hibernate 分頁 sum

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66595.html

相關(guān)文章

[Leetcode] 3Sum 4Sum 3Sum Closet 多數(shù)和

摘要：為了避免得到重復(fù)結(jié)果，我們不僅要跳過重復(fù)元素，而且要保證找的范圍要是在我們最先選定的那個數(shù)之后的。而計(jì)算則同樣是先選一個數(shù)，然后再剩下的數(shù)中計(jì)算。 2Sum 在分析多數(shù)和之前，請先看Two Sum的詳解 3Sum 請參閱：https://yanjia.me/zh/2019/01/... 雙指針法復(fù)雜度時間 O(N^2) 空間 O(1) 思路 3Sum其實(shí)可以轉(zhuǎn)化成一個2Sum的題，...

trigkit4 2019-08-14 12:29 評論0 收藏0
【LC總結(jié)】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合條件的總數(shù)。雙指針區(qū)間考慮邊界，長度，為空，等。之后的范圍用雙指針和表示。若三個指針的數(shù)字之和為，加入結(jié)果數(shù)組。不要求，所以不用判斷了。同理，頭部兩個指針向后推移，后面建立左右指針夾逼，找到四指針和為目標(biāo)值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

awesome23 2019-08-14 15:50 評論0 收藏0
Leetcode 題解 - 雙指針

摘要：一有序數(shù)組的題目描述在有序數(shù)組中找出兩個數(shù)，使它們的和為。解題思路使用雙指針，一個指針指向值較小的元素，一個指針指向值較大的元素。輸出二兩數(shù)平方和判斷一個數(shù)是否為數(shù)平方和開平方根一、有序數(shù)組的 Two Sum Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 題目描述：在有序數(shù)組中找出兩個數(shù)，使它們...

leanxi 2019-08-16 18:40 評論0 收藏0
leetcode14 4sum

摘要：這里需要注意及時處理掉重復(fù)的情況。那么就需要盡可能排除不可能的情況來提高計(jì)算效率。因?yàn)閿?shù)組已經(jīng)被排序，所以可以根據(jù)數(shù)組中元素的位置判斷接下來的情況是否有可能合成目標(biāo)值。題目要求此處為原題地址 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d =...

MoAir 2019-08-16 10:31 評論0 收藏0
[LeetCode] 416. Partition Equal Subset Sum

Problem Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:Each of the array ...

makeFoxPlay 2019-08-16 13:42 評論0 收藏0
leetcode494. Target Sum

摘要：為了尋找合適的正負(fù)號賦值，我們其實(shí)可以將數(shù)組分為兩個子集，其中一個子集中的數(shù)字都被賦予了正號，而另一個子集中的數(shù)字都被賦予了負(fù)號。如果二者的和不是一個偶數(shù)，就一定無法找到這樣的正負(fù)號集合使得其結(jié)果為。題目要求 You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now yo...

RobinTang 2019-08-15 14:32 評論0 收藏0