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

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 输入&#xff1a;[7,1,5,3,6,4] 输出&#xff1a;5 解释&#xff1a;在第 2 天&#xff08;股票价格 1&#xff09;的时候买入&#xff0c;在第 5 天&#xff08;股票价格 6&#xff…...

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有多种主从复制方式&#xff0c;推荐的是流复制 一、前置条件 1.至少两个pgsql数据库&#xff08;可以是一台设备上的两个&#xff09; 可以参考下面的教程 pgsql编译安装&#xff1a;pgsql 编译安装&#xff08;linux&#xff09; pgsql单机多开&#xff1a;pgsql 单机…...

java获取字符串集合中每个字符并且组成一个新的集合实现

直接怼代码&#xff0c;刚好碰到了这种需求&#xff0c;也是想了可久&#xff0c;其实想想也还是挺简单的 public static void main(String[] args) { // 原始字符串集合 List<String> originalList new ArrayList<>(); originalList.add("Hello"); …...

结构型设计模式——外观模式

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

【算法学习】-【双指针】-【快乐数】

LeetCode原题链接&#xff1a;202. 快乐数 下面是题目描述&#xff1a; 「快乐数」 定义为&#xff1a; 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1&#xff0c;也可能是 无限循环 但始终变不到 1。 如果…...

【Java-LangChain:使用 ChatGPT API 搭建系统-6】处理输入-链式 Prompt Chaining Prompts

第六章&#xff0c;处理输入-链式 Prompt Chaining Prompts 在本章中&#xff0c;我们将学习如何通过将复杂任务拆分为一系列简单的子任务来链接多个 Prompt。 您可能会想&#xff0c;为什么要将任务拆分为多个 Prompt&#xff0c;而不是像我们在上一个视频中学习的那样&…...

从零手搓一个【消息队列】创建核心类, 数据库设计与实现

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

14:00面试,14:06就出来了,这问的过于变态了。。。

前言 刚从小厂出来&#xff0c;没想到在另一家公司我又寄了。 在这家公司上班&#xff0c;每天都要加班&#xff0c;但看在钱给的比较多的份上&#xff0c;也就不太计较了。但万万没想到5月一纸通知&#xff0c;所有人不准加班了&#xff0c;不仅加班费没有了&#xff0c;薪资…...

url请求头信息

Accept Accept&#xff1a;请求报头域&#xff0c;用于指定客户端可接受哪些类型的信息。 Accept-Language Accept-Language&#xff1a;指定客户端可接受的语言类型。 Accept-Encoding Accept-Encoding&#xff1a;指定客户端可接受的内容编码。 Host Host&#xff1a;…...

【Oracle】Oracle系列之十六--数据库备份

文章目录 往期回顾1. 数据库备份的分类1.1 逻辑备份与物理备份&#xff08;1&#xff09;逻辑备份&#xff08;2&#xff09;物理备份&#xff08;3&#xff09;归档模式与非归档模式 1.2 完全备份/差异备份/增量备份 2. Oracle 逻辑备份2.1 EXP/IMP&#xff08;1&#xff09;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协议及数据传输

通信&#xff0c;在古代是通过书信与他人互通信息的意思。 今天&#xff0c;“通信”这个词的外沿已经得到了极大扩展&#xff0c;它目前的大意是指双方或多方借助某种媒介实现信息互通的行为。 如果按照当代汉语的方式理解“通信”&#xff0c;那么古代的互遣使节、飞鸽传书…...

互联网金融理财知识点简单总结

互联网金融理财知识点总结 互联网金融理财是指通过互联网平台进行资产管理和投资的一种金融方式。它结合了金融、科技和互联网&#xff0c;为投资者提供了更多选择和便捷性。本文将介绍互联网金融理财的关键知识点&#xff0c;包括理财基础、投资产品、风险管理和未来趋势等方…...

微信小程序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 用户&#xff0c;您可能会发现没有回收站。然而&#xff0c;聪明的开发人员已经创建了各种 Android 数据恢复软件程序&#xff0c;可以解决各种与数据丢失相关的问题。 Android 数据恢复软件如何工作&#xff1f; 问题是当你删除一个文件时&#xff0c;它的数…...

数学建模Matlab之数据预处理方法

本文综合代码来自文章http://t.csdnimg.cn/P5zOD 异常值与缺失值处理 %% 数据修复 % 判断缺失值和异常值并修复&#xff0c;顺便光滑噪音&#xff0c;渡边笔记 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 哨兵模式&#xff08;Sentinel&#xff09;3.2 集群模式&#xff08;Cluster&#xff09; 4.参考 本文主要介绍Redis如何保证高可用。 1.关于Redis Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001

qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类&#xff0c;直接把源文件拖进VS的项目里&#xff0c;然后VS卡住十秒&#xff0c;然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分&#xff0c;导致编译的时候找不到了。因…...

深入理解 React 样式方案

React 的样式方案较多,在应用开发初期,开发者需要根据项目业务具体情况选择对应样式方案。React 样式方案主要有: 1. 内联样式 2. module css 3. css in js 4. tailwind css 这些方案中,均有各自的优势和缺点。 1. 方案优劣势 1. 内联样式: 简单直观,适合动态样式和…...