C/C++ 动态规划面试算法题
1.买卖股票的最佳时机
https://blog.csdn.net/qq_41277628/article/details/113322136
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
1 #include <stdio.h>2 3 #define N 64 5 int main()6 {7 int min,temp;8 int a[] = {7,1,5,3,6,4};9 min = a[0];
10 temp = 0;
11 for(int i = 0;i<N;i++)
12 {
13 if(a[i] < min)
14 {
15 min = a[i];
16 }
17 else if((a[i]-min)>temp)
18 {
19 temp = a[i] - min;
20 }
21 }
22 printf("最高收益为%d元\n",temp);
23
24 return 0;
25 }
2.盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
https://violentayang.blog.csdn.net/article/details/123061036
1 #include <stdio.h>2 #include <string.h>3 4 #define N 95 6 int main() 7 {8 int a[N] = {1,8,6,2,5,4,8,3,7};9 int i = 0,j = N-1,sun = 0,top = 0;
10 while(i<j)
11 {
12 if(a[i]<a[j])
13 {
14 sun = (j-i)*a[i];
15 if(sun>top)
16 {
17 top = sun;
18 }
19 i++;
20 }
21 else
22 {
23 sun = (j-i)*a[j];
24 if(sun>top)
25 {
26 top = sun;
27 }
28 j--;
29 }
30 }
31 printf("可以盛%d吨的水\n",top);
32
33 return 0;
34 }
c++实现:
1 #include<iostream>2 #include<vector>3 using namespace std;4 5 class node{6 public:7 int maxsrea(vector<int>& height){8 int ans = 0;9 int l = 0,r = height.size()-1;
10 while(l<r){
11 ans = max(ans,min(height[l],height[r]) * (r-l));
12 if(height[l] < height[r]) l++;
13 else r--;
14 }
15 return ans;
16 }
17 };
18
19 int main()
20 {
21 node n;
22 vector<int> height = {1,8,6,2,5,4,8,3,7};
23 cout << n.maxsrea(height) << endl;
24
25 return 0;
26 }
3.不同路径
一个机器人位于一个 m x n 网格的左上角 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
问总共有多少条不同的路径?
https://blog.csdn.net/C_chengxuyuan/article/details/119980859
1 #include <stdio.h>2 #include <string.h>3 4 int main() 5 {6 int x,y;7 int a[100][100];8 printf("输入网格的长和宽\n");9 scanf("%d%d",&x,&y);
10
11 for(int i = 0;i<x;i++)
12 {
13 a[i][0] = 1;
14 }
15
16 for(int j = 0;j<y;j++)
17 {
18 a[0][j] = 1;
19 }
20
21 for(int i = 1;i<x;i++)
22 {
23 for(int j = 1;j<y;j++)
24 {
25 a[i][j] = a[i-1][j] + a[i][j-1];
26 }
27 }
28
29 printf("长和宽为%d,%d的网格,总共有%d条不同的路径\n",x,y,a[x-1][y-1]);
30
31 return 0;
32 }
c++实现:
1 #include <iostream>2 #include <vector>3 using namespace std;4 5 class node{6 public:7 int uniquePath(int m,int n){8 vector<vector<int>> f(m,vector<int>(n,1));9 for(int i = 1;i<m;i++){
10 for(int j = 1;j<n;j++){
11 f[i][j] = f[i-1][j] + f[i][j-1];
12 }
13 }
14 return f[m-1][n-1];
15 }
16 };
17
18 int main()
19 {
20 int y = 3,x = 7;
21 node n;
22 cout << "长为7,宽为3的网格从左上角到右下角的路径有:" << n.uniquePath(x,y);
23
24 return 0;
25 }
不同路径中间有障碍物(力扣第63题)
1 #include <iostream>2 #include <vector>3 using namespace std;4 5 class node{6 public:7 int unique(vector<vector<int>>& o){8 int m = o.size(),n = o[0].size();9 vector<vector<int>> f(m,vector<int>(n));
10 for(int i = 0;i<m;i++){
11 for(int j = 0;j<n;j++){
12 if(o[i][j] == 1) continue;
13 if(!i&&!j) f[i][j] = 1;
14 else{
15 if(i) f[i][j] += f[i-1][j];
16 if(j) f[i][j] += f[i][j-1];
17 }
18 }
19 }
20 return f[m-1][n-1];
21 }
22 };
23
24 int main()
25 {
26 node n;
27 vector<vector<int>> cur;
28 cur.push_back({0,0,0});
29 cur.push_back({0,1,0});
30 cur.push_back({0,0,0});
31 cout << n.unique(cur) << endl;
32
33 return 0;
34 }
4.最小路径和
一个机器人位于一个 m x n 网格的左上角 ,m x n的网格中分布着不同的数字
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,找出路径的最小和。
1 #include <stdio.h>2 #include <string.h>3 4 #define N 35 #define M 36 7 int main() 8 {9 int a[N][M] = {{1,3,1},{1,5,1},{4,2,1}};
10 int b[100][100];
11
12 b[0][0] = a[0][0];
13
14 for(int i = 1;i<N;i++)
15 {
16 b[i][0] = b[i-1][0] + a[i][0];
17 }
18
19 for(int j = 1;j<M;j++)
20 {
21 b[0][j] = b[0][j-1] + a[0][j];
22 }
23
24 for(int i = 1;i<N;i++)
25 {
26 for(int j = 1;j<N;j++)
27 {
28 b[i][j] = (b[i-1][j] > b[i][j-1] ? b[i][j-1]:b[i-1][j])+a[i][j];
29 }
30 }
31
32 printf("长和宽为%d,%d的网格,最小路径和为%d\n",N,M,b[N-1][M-1]);
33
34 return 0;
35 }
5.最长上升子序列
一个数的序列bi,当b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN),我们可以得到一些上升的子序列(ai1,ai2,...,aiK),
这里1≤i1 < i2 < ... < iK≤N。比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。这些子序列中最长的长度是4,比如子序列(1,3,5,8)。
你的任务,就是对于给定的序列,求出最长上升子序列的长度。
1 #include <stdio.h>2 #include <string.h>3 4 #define N 75 6 int main() 7 {8 int max = 0;9 int a[N],dp[N];
10 printf("输入一个数组\n");
11 for(int i = 1;i<=N;i++)
12 {
13 scanf("%d",&a[i]);
14 }
15
16 for(int i = 0;i<N;i++)
17 {
18 dp[i] = 1;
19 }
20
21 for(int i = 1;i<=N;i++)
22 {
23 for(int j = i-1;j>0;j--)
24 {
25 if(a[i]>a[j]&&dp[j]>=dp[i])
26 {
27 dp[i] = dp[j]+1;
28 if(dp[i]>max)
29 {
30 max = dp[i];
31 }
32 }
33 }
34 }
35 printf("最长上升子序列的长度为%d\n",max);
36
37 return 0;
38 }
6.最接近的三数之和(力扣16题)
1 #include <iostream>2 #include <vector>3 #include<algorithm>4 using namespace std;5 6 class node{7 public:8 int threesun(vector<int>& nums,int target){9 int ans = nums[0] + nums[1] + nums[2];
10 sort(nums.begin(),nums.end());
11 for(int i = 0;i<nums.size();i++){
12 int l = i + 1,r = nums.size() - 1;
13 while(l<r){
14 int sum = nums[i] + nums[l] + nums[r];
15 if(sum == target) return sum;
16 if(abs(sum-target) < abs(ans-target)) ans = sum;
17 if(sum < target) l++;
18 else r--;
19 }
20 }
21 return ans;
22 }
23 };
24
25 int main()
26 {
27 node n;
28 vector<int> cur = {-1,2,1,-4};
29 cout << n.threesun(cur,1) << endl;
30
31 return 0;
32 }
相关文章:
C/C++ 动态规划面试算法题
1.买卖股票的最佳时机 https://blog.csdn.net/qq_41277628/article/details/113322136 输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 1)的时候买入,在第 5 天(股票价格 6ÿ…...
kafka伪集群部署,使用zookeeper模式
1:拉去管理kafka界面UI镜像 docker pull provectuslabs/kafka-ui2:拉去管理kafka镜像 docker pull bitnami/kafka3:docker-compose.yml version: 3.8 services:zookeeper-1:container_name: zookeeper1image: bitnami/zookeeperports:- "2181:2181"environment:- …...
Postgresql 主从复制+主从切换(流复制)
pgsql有多种主从复制方式,推荐的是流复制 一、前置条件 1.至少两个pgsql数据库(可以是一台设备上的两个) 可以参考下面的教程 pgsql编译安装:pgsql 编译安装(linux) pgsql单机多开:pgsql 单机…...
java获取字符串集合中每个字符并且组成一个新的集合实现
直接怼代码,刚好碰到了这种需求,也是想了可久,其实想想也还是挺简单的 public static void main(String[] args) { // 原始字符串集合 List<String> originalList new ArrayList<>(); originalList.add("Hello"); …...

结构型设计模式——外观模式
摘要 本文主要分析设计模式 - 结构型 - 外观(Facade),它提供了一个统一的接口,用来访问子系统中的一群接口,从而让子系统更容易使用。 一、外观模式的意图 提供了一个统一的接口,用来访问子系统中的一群接口,从而让…...

【算法学习】-【双指针】-【快乐数】
LeetCode原题链接:202. 快乐数 下面是题目描述: 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果…...
【Java-LangChain:使用 ChatGPT API 搭建系统-6】处理输入-链式 Prompt Chaining Prompts
第六章,处理输入-链式 Prompt Chaining Prompts 在本章中,我们将学习如何通过将复杂任务拆分为一系列简单的子任务来链接多个 Prompt。 您可能会想,为什么要将任务拆分为多个 Prompt,而不是像我们在上一个视频中学习的那样&…...

从零手搓一个【消息队列】创建核心类, 数据库设计与实现
文章目录 一、创建核心类1, 交换机2, 交换机类型3, 队列4, 绑定5, 交换机转发 & 绑定规则6, 消息7, 消息属性 二、数据库设计1, 使用 SQLite2, 使用 MyBatis2.1, 创建 Interface2.2, 创建 xml 文件 三、硬盘管理 -- 数据库1, 创建 DataBaseManager 类2, init() 初始化数据库…...

14:00面试,14:06就出来了,这问的过于变态了。。。
前言 刚从小厂出来,没想到在另一家公司我又寄了。 在这家公司上班,每天都要加班,但看在钱给的比较多的份上,也就不太计较了。但万万没想到5月一纸通知,所有人不准加班了,不仅加班费没有了,薪资…...
url请求头信息
Accept Accept:请求报头域,用于指定客户端可接受哪些类型的信息。 Accept-Language Accept-Language:指定客户端可接受的语言类型。 Accept-Encoding Accept-Encoding:指定客户端可接受的内容编码。 Host Host:…...
【Oracle】Oracle系列之十六--数据库备份
文章目录 往期回顾1. 数据库备份的分类1.1 逻辑备份与物理备份(1)逻辑备份(2)物理备份(3)归档模式与非归档模式 1.2 完全备份/差异备份/增量备份 2. Oracle 逻辑备份2.1 EXP/IMP(1)E…...

uni-app:实现页面效果3
效果 代码 <template><view><!-- 风速风向检测器--><view class"content_position"><view class"content"><view class"SN"><view class"SN_title">设备1</view><view class&quo…...

计算机网络基础(一):网络系统概述、OSI七层模型、TCP/IP协议及数据传输
通信,在古代是通过书信与他人互通信息的意思。 今天,“通信”这个词的外沿已经得到了极大扩展,它目前的大意是指双方或多方借助某种媒介实现信息互通的行为。 如果按照当代汉语的方式理解“通信”,那么古代的互遣使节、飞鸽传书…...
互联网金融理财知识点简单总结
互联网金融理财知识点总结 互联网金融理财是指通过互联网平台进行资产管理和投资的一种金融方式。它结合了金融、科技和互联网,为投资者提供了更多选择和便捷性。本文将介绍互联网金融理财的关键知识点,包括理财基础、投资产品、风险管理和未来趋势等方…...

微信小程序template界面模板导入
我们有些时候 会有一些比较大但并不复杂的界面结构 这个时候 你可以试试这种导入模板的形式 我们在根目录创建一个 template 目录 然后下面创建一个 text文件夹下面创建一个 test.wxml 参考代码如下 <template name"textIndex"><text class "testw&…...

C/C++跨平台构建工具CMake-----在C++源码中读取CMakeLists.txt配置文件中的内容
文章目录 1.需求描述2.需求准备2.1 创建项目2.2 编辑CMakeLists.txt文件2.3 编写C文件2.4 编译构建项目 3.需求实现3.1 在CMakeLists.txt中输出日志信息3.2 增加配置生成C头文件3.3在C 源码中访问配置的值3.4 C文件中读取CMakeLists.txt中的字符串 总结 1.需求描述 当我们开发…...
【MVP争夺战】python实现-附ChatGPT解析
1.题目 MVP争夺战 知识点 :DFS搜索 时间限制:1s 空间限制:256MB 限定语言:不限 题目描述: 在星球争霸篮球赛对抗赛中,强大的宇宙战队,希望每个人都能拿到MVP。 MVP的条件是,单场最高分得分获得者,可以并列,所以宇宙战队决定在比赛中尽可能让更多的队员上场,且让所有有得…...

6 个最佳免费 Android 数据恢复软件
如果您是 Android 用户,您可能会发现没有回收站。然而,聪明的开发人员已经创建了各种 Android 数据恢复软件程序,可以解决各种与数据丢失相关的问题。 Android 数据恢复软件如何工作? 问题是当你删除一个文件时,它的数…...

数学建模Matlab之数据预处理方法
本文综合代码来自文章http://t.csdnimg.cn/P5zOD 异常值与缺失值处理 %% 数据修复 % 判断缺失值和异常值并修复,顺便光滑噪音,渡边笔记 clc,clear;close all; x 0:0.06:10; y sin(x)0.2*rand(size(x)); y(22:34) NaN; % 模拟缺失值 y(89:95) 50;% 模…...
如何保证Redis的HA高可用
目录 1.关于Redis2.Redis 的使用场景3.Redis的高可用3.1 哨兵模式(Sentinel)3.2 集群模式(Cluster) 4.参考 本文主要介绍Redis如何保证高可用。 1.关于Redis Redis(Remote Dictionary Server)是一个开源的…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...

iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...

【若依】框架项目部署笔记
参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作: 压缩包下载:http://download.redis.io/releases 1. 上传压缩包,并进入压缩包所在目录,解压到目标…...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...