精华内容
下载资源
问答
  • 划分数组为和相等的两部分 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;
        }
    }

     

    展开全文
  • 给你一个整数数组 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] + A[j-1] + ... + A[A.length - 1] 就可以将数组三等分。 		这个题目的思路在于,先判断前i项和是否为这个数组和的三分之一,然后在判断前j项和是否为数组和的三分之二,让j肯定要大于i+1,代码实现如下:
    
    public boolean canThreePartsEqualSum(int[] A) {
            int s = 0;
            for (int num : A) {
                s += num;
            }
            if (s % 3 != 0) {
                return false;
            }
            int target = s / 3;
            int n = A.length; 
            int i = 0; 
            int cur = 0;
            while (i < n) {
                cur += A[i];
                if (cur == target) {
                    break;
                }
                i++;
            }
            if (cur != target) {
                return false;
            }
            int j = i + 1;
            while (j  < n -1) {  
                cur += A[j];
                if (cur == target * 2) {
                    return true;
                }
                j++;
            }
            return false;
        }
    
    展开全文
  • 题目描述:给你一个整数数组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] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。

    示例 1:

    输出:[0,2,1,-6,6,-7,9,1,2,0,1]

    输出:true

    解释:0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

    示例 2:

    输入:[0,2,1,-6,6,7,9,-1,2,0,1]

    输出:false

    示例 3:

    输入:[3,3,6,5,-2,2,5,1,-9,4]

    输出:true

    解释:3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

    提示:

    3 <= A.length <= 50000

    -10^4 <= A[i] <= 10^4

    展开全文
  • 声明:原题目转载自LeetCode,解答部分为原创 Problem :  Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the ...
  • 给定一个整数数组 nums 一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。 示例: 输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出: True 说明: 有可能将其分成 4 个子集(5),(1,4...
  • 1 背包空间优化无法使用贪心算法的解释变种划分数组为和相等的两部分改变一组数的正负号使得它...
  • 文章目录斐波那契数列1. 爬楼梯2. 强盗抢劫3. 强盗在环形街区抢劫4. 信件错排5. 母牛生产矩阵路径1. 矩阵的最小路径和2.... 划分数组为和相等的两部分2. 改变一组数的正负号使得它们的和为一给定数3. 01 字符
  • 使用分治技术意味着我们要将子数组划分为两个规模相等的数组,比如分为{low, mid}{mid+1,high}两部分,如此,数组{low,high}的子数组所处的位置必然有三种情况:. 完全位于{low, mid}中 . 完全位于{mid+1,...
  • 这部分内容是参考大神CyC2018的代码总结,将leetcode中和背包问题相关的放在这里。...2.划分数组为相等的两部分 416. Partition Equal Subset Sum (Medium) 题目: 给定一个只包含正整数的非空数组。...
  • 算法16--单链表翻转

    2018-11-09 20:46:37
    5.长度2N的数组划分为相等两部分,使其之和的绝对值最小 反转单链表 递归与非递归方式: 非递归方式 非递归从第一个节点开始翻转链表 可以采用双指针与三指针来实现 三指针: pPre pCur pNext ...
  • 中位数

    2017-02-09 20:23:00
    指​一个样本中,将整体数据按数值大小排列,能将整体划分为个数相等的两部分的书,一般取顺序排列的数组中间一个数或者中间两个数的平均值。 有啥用? 也是作为描述性统计中重要一个指标,主要是用来描述样本的...
  • 栈的压入、弹出序列:建立一个辅助栈,把push序列的数字依次压入辅助栈,每次压入后,比较辅助栈的栈顶元素pop序列的首元素是否相等,相等的话就推出pop序列的首元素辅助栈的栈顶元素,若最后辅助栈空,则push...
  • 7.5.5 重载容易引发误解的两个地方——返回类型形参名 170 7.5.6 重载中的最难点——参数匹配原则 171 7.6 使用类的实例作为方法参数 172 7.6.1 超车方法:使用类实例做参数 172 7.6.2 调用这个方法 173 ...
  • dividing(多重背包)

    2021-01-21 16:46:30
    请判断能否将所有宝石分为两部分,使得两部分价值相等。 注意:宝石不能分割,比如价值6宝石不能分割两个价值3宝石。 Input 每一行输入描述一个要划分的宝石集合。 每个集合有6个非负整数a1, a2,…, a6...
  • 7.5.5 重载容易引发误解的两个地方——返回类型形参名 170 7.5.6 重载中的最难点——参数匹配原则 171 7.6 使用类的实例作为方法参数 172 7.6.1 超车方法:使用类实例做参数 172 7.6.2 调用这个方法 173 ...
  • 7.5.5 重载容易引发误解的两个地方——返回类型形参名 170 7.5.6 重载中的最难点——参数匹配原则 171 7.6 使用类的实例作为方法参数 172 7.6.1 超车方法:使用类实例做参数 172 7.6.2 调用这个方法 173 ...
  • 2021-02-04

    2021-02-04 07:24:32
    请判断能否将所有宝石分为两部分,使得两部分价值相等。 注意:宝石不能分割,比如价值6宝石不能分割两个价值3宝石。 Input 每一行输入描述一个要划分的宝石集合。 每个集合有6个非负整数a1, a2,…, a6...
  • 插入排序思路: 给定一个数组,将数组划分为,已排序未排序两部分,默认第一个元素已排序,然后一次遍历未排序数列,找到每个元素在已排序数列中位置,移动元素,并插入。 平均时间复杂度: O(n^2) 最好情况:...
  •  ArrayList Vector都是使用数组方式存储数据,此数组元素数大于实际存储数据以便增加插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢,...
  • 1993年,由于在C++领域重大贡献,Bjarne获得了ACM该年度 Grace Murray Hopper大奖并成为ACM院士(成立于1947年ACM协会是历史最悠久、目前世界上最大教育科学计算协会,成为ACM院士是个人成就里程碑)。...
  • 1993年,由于在C++领域重大贡献,Bjarne获得了ACM该年度 Grace Murray Hopper大奖并成为ACM院士(成立于1947年ACM协会是历史最悠久、目前世界上最大教育科学计算协会,成为ACM院士是个人成就里程碑)。...
  • C++程序设计语言(特别版)--源代码

    热门讨论 2012-04-23 07:33:51
    1993年,由于在C++领域重大贡献,Bjarne获得了ACM该年度 Grace Murray Hopper大奖并成为ACM院士(成立于1947年ACM协会是历史最悠久、目前世界上最大教育科学计算协会,成为ACM院士是个人成就里程碑)。...
  • C++标准程序库STL.pdf

    千次下载 热门讨论 2013-02-26 11:05:11
    多重集合(multiset) 允许存在个次序相等的元素的集合 栈(stack) 后进先出的值的排列 队列(queue) 先进先出的执的排列 优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列...
  • 在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点前一个或后一个结点(即前件或后件)。 链式存储方式既可用于...
  • java 面试题 总结

    2009-09-16 08:45:34
    ArrayListVector都是使用数组方式存储数据,此数组元素数大于实际存储数据以便增加插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢,Vector...
  • (13) 设一棵完全二叉树共有699个结点,则在该二叉树中叶子结点数(B) 注:利用公式n=n0+n1+n2、n0=n2+1完全二叉数特点可求出 A. 349 B. 350 C. 255 D. 351 (14) 结构化程序设计主要强调是(B) A.程序规模 ...
  • WritePrivateProfileSection 一个初始化文件(.ini)中指定小节设置所有项名值 WritePrivateProfileString 在初始化文件指定小节内设置一个字串 WriteProfileSection Win.ini初始化文件中一个指定小节...

空空如也

空空如也

1 2
收藏数 33
精华内容 13
关键字:

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