資訊專欄INFORMATION COLUMN
摘要：如果是奇數(shù)的話，那一定是不滿足條件的，可以直接返回。如果是偶數(shù)，將除獲得我們要求的一個(gè)子數(shù)組元素的和。如何暫存我們計(jì)算的中間結(jié)果呢聲明一個(gè)長(zhǎng)度為的布爾值數(shù)組。每個(gè)元素的布爾值代表著，數(shù)組中是否存在滿足加和為的元素序列。
題目詳情
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.想法題目的意思是輸入一個(gè)非空的、只含正整數(shù)的數(shù)組nums，要求我們判斷，數(shù)組nums能否被分成兩個(gè)子數(shù)組，滿足兩個(gè)子數(shù)組的和相等。
例1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 輸入數(shù)組可以被分為[1, 5, 5]和[11].
例2:
輸入: [1, 2, 3, 5]
輸出: false
解釋: 數(shù)組無(wú)法被拆分成兩個(gè)和相等的子數(shù)組.
首先我們需要遍歷一趟得到整個(gè)數(shù)組的和sum，從而求出每個(gè)子數(shù)組元素的加和(sum/2)。
如果sum是奇數(shù)的話，那一定是不滿足條件的，可以直接返回false。如果sum是偶數(shù)，將sum除2獲得我們要求的一個(gè)子數(shù)組元素的和。
如何暫存我們計(jì)算的中間結(jié)果呢？
聲明一個(gè)長(zhǎng)度為sum+1的布爾值數(shù)組res。每個(gè)元素的布爾值res[i]代表著，數(shù)組中是否存在滿足加和為i的元素序列。
對(duì)于每一個(gè)元素，我們都要求出他以及前面遍歷過(guò)的元素所組合出的元素和。
public boolean canPartition(int[] nums) {
int sum = 0;
for(int num : nums){
sum += num;
}
if(sum % 2 != 0)return false;
sum /= 2;
boolean[] res = new boolean[sum+1];
int length = nums.length;
res[0] = true;
for(int i=1;i<=length;i++){
for(int j=sum;j>=nums[i-1];j--){
res[j] = res[j-nums[i-1]] || res[j];
}
}
return res[sum];
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/71023.html
摘要：題目要求假設(shè)有一個(gè)全為正整數(shù)的非空數(shù)組，將其中的數(shù)字分為兩部分，確保兩部分?jǐn)?shù)字的和相等。而這里的問(wèn)題等價(jià)于，有個(gè)物品，每個(gè)物品承重為，問(wèn)如何挑選物品，使得背包的承重搞好為所有物品重量和的一般。 題目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...
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 ...
摘要：背包問(wèn)題假設(shè)有個(gè)寶石，只有一個(gè)容量為的背包，且第個(gè)寶石所對(duì)應(yīng)的重量和價(jià)值為和求裝哪些寶石可以獲得最大的價(jià)值收益思路我們將個(gè)寶石進(jìn)行編號(hào)，尋找的狀態(tài)和狀態(tài)轉(zhuǎn)移方程。我們用表示將前個(gè)寶石裝到剩余容量為的背包中，那么久很容易得到狀態(tài)轉(zhuǎn)移方程了。 Partition Equal Subset Sum Given a non-empty array containing only posi...
摘要：前言從開(kāi)始寫(xiě)相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開(kāi)始寫(xiě)leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
Problem Given an array of integers nums and a positive integer k, find whether its possible to divide this array into k non-empty subsets whose sums are all equal. Example 1:Input: nums = [4, 3, 2, 3,...
閱讀 2696·2021-10-14 09:43
閱讀 3640·2021-10-13 09:39
閱讀 3355·2019-08-30 15:44
閱讀 3209·2019-08-29 16:37
閱讀 3782·2019-08-29 13:17
閱讀 2790·2019-08-26 13:57
閱讀 1896·2019-08-26 11:59
閱讀 1347·2019-08-26 11:46
