摘要:題目鏈接,可以,不過這題可以,所以可以用做或者來做,還是得用二維數組保存算過的結果。這題的是到第個數時,能夠得到為的數量,由于可能是負數,所以要做一個,使其從開始。滾動數組優化空間。
Target Sum
題目鏈接:https://leetcode.com/problems...
dp,可以brute force,不過這題可以memory,所以可以iteration用dp table做或者recursion:dfs+suffix array來做,還是得用二維數組保存算過的結果。這題的subproblem是到第i個數時,能夠得到sum為j的ways數量,由于sum可能是負數,所以要做一個shift,使其從0開始。滾動數組優化空間。
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]; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66595.html
摘要:為了避免得到重復結果,我們不僅要跳過重復元素,而且要保證找的范圍要是在我們最先選定的那個數之后的。而計算則同樣是先選一個數,然后再剩下的數中計算。 2Sum 在分析多數和之前,請先看Two Sum的詳解 3Sum 請參閱:https://yanjia.me/zh/2019/01/... 雙指針法 復雜度 時間 O(N^2) 空間 O(1) 思路 3Sum其實可以轉化成一個2Sum的題,...
摘要:找符合條件的總數。雙指針區間考慮邊界,長度,為空,等。之后的范圍用雙指針和表示。若三個指針的數字之和為,加入結果數組。不要求,所以不用判斷了。同理,頭部兩個指針向后推移,后面建立左右指針夾逼,找到四指針和為目標值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...
摘要:一有序數組的題目描述在有序數組中找出兩個數,使它們的和為。解題思路使用雙指針,一個指針指向值較小的元素,一個指針指向值較大的元素。輸出二兩數平方和判斷一個數是否為數平方和開平方根 一、有序數組的 Two Sum Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 題目描述:在有序數組中找出兩個數,使它們...
摘要:這里需要注意及時處理掉重復的情況。那么就需要盡可能排除不可能的情況來提高計算效率。因為數組已經被排序,所以可以根據數組中元素的位置判斷接下來的情況是否有可能合成目標值。 題目要求 此處為原題地址 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d =...
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 ...
摘要:為了尋找合適的正負號賦值,我們其實可以將數組分為兩個子集,其中一個子集中的數字都被賦予了正號,而另一個子集中的數字都被賦予了負號。如果二者的和不是一個偶數,就一定無法找到這樣的正負號集合使得其結果為。 題目要求 You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now yo...
閱讀 2574·2021-09-30 09:48
閱讀 2564·2019-08-30 14:10
閱讀 2708·2019-08-29 11:22
閱讀 1837·2019-08-26 13:51
閱讀 2276·2019-08-26 12:02
閱讀 2415·2019-08-23 16:06
閱讀 3548·2019-08-23 14:06
閱讀 1093·2019-08-23 13:56