给定一个只包含正整数的数组 nums ,请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。 数据范围: , 数组中的元素满足-笔试面试资料

这是qklbishe.com第18919 篇笔试面试资料
提供答案分析,通过本文《给定一个只包含正整数的数组 nums ,请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。
数据范围: , 数组中的元素满足-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个只包含正整数的数组 nums ,请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。
数据范围: 给定一个只包含正整数的数组 nums ,请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。          数据范围:  , 数组中的元素满足 , 数组中的元素满足 给定一个只包含正整数的数组 nums ,请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。          数据范围:  , 数组中的元素满足
Java

给定一个只包含正整数的数组 nums ,请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。          数据范围:  , 数组中的元素满足 零葬

暴力递归

首先从左往右进行尝试,写出暴力递归版本。
  1. rest<0时,表示本次凑数方案失败;
  2. rest=0时,刚好凑齐,本次凑数方案是成功的;
  3. 否则看本轮取哪个数nums[i],下一轮需要凑rest-nums[i]
private boolean recurrent(int[] nums, int depth, int rest) {     if(rest < 0) return false;     if(rest == 0) return true;    // base case     for(int i = depth; i < nums.length; i++){         if(recurrent(nums, i, rest - nums[i])) return true;     }     return false; }

动态规划 

递归函数有depthrest两个可变参数,因此本质上是个二维动态规划问题。根据递归的逻辑,就可以改成动态规划版本,递归中的函数调用就是动态规划中从dp数组中取值。
我们可以看,在计算dp[i][rest]时,需要依赖左边的值,因此动态规划填表的顺序:从上往下(从下往上也可以,这个顺序无所谓的情况下还可以进行空间压缩的优化)从左往右。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param nums int整型一维数组       * @return bool布尔型      */     public boolean partition (int[] nums) {         // write code here         int sum = 0;         for(int i = 0; i < nums.length; i++){             sum += nums[i];         }         // 无法均分         if(sum % 2 != 0){             return false;         }         int target = sum / 2;         boolean[][] dp = new boolean[nums.length][target + 1];         for(int i = 0; i < nums.length; i++){             dp[i][0] = true;    // base case         }         for(int i = 0; i < nums.length; i++){             for(int rest = nums[i]; rest <= target; rest++){                 dp[i][rest] |= dp[i][rest - nums[i]];             }         }         return dp[0][target];     } }

今天 21:34:49 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个只包含正整数的数组 nums ,请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。 数据范围: , 数组中的元素满足-笔试面试资料

提供最优质的资源集合

立即查看 了解详情