当前位置: 首页 > news >正文

做网站和优化共多少钱百度快照推广是什么意思

做网站和优化共多少钱,百度快照推广是什么意思,北京微网站制作,网络营销与推广的概念问题背景 给你一个 只包含正整数 的 非空 数组 n u m s nums nums。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 数据约束 1 ≤ n u m s . l e n g t h ≤ 200 1 \le nums.length \le 200 1≤nums.length≤200 1 ≤ n u m s [ i ] ≤ …

问题背景

给你一个 只包含正整数非空 数组 n u m s nums nums。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

数据约束

  • 1 ≤ n u m s . l e n g t h ≤ 200 1 \le nums.length \le 200 1nums.length200
  • 1 ≤ n u m s [ i ] ≤ 100 1 \le nums[i] \le 100 1nums[i]100

解题过程

要求分成两个子集且和相等,其实就是找到一个总和为 s u m / 2 sum / 2 sum/2 的子集,其中 s u m sum sum 表示整个集合的和。需要注意的是, s u m sum sum 必须是偶数。
此外,和为零是一种可能的状态,所以记忆化数组中的元素要初始化为 − 1 -1 1
递归入口 是 d f s ( n − 1 , s u m / 2 ) dfs(n - 1, sum / 2) dfs(n1,sum/2),表示在 [ 0 , n − 1 ] [0, n - 1] [0,n1] 的范围上找到一个和为 s u m / 2 sum / 2 sum/2 的子集。
递归边界 是 d f s ( − 1 , 0 ) = t r u e dfs(-1, 0) = true dfs(1,0)=true,表示枚举完了整个集合中的所有元素,最终能够使得剩余目标和减少到零。

翻译成递推时要注意,数组下标不能为 − 1 -1 1,所以要进行转移,将结果映射到 [ 1 , n ] [1, n] [1,n] 这个范围上。

具体实现

递归

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if ((sum & 1) == 1) {return false;}int n = nums.length;int[][] memo = new int[n][(sum >> 1) + 1];for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(n - 1, sum >> 1, nums, memo);}private boolean dfs(int i, int j, int[] nums, int[][] memo) {if (i < 0) {return j == 0;}if (memo[i][j] != -1) {return memo[i][j] == 1;}boolean res = j >= nums[i] && dfs(i - 1, j - nums[i], nums, memo) || dfs(i - 1, j, nums, memo);memo[i][j] = res ? 1 : 0;return res;}
}

递推

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if ((sum & 1) == 1) {return false;}sum /= 2;int n = nums.length;boolean[][] dp = new boolean[n + 1][sum + 1];dp[0][0] = true;for (int i = 0; i < n; i++) {int cur = nums[i];for (int j = 0; j <= sum; j++) {dp[i + 1][j] = j >= cur && dp[i][j - cur] || dp[i][j];}}return dp[n][sum];}
}

空间优化

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if ((sum & 1) == 1) {return false;}sum /= 2;int n = nums.length;boolean[] dp = new boolean[sum + 1];dp[0] = true;// minSum 表示前 i 个数和的上界,不可能超过所有这些数的总和int minSum = 0;for (int num : nums) {// 用这个值来初始化内层循环可以避免许多不必要的判断,想不清楚的话直接用 sum 也可以minSum = Math.min(minSum + num, sum);for (int j = minSum; j >= num; j--) {dp[j] = dp[j] || dp[j - num];}if (dp[sum]) {return true;}}return false;}
}
http://www.15wanjia.com/news/10304.html

相关文章:

  • 移动端网站开发流程自媒体人专用网站
  • 台州公司网站建设做seo必须有网站吗
  • 如何直到网站是用什么模板做的关键词优化软件
  • 如何做网站逻辑结构图登封网络推广
  • 网站建设需要学习什么电商运营主要工作内容
  • j2ee做的网站百度问一问付费咨询
  • 做公司网站要那些资料在线工具seo
  • 苹果网站上物体阴影怎么做的网站推广建设
  • 在网站做专题百度搜索工具
  • 怒江网站制作百度站长工具
  • 做汉字词卡的网站app开发工具
  • 加强网站建设的爱站网站排行榜
  • 企业网站开发douyanet外贸网站哪个比较好
  • 代理行业门户网站百度新版本更新下载
  • dw做网站图片运用seo专业培训班
  • 县政府网站建设情况汇报seo推广教程seo高级教程
  • 有什么平面设计的网站余姚关键词优化公司
  • 做软件网站成人电脑培训班附近有吗
  • b2b网站建设方案长沙专业搜索引擎seo公司
  • 连锁店管理网站开发怎么做好推广和营销
  • 专门教人做点心的网站巨量广告投放平台
  • 济南市建设委员会官方网站张雷明履新河南省委常委
  • 网站制作培训班台州网站建设方案推广
  • 淄博网站制作价格低bt磁力猫
  • 江西建设工程信息网站北京疫情最新新闻
  • 服装电子商务网站有哪些济南优化网站关键词
  • 怎样做电子商务网站百度关键词优化排名技巧
  • 网站项目建设周期沈阳网站建设制作公司
  • 怎样做网站的源代码seo优化官网
  • 换空间网站备案吗seo指搜索引擎