国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LeetCode] 416. Partition Equal Subset Sum

makeFoxPlay / 3527人閱讀

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 element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.
Solution DFS1
class Solution {
    public boolean canPartition(int[] nums) {
        Map map = new HashMap<>();
        int sum = 0;
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
            sum += num;
        }
        if (sum % 2 != 0) return false;
        return dfs(map, sum/2);
    }
    private boolean dfs(Map map, int target) {
        if (map.containsKey(target) && map.get(target) > 0) return true;
        for (int num: map.keySet()) {
            if (num < target && map.get(num) > 0) {
                map.put(num, map.get(num)-1);
                if (dfs(map, target-num)) return true;
                map.put(num, map.get(num)+1);
            }
        }
        return false;
    }
}
DFS2 - TLE
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num: nums) sum += num;
        if (sum%2 != 0) return false;
        int target = sum/2;
        return dfs(nums, new boolean[nums.length], 0, 0, target);
    }
    private boolean dfs(int[] nums, boolean[] used, int start, int sum, int target) {
        if (sum > target || start >= nums.length) return false;
        if (sum == target) return true;
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > target) return false;
            if (!used[i]) {
                used[i] = true;
                if (dfs(nums, used, i+1, sum+nums[i], target)) return true;
                used[i] = false;
            }
        }
        return false;
    }
}

TLE for this test case:
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/72189.html

相關文章

  • leetcode 416 Partition Equal Subset Sum

    摘要:如果是奇數的話,那一定是不滿足條件的,可以直接返回。如果是偶數,將除獲得我們要求的一個子數組元素的和。如何暫存我們計算的中間結果呢聲明一個長度為的布爾值數組。每個元素的布爾值代表著,數組中是否存在滿足加和為的元素序列。 題目詳情 Given a non-empty array containing only positive integers, find if the array ca...

    jsummer 評論0 收藏0
  • leetcode416. Partition Equal Subset Sum

    摘要:題目要求假設有一個全為正整數的非空數組,將其中的數字分為兩部分,確保兩部分數字的和相等。而這里的問題等價于,有個物品,每個物品承重為,問如何挑選物品,使得背包的承重搞好為所有物品重量和的一般。 題目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...

    Caicloud 評論0 收藏0
  • [Leetcode - Dynamic Programming] Partition Equal S

    摘要:背包問題假設有個寶石,只有一個容量為的背包,且第個寶石所對應的重量和價值為和求裝哪些寶石可以獲得最大的價值收益思路我們將個寶石進行編號,尋找的狀態和狀態轉移方程。我們用表示將前個寶石裝到剩余容量為的背包中,那么久很容易得到狀態轉移方程了。 Partition Equal Subset Sum Given a non-empty array containing only posi...

    qpal 評論0 收藏0
  • leetcode 部分解答索引(持續更新~)

    摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0
  • [LeetCode] 698. Partition to K Equal Sum Subsets

    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,...

    kuangcaibao 評論0 收藏0

發表評論

0條評論

makeFoxPlay

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<