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

建立企业网站的形式有哪几种网站优化什么意思

建立企业网站的形式有哪几种,网站优化什么意思,web前端界面设计工具,wordpress百度分享插件下载刷题记录 1049. 最后一块石头的重量 II*494. 目标和二维数组滚动数组 *474. 一和零 1049. 最后一块石头的重量 II leetcode题目地址 本题与416. 分割等和子集类似。依旧是01背包问题,本题尽可能将石头分为相等(相近)的两堆,然后…

刷题记录

  • 1049. 最后一块石头的重量 II
  • *494. 目标和
    • 二维数组
    • 滚动数组
  • *474. 一和零

1049. 最后一块石头的重量 II

leetcode题目地址

本题与416. 分割等和子集类似。依旧是01背包问题,本题尽可能将石头分为相等(相近)的两堆,然后两堆求差取绝对值既可。dp[j]表示背包容量为j时背包中物品的最大重量。

时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n ) O(n) O(n)

// java
class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for(int i=0; i<stones.length; i++){sum += stones[i];}int target = sum / 2;int[] dp = new int[target+1];for(int i=0; i<stones.length; i++){for(int j=target; j>=stones[i]; j--){dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);}}return Math.abs(sum-dp[target]*2);}
}

*494. 目标和

leetcode题目地址

二维数组

首先对所有数字求和得到sum。

设添加‘+’的数字和为x,则添加‘-’的数字之和为sum-x,则有:target = x - ( sum - x ).

则,x = ( target + sum ) / 2. 这样就将问题简化为求能够组合(添加‘+’)成 x 的数字和的方案数。

当上式中的除以2无法整除时,说明当前数组无法组合出target的方案,返回0.

要求组合成x的方案数,则将x作为背包容量。

dp[i][j]记录背包容量为 j 时,使用 0-i 的物品可以(恰好)装满背包的方案数。

当 j=0 时,即背包容量为0,若 0-i 中没有0,则只有1种方案就是不放物品;若 0-i 中有 k 个 0,则方案数为 2 ^ k(这里的来由是:每一个0都有2个状态,即选或不选,因此k个0就有 2 ^ k种组合) ;

当 i=0 时,即只使用第0个物品,只有 j == nums[0] 时的方案为1。

  • 当访问到物品i时,若背包容量 j 可以放下当前物品 nums[i],则当前物品有两种状态,即选或不选。
    • 选:背包需要腾出当前物品大小的空间来存放当前物品,即dp[i-1][j-nums[i]]
    • 不选:dp[i-1][j]
      则有:dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j]
  • 若背包容量 j 放不下当前物品 nums[i], 则dp[i][j] = dp[i-1][j].

时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n 2 ) O(n^2) O(n2)

// java
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i=0; i<nums.length; i++){sum += nums[i];}if(Math.abs(target)>sum) return 0;if((sum+target)%2==1) return 0;int x = (sum+target)/2;int[][] dp = new int[nums.length][x+1];if(nums[0]<=x) dp[0][nums[0]] = 1;int zeroCnt = 0;for(int i=0; i<nums.length; i++){if(nums[i] == 0){zeroCnt++;}dp[i][0] = (int)Math.pow(2, zeroCnt);}for(int i=1; i<nums.length; i++){for(int j=0; j<=x; j++){if(j>=nums[i]){dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];}else{dp[i][j] = dp[i-1][j];}}}return dp[nums.length-1][x];}
}

滚动数组

思路同上,只是有一些小细节需要处理:

  • 所有元素都只使用一次,因此遍历背包容量需要从后向前。
  • 在初始化第一个元素即dp[0]时,需要注意,若nums[0]为0,则有2种方案(选或不选),反之只有一种方案(不选)。

时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n ) O(n) O(n)

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

*474. 一和零

leetcode题目地址

本题是一个二维的01背包问题,背包容量是两个维度,这里使用的是滚动数组思想(二维),若要用普通的dp算法则需要使用三维数组。

dp[i][j] 代表至多 i 个 0,j 个 1 的子集个数。

由于是子集个数,不同于上题的方案数, 因此这里在留出当前物品空间后需要加1.
由于是滚动数组,则在更新时需要与当前值求最大值保留。

即:dp[i][j] = max(dp[i][j], dp[i-zeroCnt][j-oneCnt]+1).

时间复杂度: O ( n 3 ) O(n^3) O(n3) -> O ( k m n ) O(kmn) O(kmn)
空间复杂度: O ( n 2 ) O(n^2) O(n2) -> O ( m n ) O(mn) O(mn)

// java
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];for(int k=0; k<strs.length; k++){int zeroCnt = 0, oneCnt = 0;char[] arr = strs[k].toCharArray();// 统计当前字符串中的0、1个数for(int j=0; j<arr.length; j++){if(arr[j] == '0') zeroCnt++;else oneCnt++;}// 01背包for(int i=m; i>=zeroCnt; i--){for(int j=n; j>=oneCnt; j--){dp[i][j] = Math.max(dp[i][j], dp[i-zeroCnt][j-oneCnt]+1);}}}return dp[m][n];}
}
http://www.15wanjia.com/news/55491.html

相关文章:

  • 课程设计报告 网站开发app推广方式
  • 重庆网站设计找重庆最佳科技世界新闻最新消息
  • 龙湖什么网站做宣传seo实战密码第四版
  • 分销平台官网seo技术公司
  • 做网站 免费字体seo自动排名软件
  • asp网站图片网络营销促销策略有哪些
  • 国内做新闻比较好的网站直通车关键词优化
  • 黄冈市住房和城乡建设厅网站搜狗站长
  • 织梦 手机网站搜索引擎网站入口
  • wordpress 3.8 漏洞seo关键词大搜
  • 贵州网站建设公司推荐一个企业seo网站的优化流程
  • 互联网最好的公司seo软件推荐
  • 河南做网站企起谷歌优化师
  • 好游快游app官方网站下载在线观看的seo综合查询
  • win7在局域网做网站百度 指数
  • 网站做双拼域名什么意思百度网站提交收录入口
  • 思源黑体可以做网站app拉新渠道
  • 做网站有什么软件吗关键词优化骗局
  • 电脑做的本地网站手机看爱站工具包的模块有哪些
  • 营销型网站建设费用怎么这么大新闻头条最新消息国家大事
  • 公考在哪个网站上做试题百度推广登陆平台登录
  • 网站开发有哪些参考文献seo快速排名上首页
  • 拼团做的比较好的网站网址怎么推广
  • 查排名的网站怎么去营销自己的产品
  • 做网站学哪方面知识海外推广平台有哪些?
  • 如何创建网站软件制作平台
  • 做网站如何站长之家的作用
  • 详情页面设计网站优化入门免费教程
  • 网站开发流程规范淘宝推广方式
  • 淘宝作图在哪个网站上做图百度识图扫一扫入口