找工作准备刷题Day21 动态规划算法 (卡尔41期训练营 8.6)

  1. 上周有些事情回了趟老家,祝广大博友身体健康,多运动。
  2. 前面的贪心算法题目后面慢慢补,近期找到了一个实习,大概持续三个月,现在计划是白天工作,晚上下班以后运动运动+刷题。
  3. 要加强牛客网那种两小时3道题的刷题方式,限时刷题,贴近实际机考。

第一题  01背包问题

卡尔网题目链接:https://kamacoder.com/problempage.php?pid=1046


 

题解

#include <iostream>
#include <vector>
using namespace std;
//  0-1 bag 2D array solution
int bag_01_2DArray()
{int m, bagWeight;cin >> m >> bagWeight;vector<int> weight(m), value(m);for (int i = 0; i < m; i++)cin >> weight[i];for (int i = 0; i < m; i++)cin >> value[i];// initialize// vector<vector<int>> dp(m, vector<int>(bagWeight + 1, 0));vector<int> dp(bagWeight + 1, 0);for (int i = 0; i < m; i++){// when j < weight[i], we do not change the value , so the loop endsfor (int j = bagWeight; j >= weight[i]; j--){dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;return 0;
}//  0-1 bag roll array solution
int bag_01_rollArray()
{int m, bagWeight;cin >> m >> bagWeight;vector<int> weight(m), value(m);for (int i = 0; i < m; i++)cin >> weight[i];for (int i = 0; i < m; i++)cin >> value[i];// initializevector<vector<int>> dp(m, vector<int>(bagWeight + 1, 0));for (int j = weight[0]; j <= bagWeight; j++)dp[0][j] = value[0];for (int i = 1; i < m; i++){for (int j = bagWeight; j >= 0; j--){if (j < weight[i])dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}cout << dp[m - 1][bagWeight] << endl;return 0;
}int main()
{bag_01_rollArray();return 0;
}



第二题:Leetcode416. 分割等和子集

题目描述

解题思路

这个题目可以转换为01背包问题:背包大小为数组和的一半,每份材料的weight和value就是nums元素取值。请问这种情况下,dp[二分之一sum] 是否等于 二分之一sum,如果等于,那么就存在,都则就不存在。

题解

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = accumulate(nums.begin(), nums.end(), 0);if (sum & 1)return false;const int target = sum >> 1;vector<int> dp(target + 1, 0);for (int i = 0; i < nums.size(); i++) {for (int j = target; j >= nums[i]; j--)dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}return dp[target] == target;}
};

第三题:Leetcode238. 除自身以外数组的乘积

题目描述

解题思路

可以使用两个辅助数组,分别记录从左到右的乘积和从右到左的乘积,然后使用前缀积即可。

进一步,可以优化得到空间复杂度为O(1)的方案。

题解

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {if (nums.empty())return {};const int len = nums.size();vector<int> ans(len, 1);for (int i = 1; i < len; i++) {ans[i] = ans[i - 1] * nums[i - 1];}int tmp = 1;for (int i = len - 2; i >= 0; i--) {tmp *= nums[i + 1];ans[i] *= tmp;}return ans;}
};

快排细节梳理

详见第一层 while循环后面的注释

写示例需要考虑多种情况,逆序、重复元素等等。

#include <iostream>
#include <vector>
using namespace std;void quicksort(vector<int> &nums, const int left, const int right)
{if (left >= right)return;int base = nums[left];int l = left, r = right;while (l < r){// 这里和下面,一定有一个地方要带上等于号// 物理意义是:base左边都小于 base值,右边都大于等于base值while (l < r && nums[r] >= base)r--;nums[l] = nums[r];while (l < r && nums[l] < base)l++;nums[r] = nums[l];}nums[l] = base;quicksort(nums, left, l - 1);quicksort(nums, l + 1, right);
}int main()
{// char str[3];// std::cin>>str;std::cout << "hello world" << std::endl;vector<int> a{6, 5, 5, 4, 3, 3, 2, 1, -1, 10};quicksort(a, 0, a.size() - 1);for (auto n : a)cout << n << " ";cout << endl;std::cout << "hello world" << std::endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/393214.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Zero123 论文学习

论文链接&#xff1a;https://arxiv.org/abs/2303.11328 代码链接&#xff1a;https://github.com/cvlab-columbia/zero123 解决了什么问题&#xff1f; 人类通常能够仅凭一个相机视角来想象物体的三维形状和外观。这种能力对于日常任务非常重要&#xff0c;例如物体操纵和在…

Ubuntu distro环境搭建

0 Preface/Foreword 1 环境搭建 1.1 安装make工具 sudo apt install make 1.1.1 查看make版本 1.1.2 查看make使用方法 2 搭建交叉编译工具链 2.1 解压交叉工具链到指定路径 命令解释如下&#xff1a; sudo&#xff0c; 表示使用administrative privilegetar&#xff0c;…

3.达梦数据库基础运维管理

文章目录 前言一、基础数据库管理权限角色管理1.1 DM 系统管理员的类型1.2 角色责则分类 DM 数据库2.1 数据库评估2.2 状态和模式 参考内容 前言 本篇博客为上一篇博客的进阶版&#xff0c;主要针对常规达梦数据库的基本管理上面 一、基础数据库管理 权限角色管理 1.1 DM 系…

母带混音插件-Musik Hack Master Plan 1.59 WiN-MAC,长期更新持续有效

Musik Hack Master Plan 1.59 WiN-MAC 一款专业的音频母带制作流程&#xff0c;只需简单的控制就能制作出适合发布的母带&#xff1a; 水晶般清晰的响度、丰富的模拟饱和度、相位一致的成像、物理磁带模拟&#xff0c;以及修复和监听混音的额外工具。 一。Musik Hack Master P…

ViT算法解读——Transformer在分类任务中的应用

论文&#xff1a;An image is worth 16x16 words: Transformers for image recognition at scale 作者&#xff1a;Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg…

Golang | Leetcode Golang题解之第322题零钱兑换

题目&#xff1a; 题解&#xff1a; func coinChange(coins []int, amount int) int {var (dfs func(x int) int // x金额 最少硬币个数memo make(map[int]int) // 记忆化)dfs func(x int) int {//边界if x 0 {return 0} else if x < 0 {return math.MaxInt32}//记…

有限元和稀疏矩阵

对于大规模的有限元计算&#xff0c;系统的整体刚度矩阵是非常耗费内存的&#xff0c;以百万自由度为例&#xff0c;刚度矩阵K的大小为100万x100万&#xff0c;元素大小为双精度double&#xff0c;占用8 byte&#xff0c;那么K占用的内存为100万x100万x8 byte 8000G&#xff0…

盘点4款令人惊艳的视频剪辑工具

在这个短视频盛行的时代&#xff0c;每个人都可以成为视频内容的创作者。但是&#xff0c;在此之前&#xff0c;拥有一款适合自己的剪辑软件十分重要。今天我就来和大家来说一说我自己觉得比较好用的4款剪辑软件。 1、福昕剪辑神器 直达链接&#xff1a;www.pdf365.cn/foxit-c…

【验证码逆向专栏】某安登录流程详解与验证码逆向分析与识别

声明 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;不提供完整代码&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 本文章未…

DedeCMS-V5.7.82-UTF8织梦管理系统漏洞

将靶场环境放到www目录下——访问/dedecms/uploads 安装程序 - 织梦内容管理系统 V5.7 UTF8SP2 同意协议——继续 继续 配置后——点击继续 进入后台 登录后台——填写用户名密码。 方法一&#xff1a;上传shell文件 后台——核心——附件管理——上传新文件。 访问/dedecms…

接口测试之python+rquest+unittest分层自动化框架

接口测试之接口po框架 一、新建一个项目 接口自动化框架设计实战&#xff1a; 第一包&#xff1a;config 案例&#xff1a; #登录接口 dl_url http://cms.duoceshi.cn/cms/manage/loginJump.do dl_d {userAccount: admin, loginPwd: 123456} dl_h "Content-Type:app…

若依分离版本部署流程—开启HTTPS访问。

目录 前言 一、申请证书 二、后端打包 三、前端打包 四、服务器部署 ① Redis启动 ② 运行Jar包 ③ 上传ssl证书到服务器 ④ Nginx配置前端部分 五、访问 前言 在若依分离版本的项目部署过程中&#xff0c;跟大多数前后端分离项目差不多&#xff0c;都是前后端分别打包到服…

鸿蒙(API 12 Beta2版)媒体开发【使用AudioRenderer开发音频播放功能】

音频播放开发概述 如何选择音频播放开发方式 系统提供了多样化的API&#xff0c;来帮助开发者完成音频播放的开发&#xff0c;不同的API适用于不同音频数据格式、音频资源来源、音频使用场景&#xff0c;甚至是不同开发语言。因此&#xff0c;选择合适的音频播放API&#xff…

Linux学习笔记:iptables命令管理

1、iptables简介 其实iptables只是Linux防火墙的管理工具而已&#xff0c;位于/sbin/iptables。真正实现防火墙功能的是netfilter&#xff0c;它是Linux内核中实现包过滤的内部结构。 语法格式&#xff1a;iptables [-t table] COMMAND [chain] CRETIRIA -j ACTION -t&#…

xss漏洞(五,xss-labs靶场搭建及简单讲解)

本文仅作为学习参考使用&#xff0c;本文作者对任何使用本文进行渗透攻击破坏不负任何责任。 前言&#xff1a; 本文基于github上的xss-labs靶场以及PHP study进行操作。 一&#xff0c;靶场环境搭建。 1, 下载并解压到phpstudy的www目录下。 同前文一致&#xff0c;将文件…

精准防控,高效管理:AI智能分析网关V4区域未停留检测算法的介绍及应用

一、区域未停留AI检测算法概述 随着人工智能和计算机视觉技术的飞速发展&#xff0c;区域未停留AI检测算法作为一种重要的视频分析技术&#xff0c;逐渐在各个领域得到广泛应用。该算法通过高效处理视频流数据&#xff0c;能够实时分析并判断目标对象是否在预设区域内有足够的…

PSTNET阅读

ICLR2021 点云序列在空间维度上具有不规则性和无序性&#xff0c;但在时间维度上具有规律性和有序性。 现有的基于网格的卷积不能直接应用于原始点云序列的时空建模。 在时空序列下&#xff0c;基于网格和基于点的卷积对比。 创新点 1.首次尝试在原始点云序列建模中分解空间…

【Java 第九篇章】多线程实际工作中的头大的模块

多线程是一种编程概念&#xff0c;它允许多个执行路径&#xff08;线程&#xff09;在同一进程内并发运行。 一、多线程的概念和作用 1、概念 线程是程序执行的最小单元&#xff0c;一个进程可以包含多个线程。每个线程都有自己的程序计数器、栈和局部变量&#xff0c;但它们…

Python获取Excel内容

Python获取Excel内容 目录 Python获取Excel内容1.读取Excel并登陆2.下载Excel中图片 数据存储到列表3.上传到接口 需求&#xff1a;获取xlsx files目录下的所有Excel信息&#xff0c;并将数据打包成字典格式上传到接口 示例数据&#xff1a; 1.读取Excel并登陆 import os impo…

【算法】贪心算法

应用场景——集合覆盖问题 假设存在下面需要付费的广播台&#xff0c;以及广播台信号可以覆盖的地区。如何选择最少的广播台&#xff0c;让所有的地区都可以接收到信号 贪心算法介绍 1.贪心算法是指在对问题进行求解时&#xff0c;在每一步选择中都采取最好或者最优的选择 2…