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

奎文建设局网站推广之家官网

奎文建设局网站,推广之家官网,化学商城网站建设,不允许网站建设协议1、不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 感悟:通过举例推导,n1,只有一颗二叉搜索树;n2&#xff0c…

1、不同的二叉搜索树

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

感悟:通过举例推导,n=1,只有一颗二叉搜索树;n=2,有两颗;n=3,有5颗,且可以看出,是在n=2的前提上演变过来的。得出递归公式:dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量],即:dp[i] += dp[j - 1] * dp[i - j];

class Solution {public int numTrees(int n) {int[] dp = new int[n+1];dp[0] = 1;//dp[1] = 1;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i] += dp[j-1]*dp[i-j];}}return dp[n];}
}

2、分割等和子集

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

感悟:典型的0-1背包问题,数组元素的和是固定的,所以背包容量是sum/2,看是否有能刚好装满背包的元素。0-1背包问题的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);当dp[target]=target时,表示找到了能装满背包的元素。

注意:动态数组使用一维数组时,第二层循环需要倒序,不然可能会把某个元素放入多次;

class Solution {public boolean canPartition(int[] nums) {int target = 0;for(int n :nums){target += n;}if(target % 2 >0) return false;int m = target/2;int[] dp = new int[m+1];for(int i=0;i<nums.length-1;i++){for(int j=m;j>0 && j>=nums[i];j--){dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}return dp[m] == m;}
}

3、最后一块石头的重量II

有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

  • 如果 x == y,那么两块石头都会被完全粉碎;
  • 如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x

最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0

感悟:和上题类似,当两块石头尽可能接近时,可以获得最小的重量。

class Solution {public int lastStoneWeightII(int[] stones) {if(stones == null || stones.length == 0) return 0;int len = stones.length;int sum = 0;for(int n : stones){sum += n;}int m = sum/2;int[] dp = new int[m+1];for(int i=0;i<len;i++){for(int j=m;j>=stones[i];j--){dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum-2*dp[m];}
}

4、目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :

  • 例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

感悟:整个数组分成left、right两部分,left+right=sum,left-right=target,所以left = (sum+target)/2,又转化为0-1背包问题了。用二维数组时,能更清晰的推导出转移方程。

归纳总结如下:

  • 不放物品i:即背包容量为j,里面不放物品i,装满有dp[i - 1][j]中方法。

  • 放物品i: 即:先空出物品i的容量,背包容量为(j - 物品i容量),放满背包有 dp[i - 1][j - 物品i容量] 种方法。

本题中,物品i的容量是nums[i],价值也是nums[i]。

递推公式:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;int len = nums.length;for(int n : nums){sum += n;}if((sum+target)%2 == 1) return 0;if((sum+target) < 0) return 0;int left = (sum+target)/2;int[] dp = new int[left+1];dp[0] = 1;for(int i=0;i<len;i++){for(int j=left;j>=nums[i];j--){dp[j] += dp[j-nums[i]];}}return dp[left];}
}

5、一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

感悟:本题稍有点特殊,背包有两个维度,0和1分别是一个维度。递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

class Solution {public int findMaxForm(String[] strs, int m, int n) {if(strs.length == 0) return 0;int[][] dp = new int[m+1][n+1];for(String s:strs){int zeroNum = 0,oneNum = 0;for(char c:s.toCharArray()){if(c == '0'){zeroNum++;}else{oneNum++;}}for(int i=m;i>=zeroNum;i--){for(int j=n;j>=oneNum;j--){dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}return dp[m][n];}
}

总结:0-1背包问题,当递推公式不好直接看出来时,可以先尝试使用二维数组去推理。

0-1背包的递推公式推理过程抽象化如下:

  • 不放物品i:背包容量为j,里面不放物品i的最大价值是dp[i - 1][j]。

  • 放物品i:背包空出物品i的容量后,背包容量为j - weight[i],dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

http://www.cadmedia.cn/news/7030.html

相关文章:

  • 福永网站推广灰色词快速排名接单
  • wordpress vps建站app运营
  • 网站搭建上门多少钱成功的营销案例及分析
  • 南京哪家网站做的好优秀网站网页设计图片
  • 建设网站备案与不备案区别网址服务器查询
  • 男女之间做那个事情很污的网站浙江专业网站seo
  • 东莞本地的发布平台二十条优化
  • 收录网站是什么意思站长素材网站官网
  • 西安疫情吉林seo推广
  • 职业教育网站建设可行性报告台湾永久免费加密一
  • 应用公园是收费还是免费的seo优化网络
  • 百度对网站建设公司全网营销策划公司
  • 网站建设和优化要求seo推广软件哪个好
  • 企业网站springboot武汉大学人民医院东院
  • 小红书推广营销网站seo博客
  • 商务之家网福建seo快速排名优化
  • 天津网站排名优化外贸营销网站制作
  • 网站建设网页设计培训班怎么制作网站教程步骤
  • 自己想做个网站需要多少钱优化网站seo公司
  • 芜湖网站建设推广公司搜索引擎优化是什么?
  • seo做论坛和企业网站差别百度自动点击器怎么用
  • 宁波网站推广运营公司网上推销产品的软件
  • 给我一个网站电工培训内容
  • 广州建网站开发seo型企业网站seo排名优化软件有用吗
  • 旅行社网站规划与建设如何在网上做销售推广
  • 系统开发工具有哪些长沙seo优化价格
  • 淘客推广佣金广安seo外包
  • 网站开发遇到的难题解决seo优化排名工具
  • 江西专业的网站建设制作sem和seo是什么
  • 专业做红木家具网站网络推广员是干什么的