算法训练营第43天|LeetCode 1049.最后一块石头的重量Ⅱ 494.目标和 474.一和零

news/2025/3/14 22:10:15/

LeetCode 1049.最后一块石头的重量Ⅱ

题目链接:

LeetCode 1049.最后一块石头的重量Ⅱ

代码:

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;int size = stones.size();for(int i=0;i<size;i++){sum += stones[i];}int target = sum/2;vector<int>dp(3010,0);for(int i = 0;i<size;i++){for(int j=target;j>=stones[i];j--){dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);}}int temp = sum-dp[target];return abs(temp-dp[target]);}
};

LeetCode 494.目标和

题目链接:

LeetCode 494.目标和

代码:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int size = nums.size();int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int temp = (sum+target)/2;vector<int>dp(temp+1,0);dp[0]=1;for (int i = 0; i < nums.size(); i++) {for (int j = temp; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[temp];}
};

LeetCode 474.一和零

题目链接:

LeetCode 474.一和零

代码:

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>dp(m+1,vector<int>(n+1,0));for(string str:strs){int x=0,y=0;for(char ch:str){if(ch=='1')y++;if(ch=='0')x++;}for(int i=m;i>=x;i--){for(int j=n;j>=y;j--){dp[i][j] = max(dp[i-x][j-y]+1,dp[i][j]);}}}return dp[m][n];}
};

 


http://www.ppmy.cn/news/1426831.html

相关文章

Apache Doris 2.1.2 版本正式发布!

亲爱的社区小伙伴们&#xff0c;Apache Doris 2.1.2 版本已于 2024 年 4 月 12 日正式发布。该版本提交了若干改进项以及问题修复&#xff0c;进一步提升了系统的性能及稳定性&#xff0c;欢迎大家下载体验。 官网下载页&#xff1a;https://doris.apache.org/download/ GitH…

机器学习实验------决策树

第1关&#xff1a;什么是决策树 任务描述 本关任务&#xff1a;根据本节课所学知识完成本关所设置的选择题。 第2关&#xff1a;信息熵与信息增益 任务描述 本关任务&#xff1a;掌握什么是信息增益&#xff0c;完成计算信息增益的程序设计。 import numpy as npdef calcIn…

Rust入门-Hello World

1、安装 在 Linux 或 macOS 上安装 rustup 打开终端并输入下面命令&#xff1a; $ curl --proto https --tlsv1.2 https://sh.rustup.rs -sSf | sh如果安装成功&#xff0c;将出现下面这行&#xff1a; Rust is installed now. Great!2、更新 $ rustup self uninstall3、卸…

视频怎么去水印,轻松去视频水印的方法

视频水印是为了提高视频的版权保护能力&#xff0c;防止视频被盗用或者不正当使用&#xff0c;但另一方面会破坏视频的流畅度和清晰度&#xff0c;很影响视觉观感和后续创作。想要去除视频水印&#xff0c;下面三种方法你必须得知道&#xff0c;赶紧看过来~ 1、使用美图秀秀(A…

5G网络开通与调测ipv4

要求如下&#xff1a; 1. 勘站规划 1. 【重】首先观察NR频点&#xff0c;完成设备选型 2645--选择N41 3455--选择N78 4725--选择N79 设备选型如下&#xff1a;观察AAU的通道数&#xff0c;最大发射功率&#xff1b;选择N41的选型频段也要选41 2. …

STL--list双向链表

功能 将数据进行链式存储 链表&#xff08;list&#xff09;是一种物理存储单元上非连续的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接实现的 链表的组成&#xff1a;链表由一系列结点组成 结点的组成&#xff1a;一个是存储数据元素的数据域&#xff0…

设计模式学习笔记 - 开源实战二(下):从Unix开源开发学习应对大型复杂项目开发

概述 前两骗文章&#xff0c;分别从代码编写、研发管理的角度&#xff0c;探讨了如何应对大型复杂软件开发。在研发管理这一部分&#xff0c;又讲到了比较重要的几点&#xff0c;它们分别是编码规范、单元测试、持续重构和 Code Review。其中&#xff0c;前三点在前面的文章中…

Power BI报告在PPT中实时刷新的实现技巧分享

前面我们刚介绍了如何在PPT中展示Power BI报告&#xff1f; 很巧的是&#xff0c;在刚刚的Power BI 2024年4月更新的诸多新特性中&#xff0c;PPT中使用的Power BI插件又有新特性的更新&#xff0c;数据自动刷新功能(新特性仅限国际版使用)&#xff0c;这个新特性支持最低15秒…