精华内容
下载资源
问答
  • 划分数组为和相等两部分 416. Partition Equal Subset Sum (Medium) 题目描述:   给定一个数组,判断其是否可以被划分为相等两部分。 思路分析:   我们可以换一种思路,判断其是否可以分为相等两部分,...

    划分数组为和相等的两部分

    416. Partition Equal Subset Sum (Medium)

    题目描述:

      给定一个数组,判断其是否可以被划分为相等的两部分。

    思路分析:

      我们可以换一种思路,判断其是否可以分为相等的两部分,其实就是看是否能在数组中挑选出和为数组和一半的序列。那么就可以转化为背包问题,在N个数中挑选数字使其和为数组和的一半,状态转移方程为:

      dp[i]=dp[i] || dp[i-num]

    代码:

    public boolean canPartition(int []nums){
        int sum=0;
        for(int num:nums){
            sum=sum+num;
        }
        if(sum%2!=0)
            return false;
        int target=sum/2;
        boolean []dp=new boolean [target+1];
        dp[0]=true;
        for(int num:nums){ //0-1背包一个物品只能用一次
            for(int i=target;i>=num;i--){ //从后向前,先计算dp[i],再计算dp[i-num]
                dp[i]=dp[i]||dp[i-num];
            }
        }
        return dp[target];
    }

    转载于:https://www.cnblogs.com/yjxyy/p/11119379.html

    展开全文
  • [LeetCode] Partition Equal Subset Sum 相同子集分割 偶数, 除以2, 或方法求解 Given anon-emptyarray containingonly positive integers, find if the array can be partitioned into two subsets such ...

    [LeetCode] Partition Equal Subset Sum 相同子集和分割

    偶数, 除以2, 或方法求解

     

    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:
    Both the array size and each of the array element will not exceed 100.

    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.

    这道题给了我们一个数组,问我们这个数组能不能分成两个非空子集合,使得两个子集合的元素之和相同。那么我们想,原数组所有数字和一定是偶数,不然根本无法拆成两个和相同的子集合,那么我们只需要算出原数组的数字之和,然后除以2,就是我们的target,那么问题就转换为能不能找到一个非空子集合,使得其数字之和为target。开始我想的是遍历所有子集合,算和,但是这种方法无法通过OJ的大数据集合。于是乎,动态规划 Dynamic Programming 就是我们的不二之选。我们定义一个一维的dp数组,其中dp[i]表示原数组是否可以取出若干个数字,其和为i。那么我们最后只需要返回dp[target]就行了。初始化dp[0]为true,由于题目中限制了所有数字为正数,那么就不用担心会出现和为0或者负数的情况。关键问题就是要找出状态转移方程了,我们需要遍历原数组中的数字,对于遍历到的每个数字nums[i],需要更新dp数组,我们的最终目标是想知道dp[target]的boolean值,就要想办法用数组中的数字去凑出target,因为都是正数,所以只会越加越大,那么加上nums[i]就有可能会组成区间 [nums[i], target] 中的某个值,那么对于这个区间中的任意一个数字j,如果 dp[j - nums[i]] 为true的话,说明现在已经可以组成 j-nums[i] 这个数字了,再加上nums[i],就可以组成数字j了,那么dp[j]就一定为true。如果之前dp[j]已经为true了,当然还要保持true,所以还要‘或’上自身,于是状态转移方程如下:

    dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)

    有了状态转移方程,那么我们就可以写出代码了,这里需要特别注意的是,第二个for循环一定要从target遍历到nums[i],而不能反过来,想想为什么呢?因为如果我们从nums[i]遍历到target的话,假如nums[i]=1的话,那么[1, target]中所有的dp值都是true,因为dp[0]是true,dp[1]会或上dp[0],为true,dp[2]会或上dp[1],为true,依此类推,完全使我们的dp数组失效了,参见代码如下:

    1. 要想到数组元素的和必须是偶数

    2.定义一个一维的dp数组,其中dp[i]表示原数组是否可以取出若干个数字,其和为i,只需要返回dp[target]

    3.如果 dp[j - nums[i]] 为true的话,说明现在已经可以组成 j-nums[i] 这个数字了,再加上nums[i],就可以组成数字j了,那么dp[j]就一定为true。如果之前dp[j]已经为true了,当然还要保持true,所以还要‘或’上自身

    4.这里需要特别注意的是,第二个for循环一定要从target遍历到nums[i],而不能反过来,想想为什么呢?因为如果我们从nums[i]遍历到target的话,假如nums[i]=1的话,那么[1, target]中所有的dp值都是true,因为dp[0]是true,dp[1]或上dp[0],为true,dp[2]会或上dp[1],为true,依此类推,完全使我们的dp数组失效了

    5 可以给数组排个序来看, 这里既然是先判断出可以整数合适偶数了 那么只要找到第一个完成dp[target]的子序列就代表后面子序列的和一一定是dp[target]

    但其实不用排序也可以 因为每个从0 到 target 会以此比较 

    class Solution {
        
        public boolean canPartition(int[] nums) {
        int sum = computeArraySum(nums);
        if (sum % 2 != 0) {
            return false;
        }
        int W = sum / 2;
        boolean[] dp = new boolean[W + 1];
        dp[0] = true;
        for (int num : nums) {                 // 0-1 背包一个物品只能用一次
            for (int i = W; i >= 1; i--) {   // 从后往前,先计算 dp[i] 再计算 dp[i-num]
                if(i >= num)
                    dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[W];
    }
    
        private int computeArraySum(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            return sum;
        }
    }

    最初版本

    class Solution {
        public boolean canPartition(int[] nums) {
            int sum = computeArraySum(nums);
        if (sum % 2 != 0) {
            return false;
        }
        int W = sum / 2;
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][W + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            int num = nums[i-1];        // 0-1 背包一个物品只能用一次
            for (int j = 1; j <= W; j++) { 
                if(j >= num)// 从后往前,先计算 dp[i] 再计算 dp[i-num]
                    dp[i][j] = dp[i-1][j] || dp[i - 1][j - num];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][W];
    }
    
        private int computeArraySum(int[] nums) {
            int sum = 0;
            for (int num : nums) {
            sum += num;
            }
            return sum;
        }
    }

     

    展开全文
  • 2018-08-13 17:35:09一、Partition Equal Subset Sum问题描述:问题求解:二分本质上其实是一个背包问题,就是问是否存在一种情况,使得可以填满一个sum/2的背包。public boolean canPartition(int[] nums) {int ...

    2018-08-13 17:35:09

    一、Partition Equal Subset Sum

    问题描述:

    问题求解:

    二分和本质上其实是一个背包问题,就是问是否存在一种情况,使得可以填满一个sum/2的背包。

    public boolean canPartition(int[] nums) {

    int sum = 0;

    for (int i : nums) sum += i;

    if (sum % 2 != 0) return false;

    sum /= 2;

    boolean dp[] = new boolean[sum + 1];

    dp[0] = true;

    for (int num : nums) {

    for (int i = sum; i >= num; i--) {

    dp[i] = dp[i] || dp[i - num];

    }

    }

    return dp[sum];

    }

    二、Partition to K Equal Sum Subsets

    问题描述:

    问题求解:

    Brute Force,本质是使用组合数进行解空间的遍历。

    PS.使用排列数也可以,但是效率比组合数要慢上不少。

    public boolean canPartitionKSubsets(int[] nums, int k) {

    int sum = 0;

    for (int i = 0; i < nums.length; i++) sum += nums[i];

    if (sum % k != 0) return false;

    Arrays.sort(nums);

    int eachSum = sum / k;

    int[] visited = new int[nums.length];

    return helper(nums, eachSum, 0, visited, 0, k);

    }

    private boolean helper(int[] nums, int eachSum, int curSum, int[] visited, int start, int k) {

    if (k == 0) return true;

    if (curSum > eachSum) return false;

    if (curSum == eachSum) return helper(nums, eachSum, 0, visited, 0, k - 1);

    for (int i = start; i < nums.length; i++) {

    if (visited[i] == 1 || (i > start && nums[i] == nums[i - 1] && visited[i - 1] == 0)) continue;

    visited[i] = 1;

    if (helper(nums, eachSum, curSum + nums[i], visited, i + 1, k)) return true;

    visited[i] = 0;

    }

    return false;

    }

    三、Matchsticks to Square

    问题描述:

    问题求解:

    k = 4.

    public boolean makesquare(int[] nums) {

    if (nums.length == 0) return false;

    int sum = 0;

    for (int num : nums) sum += num;

    if (sum % 4 != 0) return false;

    int eachSum = sum / 4;

    Arrays.sort(nums);

    return helper(nums, eachSum, 0, new int[nums.length], 0, 4);

    }

    private boolean helper(int[] nums, int eachSum, int curSum, int[] visited, int start, int k) {

    if (k == 0) return true;

    if (curSum > eachSum) return false;

    if (curSum == eachSum) return helper(nums, eachSum, 0, visited, 0, k - 1);

    for (int i = start; i < nums.length; i++) {

    if (visited[i] == 1 || (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0)) continue;

    visited[i] = 1;

    if (helper(nums, eachSum, curSum + nums[i], visited, i + 1, k)) return true;

    visited[i] = 0;

    }

    return false;

    }

    展开全文
  • 将一个数组划分成总和相等两部分(分割数组) 思想 1. 先求和sum/2,判断是否可分割 2. 递归求和 c++代码 include &lt;iostream&gt; include&lt;list&gt; using namespace std; int ...

    将一个数组划分成总和相等的两部分(分割数组)

    思想
    1. 先求和sum/2,判断是否可分割
    2. 递归求和

    c++代码

    include <iostream>
    include<list>
    using namespace std;
    
    int getSum(int A[], int len)
    {
        int sum = 0;
        for (int i = 0; i<len; i++)
        {
            sum += A[i];
        }
        return sum;
    }
    
    bool foo(int A[], int len, int curSum, int defSum, int B[], int curPos)
    {
        if (curSum == defSum)
        {
            return true;
        }
    
        if (len == 0)
            return false;
    
        bool bFound = false;
        for (int i = 0; i < len; i++)
        {
            if (curSum + A[i] <= defSum)
            {
                B[curPos++] = A[i];
                if (foo(&A[i+1], len - 1, curSum + A[i], defSum, B, curPos))
                {
                    bFound = true;
                    break;
                }
                B[curPos] = 0;
                curPos--;
            }
        }
    
        return bFound;
    }
    
    
    
    void main()
    {
    
        int Array[1000]; 
        int length;
        while (cin >> length)
        {
            for (int i = 0; i < length; i++)
            {
                cin >> Array[i];
            }
            int B[500];
            int sum = getSum(Array, length);
            if (sum % 2 == 0)
            {
                bool JudgeSuccess = foo(Array, length, 0, sum / 2, B, 0);
                if (JudgeSuccess)
                    cout << "True" << endl;
                else
                    cout << "False" << endl;
            }
            else
                cout << "False" << endl;
        }
    
    
        system("pause");
    }
    展开全文
  • 判断给定的一个数组,是不是可以分成数组和相等数组 Example: [1,2,6,3]可以分成[1,2,3][6] 算法:动态规划 class Solution(object): def canPartition(self, nums): """ :type nums: List[int] :...
  • 什么80%的码农都做不了架构师?>>> ...
  • 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] = =A[i+1] + A[i+2] + … + A[j-1] == A[j] +...
  • 此题可以用0,1背包问题来解决,分成的数组,一定整个数组的一半,所以将背包容量设初始数组的一半即可,最后在判断背包所装的容量是不是整个数组的一半。 代码: #include &lt;...
  • 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] +...
  • //如果大于的话就看它的dp[i][j]=dp[i-1][j-arr.elementAt(i)]true,如果true则这个也true }if(j==arr.elementAt(i)) { //相等则赋值true,因为只有在它的子序列中找到一个能正好填满背包的值就可以 dp...
  • Reduction:给定partition problem的实例,创建每个大小1的列表。结果将是这个问题。以上结论:这个问题是NP-Hard,没有已知的多项式解。第二,由于问题的严重性,任何指数伪多项式解决方案都需要很长时间才能...
  • 声明:原题目转载自LeetCode,解答部分为原创 Problem :  Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the ...
  • 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + ...
  • 数组分成个尽量相等的子数组

    千次阅读 2019-09-22 18:44:34
    将一个数组分成两部分,不要求两部分所包含的元素个数相等,要求使得这两个部分的的差值最小。比如对于数组{1,0,1,7,2,4},可以分成{1,0,1,2,4}{7},使得这两部分的差值最小。 思路: 这个问题可以转化求...
  • 给你一个整数数组 arr,只有可以将其划分为三个和相等的 非空 部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i + 1 < j 且满足 (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ...
  • //表示第j个及地j之前的元素的组合的和为0的存在性1 因为第j个及地j之前的元素一个都不选结果就是0 } for (int i = 1; i; i++) //loop从第一个元素到最后一个元素 { for (int j = 1; j; j++) //loop从1到...
  • 首先用accumulate函数求出数组的总和,再得到每一段的,之后利用双指针ij,分别从数组的0size-1开始寻找满足和为每一段的数组段,找到之后记录ij的值,再求ij中间的,判断是否符合。 代码 class ...
  • 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] +...
  • 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + ...
  • /*! * @file 数组分割.cpp ... * @brief: 将数组分割成两部分两部分和相等的部分;判断是否存在这样的分割 思路1:递归:1、先求出这个数组, 2、看这个能不能被2整除,可以的话再进行...
  • 给你一个整数数组A,只有可以将其划分为三个和相等的非空部分时才返回true,否则返回 false。 形式上,如果可以找出索引i+1 < j且满足(A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A...
  • 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] +...
  • Java实现 LeetCode 1013 将数组分成和相等的三个部分

    万次阅读 多人点赞 2020-03-11 11:38:51
    给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] +...
  • 数组 (0, i - 1),(i + 1, j - 1),(j + 1, k - 1),(k + 1, n - 1) 的应该相等。 这里我们定义子数组 (L, R) 表示原数组从索引L的元素开始至索引R的元素。 示例: 输入: [1,2,1,2,1,2,1] 输出: True
  • 类似,那道题只让分成个子集合,所以问题可以转换是否存在和为整个数组和的一半的子集合,可以用dp来做。但是这道题让求k个相同的,感觉无法用dp来做,因为就算找出了一个,其余的也需要验证。 dfs,首先...
  • LeetCode刷题笔记之将数组分成和相等的三个部分
  • 力扣题目地址:...首先看题目: 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] ...
  • 给定一个整数数组 A,只有我们可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果我们可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] =...
  • 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] +...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,119
精华内容 15,647
关键字:

划分数组为和相等的两部分