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

甘肃省第九建设集团网站搜索引擎优化的内容有哪些

甘肃省第九建设集团网站,搜索引擎优化的内容有哪些,温州市住房和城乡建设委员会网站,商业设计包括什么代码随想录算法训练营第四十三天| 1049. 最后一块石头的重量 II,494. 目标和,474. 一和零 1049. 最后一块石头的重量 II494. 目标和474. 一和零 1049. 最后一块石头的重量 II 题目链接:最后一块石头的重量 II 重点: 本题其实就是…

代码随想录算法训练营第四十三天| 1049. 最后一块石头的重量 II,494. 目标和,474. 一和零

  • 1049. 最后一块石头的重量 II
  • 494. 目标和
  • 474. 一和零

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

题目链接:最后一块石头的重量 II
重点:
本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小
和 416. 分割等和子集比较相似

0-1背包要素:

  • 背包体积:sum//2
  • 物品价值:stones[i]
  • 物品重量:stones[i]
  • 物品可以用一次

动态规划要素:

  • dp[i][j] = [0,i]任选石头在背包容量为j的前提下可以达到的最大体积。
  • 之后的都和经典0-1问题一样
class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:# dp[i][j] = [0,i]任选石头在背包容量为j的前提下可以达到的最大体积。target = sum(stones)//2dp = [[0]*(target+1) for _ in range(len(stones))]# 初始化for j in range(target+1):if stones[0] <= j:dp[0][j] = stones[0]for i in range(1,len(stones)):for j in range(1,(target+1)):if stones[i] > j: # 放不进去,就用i之前的元素dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])#print(dp[-1][-1])return abs(2*dp[-1][-1]-sum(stones))

一维:
dp[j] = 在背包容量为j的前提下可以达到的最大体积。

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:# dp[j] = 任选石头在背包容量为j的前提下可以达到的最大体积。target = sum(stones)//2dp = [0]*(target+1)for i in range(len(stones)):for j in range(target,0,-1):if stones[i] <= j:dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])return abs(2*dp[-1]-sum(stones))

494. 目标和

题目链接:目标和

  • dp[i][j] = [0,i]任选元素可以达到j-t的不同表达数目
  • 由于只能加减,范围是-sum(nums)sum(nums)
  • 初始化:dp的第一行,只有一个元素,所以-i或者i等于j代表的和时,就加一
  • 递推公式:每次多加一个元素可以+nums[i]或者-nums[i],所有如果之前的元素可以组成j-t+nums[i]或者j-t-nums[i]的就可以达到j-t,也就是说在如果在dp下标范围内,dp[i][j]的次数就是j-t+nums[i]的次数加上j-t-nums[i]的次数。
    先不降成一维了,自己都搞不清
class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:# dp[i][j] = [0,i]任选元素可以达到j的不同表达数目t = sum(nums)if target > t or target < -t:return 0dp = [[0]*(2*t+1) for _ in range(len(nums))]for j in range(2*t+1):if nums[0] == j-t:dp[0][j] += 1if -nums[0] == j-t:dp[0][j] += 1for i in range(1,len(nums)):for j in range(2*t+1):#print(j-target-nums[i],j-target+nums[i])if j-t-nums[i] >= -t and j-t+nums[i] <= t:#print(1)dp[i][j] += dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]] elif j-t-nums[i] < -t and j-t+nums[i] <= t:#print(2)dp[i][j] += dp[i-1][j+nums[i]] elif j-t-nums[i] >= -t and j-t+nums[i] > t:#print(3)dp[i][j] += dp[i-1][j-nums[i]]return dp[-1][sum(nums)+target]

474. 一和零

题目链接:一和零
这个背包的重量是两维的需要满足0的数量和1的数量。为了不让dp变成三维的试一下之前的一维累加吧。
dp[i][j] = 拥有最多i个0和j个1的最长子集长度。

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:# dp[i][j] = 最多拥有i个0和j个1的最长子集长度。dp = [[0]*(m+1) for _ in range(n+1)]for i in range(len(strs)):one = strs[i].count('1')zero = strs[i].count('0')for j in range(n,-1,-1):for k in range(m,-1,-1):if one <= j and zero <= k:dp[j][k] = max(dp[j][k],dp[j-one][k-zero]+1)return dp[-1][-1]     
http://www.zhongyajixie.com/news/18271.html

相关文章:

  • 建设人大网站电子商务营销策略有哪些
  • 制作网页时若要使链接目标在新窗口中打开则应用选择seo在线优化工具
  • 网站制作 武汉正规的推文平台
  • 内江手机网站建设优化分析
  • 湖州做网站优化百度广告一天多少钱
  • 网站开发多少钱一天是seo是指搜索引擎优化
  • 中国有没有做的好的网站谷歌浏览器免费入口
  • 企迪网重庆百度推广排名优化
  • 做视频赚钱的国外网站seo网站优化培训怎么做
  • 求一外国h网站html网页完整代码作业
  • 做百度网站要注意什么关键词优化公司网站
  • 网站建设领导小组东莞百度快速优化排名
  • php大型网站开发视频教程西安百度推广公司
  • 淄博企业网站建设价格百度app登录
  • 如何做网站直播入口关键词歌词完整版
  • 软文推广法广州seo托管
  • 深圳网站制作hi0755如何让百度收录自己信息
  • 毕设做网站怎么命题广东公司搜索seo哪家强
  • 新余做网站百度电商推广
  • 本地网站模板修改企业网站策划
  • 西二旗网站建设百度小说搜索风云榜
  • 如何不用域名也可以做网站长沙正规seo优化价格
  • 西安公司网站设计费用抖音seo是什么意思
  • 网站怎么做支付宝支付接口制作网页用什么软件
  • 辽宁 政府网站信息内容建设搜索引擎免费登录入口
  • 不想花钱怎么做网站新产品推广方案策划
  • vs2017 做网站360优化大师官网
  • 好网站分享郑州网站制作选择乐云seo
  • 上海市住房与城乡建设管理委员会网站外链代发软件
  • 做科技申报看什么网站sem是做什么的